ubuntuusers.de

Hallo alle zusammen,

der folgende Punkt hat eigentlich nichts mit Linux oder Programmieren zu tun. Aber vielleicht hat ja doch der eine oder andere eine Idee?

Ich habe eine Menge von 50.000 Elementen

Ich ziehe nun 1.000 mal (ohne Zurücklegen) aus diesen Elementen. Anschließend ziehe ich 500 mal (wieder ohne zurücklegen) aus der Ursprungsmenge von 50.000 Elementen.

Zwischen den beiden Mengen habe ich eine Schnittmenge von 100. Das heißt ich habe 100 Elemente in beiden Experimenten gezogen. Mich würde interessieren, wie hoch die Wahrscheinlichkeit hierfür ist...

Leider ist die Statistik Vorlesung schon längst wieder vergessen. Vielleicht hat ja jemand eine Idee? Danke jedenfalls..

Erechtheus schrieb:

der folgende Punkt hat eigentlich nichts mit Linux oder Programmieren zu tun.

Dann bist Du hier falsch. Dafür gibt es Foren wie z. B. matheplanet.com.

Danke, ich probiers dann dort...

Naja, man könnte das natürlich simulieren 😉

Einfach eine Menge von 50.000 Elementen erstellen, dann 1000 ziehen, dann 500 ziehen und dann vergleichen. Ist die Übereinstimmung exakt 100, dann Erfolgszähler +1. Nach ausreichend vielen Durchgängen hat man so einen Näherungswert ... 😀

Sollen es genau oder mindestens 100 Übereinstimmungen sein?

Angenommen Du hast 10 Elemente, und ziehst 5. Und nochmal 10 und ziehst 2. Und wie groß ist die Wahrscheinlichkeit, daß von den 2en genau eins in den 5en ist? Wie bist Du drauf gekommen? ☺

So, mir war langweilig 😀 Python Script

Viel Spaß beim Durchtesten ... 10000 Experimente ergaben bei mir noch 0%. Da muss man wohl mehr investieren ...

Aber bei kleineren Werten klappt's.

# 2x Ziehen und durch set() duplikate (=Übereinstimmungen) entfernen

Es sollte doch ohne Zurücklegen gezogen werden - wie kann es da zu Duplikaten kommen? Oder verstehe ich was falsch?

user unknown schrieb:

# 2x Ziehen und durch set() duplikate (=Übereinstimmungen) entfernen

Es sollte doch ohne Zurücklegen gezogen werden - wie kann es da zu Duplikaten kommen? Oder verstehe ich was falsch?

Ja wird es ja auch! Aber ja 2x jeweils aus der Ursprungsmenge. Dabei kann ja gerade der Fall auftreten, dass ein Element in beiden Ziehungen dabei ist. Sind es genau 100, ist dieses Experiement ja gelungen.

Ich wende den "Trick" an, dass ich einfach genau diese Duplikate entferne und dann die Differenz überprüfe. Diese muss bei 100 Übereinstimmungen eben wieder genau 100 ergeben.

Im Prinzip ist das Problem simpel. Von den 50.000 Objekten werden im ersten Experiment 1.000 ausgewählt. Diese sind dann vor dem Beginn der zweiten Ziehung sozusagen „markiert“. Die restlichen Eigenschaften der Objekte interessieren nach der Fragestellung nicht. Es wurde nur gefragt, wie hoch die Wahrscheinlichkeit ist 100 Objekte nochmal zu ziehen. Keine Aussagen über sonstige Unterscheidungsmerkmale.

Anschließend müsste man sich einen Baum aufstellen. Beim ersten Objekt ist die Wahrscheinlichkeit P(M) = 1000/50000 = 1/50, dass ein markiertes Objekt gezogen wird. – Das wäre dann P(M) = positive_Objekte/gesamt_Objekte. – Bei der Ziehung des zweiten Objektes ist die Chance dann nur noch P(M)=999/49999 und so weiter. Umgekehrt gibt es natürlich bei jedem Zug auch die andere Möglichkeit, dass ein unmarkiertes Objekt gezogen wird, z.B. P(U) = 49000/50000 = 49/50 für das erste Objekt.

Das müsste man dann für jede Rekursion durchführen und die Wahrscheinlichkeiten jeweils multiplizieren. Also in obigem Fall wird zweimal gezogen und zwei markierte Objekte gezogen, dann ist die Wahrscheinlichkeit dafür: P(MM) = 1/50 * 999/49999 = 0,000399

Auf diese Weise erhält man für jeden Pfad entlang des Baumes eine Wahrscheinlichkeit – die Wahrscheinlichkeiten für alle Pfade mit genau 100 markierten Objekten kann man addieren. Oder die Wahrscheinlichkeiten für alle Pfade bei denen mindestens 100 markierte gezogen werden, oder … Viel Spaß, der Baum hat viele Pfade 😀

Jetzt ist die Frage ob man das mathematisch einfacher berechnen kann … Ich vermute schon, Vermutlich über irgendwelche Binomialkoeffizienten, hab aber keine Ahnung wie man das Modell darauf umsetzen kann. Und auch wenig Lust das jetzt zu recherchieren. 😀

~jug

Wie muß ich denn den Code ändern, daß statt 50000, 1000, 500, 100 die Werte 10, 5, 2, 1 gewählt werden? Das müßte man ja in endlicher Zeit zu einem Mittelwert treiben können, der sich von Hand überprüfen läßt.

– Meine erste Überlegung ist, daß die erste Ziehung ziemlich uninteressant ist. Wir können als Elemente die natürlichen Zahlen bis 50.000 annehmen, und annehmen, daß die ersten 1000 Zahlen gezogen werden. Das ist so wahrscheinlich wie jede andere Ziehung, und für die Folgeziehung ist es auch unerheblich wie die Zahlen heißen, die gezogen wurden. Es macht die Sache aber übersichtlicher.

Also mein simples Beispiel: Aus den 10 Zahlen (0..9) werden 2 gezogen, und wie hoch ist die Wahrscheinlichkeit, daß genau eine < 5 ist.

a) Das die erste Zahl < 5 ist trifft mit 5/10 Wahrscheinlichkeit ein, und
b) mit 5/10 ist die erste Zahl größer
c) Die zweite Zahl, wenn a) eintrat, ist - da nur noch 4 von 9 kleiner als 5 sind,
caa) mit 4/9 < 5 (ungünstiges Ereignis)
cab) mit 5/9 >= 5 zum günstigen Ereignis
d) Wenn b eintrat sind noch 5 kleinere Zahlen vorhanden
dba) mit 5/9 Wahrscheinlichkeit trifft das günstige Ereignis ein (bisher noch keine kleinere Zahl, aber jetzt)
dbb) mit 4/9 trifft das ungünstige Ereignis ein.

Die Gesamtwahrscheinlichkeiten bilden sich aus der Summe der multiplizierten Wahrscheinlichkeiten.

5/10 * 5/9 (cab) + 5/10*5/9 (dba) günstiges Ereignis 
= 2*(5/10*5/9) = 0.55
5/10 * 4/9 (caa) + 5/10*4/9 (dbb) ungünstiges Ereignis 
= 2*(5/10*4/9) = 0.44

Das schöne daran ist, daß es insgesamt 0.99 ergibt, was hinreichend nah am erwünschten 1.0 ist - die richtigen Zahlen sind 2*25/90 + 2*20/90 = (40+50)/90 = 1 q.e.d.

Was sagt das Pythonprogramm - ich finde die Schlüsselzahlen 50.000, 1.000, 500 und 100 nur im Kommentar.

Ist die Fragestellung überhaupt korrekt formuliert? Denn wenn man je aus 50.000 Elementen einmal 1000 Elemente und einmal 500 Elemente zieht, ist eine Schnittmenge von 100 Elementen doch utopisch. Die Wahrscheinlichkeit dafür muss nahe 0% liegen.

Das ganze Problem ist im Grunde relativ einfach. Seien die Elemente der Menge der Einfachheit halber die Zahlen 1..50000. Angenommen, die Zahlen 1..100 werden in beiden Ziehungen gezogen, und alle anderen in höchstens einer der beiden Ziehungen. Dann muss ich aus den verbleibenden 49900 Zahlen 900 ziehen, um die Menge mit 1000 Elementen zu füllen. Dafür gibt es (49900 über 900) Möglichkeiten. Jetzt muss ich aus den restlichen 49000 Zahlen noch 400 für die Menge mit 500 Elementen ziehen, hierfür gibt es (49000 über 400) Möglichkeiten. Außerdem muss ich noch mit (50000 über 100) multiplizieren, da es ja noch viele andere mögliche 100-elementige Schnittmengen gibt. Insgesamt gibt es also (50000 über 100) * (49900 über 900) * (49000 über 400) günstige Fälle. Die Anzahl der möglichen Fälle beträgt einfach (50000 über 1000) * (50000 über 500). Es ergibt sich also insgesamt

[1]/[2]

Wer mag kann das jetzt ausrechnen. Numerisch wird das allerdings schwer, da die Zahlen wahrscheinlich zu groß werden.

//edit: ICH WILL MEINEN BBCODE ZURÜCK, VERDAMMT!
Gemeint war natürlich ((50000 über 100) * (49900 über 900) * (49000 über 400))/((50000 über 1000) * (50000 über 500)) und nicht der Schwachsinn, den diese Krankheit von einer Forensoftware daraus gemacht hat.

• 1: 50000 über 100) * (49900 über 900) * (49000 über 400
• 2: 50000 über 1000) * (50000 über 500

Die Vorschau ist Dein Freund. ☺

Was spricht denn dafür die erste Ziehung zu berücksichtigen? Wenn wir mit kleinen Zahlen operieren:

Es gibt Total 500.
Davon ziehen wir in einem ersten Durchgang 10.
In einem zweiten versuchen wir bei genau 5 Ziehungen eine der Ziffern der ersten Ziehung zu treffen.

Darauf hat doch keinen Einfluß welche Ziffern wir im ersten Zug gezogen haben.
Wir können einfach annehmen im ersten Zug ziehen wir die Zahlen 0-9, und versuchen im zweiten Zug bei 5 Ziehungen eine Zahl < 10 zu treffen.
Ziehen wir andere Zahlen als 0-9 im ersten Zug, so ändert sich ja nur der Name der Zahl die wir suchen - nicht aber die Chance eine Zahl zu treffen. Anders ausgedrückt können wir die erste Zahlengruppe ziehen, und taufen die Zahlen um auf die Namen 0-9. Die Namen 0 bis 9 der Ausgangsmenge, wenn sie nicht in der gezogenen Menge sind, vergeben wir neu mit den überschriebenen Zahlen. Würde sich jemand für den Namen der ursprünglichen Zahlen interessieren, so könnten wir die Kugeln auspacken, und den alten Namen herausfinden - aber niemand will den alten Namen wissen. (Das sind alles Ignoranten ☺ ).

Dem X über Y konnte ich nicht ganz folgen, obwohl ich mich daran erinnere, sowas gekonnt zu haben, und daß das ein häufiger Trick ist, die Komplementärmenge zu bestimmen.

Hello World meint:

(naja - war zugegebenermaßen keine Freude das einzugeben, und sieht auch nicht einleuchtend aus.

Das will ich mal mit den 10,5,2,1-Werten testen. Die allgemeine Formel lautet doch:

• Aus einer Liste von M Objekten (50.000, 10)

• zieh N (500, 5)

• und prüfe, ob P (100,1) davon < O (1000, 2)

die erste Zahl jeweils aus Aufgabenstellung, die zweite als Testbeispiel.

Allgemein:

Beispiel:

ergo:

Mit Fakultäten:

Gelebte Subtraktion sieht so aus:

  10!     9!     8!        10!     10! 
 ----- *  -- *  -----  /( ---  *  -----)
 1!*9!    8!    4!*4!     2!8!    5!*5!

und ein paar offensichtliche Vereinfachungen:

  10     9    8*7*6*5     10*9   10*9*8*7*6 
 ----- * -- * -------  /( ---- * ----------)
   1     1    4*3*2*1      2      5*4*3*2

es schrumpft zusammen

  90      7*2*5        5*9    9*2*7*2 
 -----  * -------  / (---- * -----------)
   1       1            1      1

  90 * 70 /( 9 * 9*2*5*7*2 )   

und

  90 * 70
------------
( 9*9*70*2 )   

\⇒

  5 
-----
( 9 )   

5/9 - das entspricht meiner Programmausgabe. (0 Komma Periode 5).

Daraus schließe ich mal, daß die Formel stimmt. ☺

bremer schrieb:

Ist die Fragestellung überhaupt korrekt formuliert? Denn wenn man je aus 50.000 Elementen einmal 1000 Elemente und einmal 500 Elemente zieht, ist eine Schnittmenge von 100 Elementen doch utopisch. Die Wahrscheinlichkeit dafür muss nahe 0% liegen.

Deshalb wird die Frage ja erst interessant. Wenn ich 10 Läufe meines Programms ansetze, dann schwankt es munter um die 10 o.s.ä. und sieht aus, als könnte es noch sehr lange dauern, bis die 100 getroffen wird. Geschweige denn, daß sie so oft getroffen wird, daß man Aussagen über die Häufigkeit wagen würde.

anz = 14 ? = 100
anz = 12 ? = 100
anz = 13 ? = 100
anz = 12 ? = 100
anz = 8 ? = 100
anz = 15 ? = 100
anz = 3 ? = 100
anz = 10 ? = 100
anz = 11 ? = 100
anz = 8 ? = 100

Ausrechnen geht gewiß schneller.

Dieses bc-Script:

define fac (x) {
	if (x <= 1) return (1);
	return (fac(x-1) * x);
}

define ue (o, u) {
	return (fac (o) / (fac (u) * fac (o-u)))
}

define erg (n, m, o, p) {
	return (ue (m, p) * ue (m-p, o-p) * ue (m-o, n-p)) / (ue (m, o) * ue (m, n))
}

erg (2, 10, 5, 1) 
erg (5, 500, 10, 1) 
erg (50, 5000, 100, 10) 
scale=50
erg (500, 50000, 1000, 100) 

ließ ich laufen, allerdings ohne die Zeile scale=50, und bekam als Ergebnis:

.55555555555555555555
.09295778542189725871
.00000003210062854883
0

Es dauert ziemlich lange - eine Fakultätsfunktion, die die berechneten Werte cached, wäre wohl ein großer Gewinn. Ob das mit bc geht weiß ich gar nicht.

Grob überschlagen sage ich voraus, dass wir die Frage nicht beantworten werden, solange wir mit Fließkommazahlen arbeiten. 64bit dürften dafür nicht ausreichen.

/: Mein Ergebnis lautet: 1 / 18702648385559950437214276323901142382909011676228781857433459698440400800246476073936165125482268193638015615396237226102441926035443687374749498997995