Hallo, leider war kein Forum passend. Daher habe ich das bestbesuchte genommen ;) Die Frage: Aus einer Urne mit 64 durchnummerierten Kugeln werden eine zufällige Anzahl an Kugeln gezogen. Wie hoch ist die Wahrscheinlichkeit, dass die Kugel mit Nummer 1 und die Kugel mit Nummer 2 gleichzeitig gezogen werden? Anmerkung: Eigentlich erwarte ich eine recht niedrige Wahrscheinlichkeit. Jedoch habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt und wundere mich über die Herkunft dieses hohen Wertes... Danke im Voraus und beste Grüße
blablub schrieb: > Wie hoch ist die Wahrscheinlichkeit, dass die > Kugel mit Nummer 1 und die Kugel mit Nummer 2 gleichzeitig gezogen > werden? grob irgendwas zwischen 0 und 1 ... (Ich hasse Stochastik)
Mit oder ohne zurücklegen? Mit zurücklegen liegt die Chance beide male bei 1:64, also 1:(64*64), ohne Zurücklegen bei 1:64*1:63. Wahrscheinlichkeiten werden multipliziert.
Offtopic wär' nicht schlecht gewesen. Oder einfach im Unterricht zuhören.
blablub schrieb: > Jedoch habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt ... Zeigt doch bitte dein Experiment.
Ah ja und was hat das mit Kombinatorik zu tun? Und dann noch "fortgeschritten", du bist mir ja ein lustiger.
Martin Schwaikert schrieb: > Mit zurücklegen liegt die Chance beide male bei 1:64, also 1:(64*64), > ohne Zurücklegen bei 1:64*1:63. Wahrscheinlichkeiten werden > multipliziert. Martin Schwaikert schrieb: > Mit oder ohne zurücklegen? > > Mit zurücklegen liegt die Chance beide male bei 1:64, also 1:(64*64), > ohne Zurücklegen bei 1:64*1:63. Wahrscheinlichkeiten werden > multipliziert. Noch einmal die Aufgabe lesen.
Martin Schwaikert schrieb: > Mit oder ohne zurücklegen? > > Mit zurücklegen liegt die Chance beide male bei 1:64, also 1:(64*64), > ohne Zurücklegen bei 1:64*1:63. Wahrscheinlichkeiten werden > multipliziert. Es wird quasi auf einmal eine zufällige Anzahl entnommen. Daher nicht eine Binominalverteilung, sondern viele...
Jürgen schrieb: > blablub schrieb: >> Jedoch habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt ... > > Zeigt doch bitte dein Experiment. also im pseudocode: while(lange) { uint64 a = rand64(); if (2bestimmte bits gesetzt) good++; else bad++; } good/(bad+good) = 25%; Electronics'nStuff schrieb: > Ah ja und was hat das mit Kombinatorik zu tun? > Und dann noch "fortgeschritten", du bist mir ja ein lustiger. ah ja und deine Lösung?
blablub schrieb: > ah ja und deine Lösung? Oh, ich entschuldige mich. Habe das auch so verstanden wie Martin.
blablub schrieb: > Eigentlich erwarte ich eine recht niedrige Wahrscheinlichkeit. Jedoch > habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt und > wundere mich über die Herkunft dieses hohen Wertes... Könnte ich mir schon vorstellen. Wieviele Möglichkeitenb gibt es denn, wenn du 50 Kugeln von den 64 ziehst. Und in wievielen dieser Möglichkeiten ist jeweils Kugel 1 und Kugel 2 enthalten. Wieviele Möglichkeiten gibt es bei 51 gezogenen Kugeln? Wie oft ist 1 & 2 dabei? etc. etc. Sicher. Ziehst du nur wenige Kugeln, ist die Wahrscheinlichkeit für 1&2 nicht sehr hoch. ABer je mehr Kugeln du in einem Durchgang ziehst, desto höher wird sie. Und offnbar genügt das, um die Wahrscheinlichkeit über alle n-gezogenen Kugeln (n beliebig) hochzutreiben.
blablub schrieb: > Aus einer Urne mit 64 durchnummerierten Kugeln werden eine zufällige > Anzahl an Kugeln gezogen. Wie hoch ist die Wahrscheinlichkeit, dass die > Kugel mit Nummer 1 und die Kugel mit Nummer 2 gleichzeitig gezogen > werden? Wird eine Kugel gezogen: Wahrscheinlichkeit = 0% Werden 16 Kugeln gezogen: Wahrscheinlichkeit = 25% Werden 32 Kugeln gezogen: Wahrscheinlichkeit = 50% Werden 48 Kugeln gezogen: Wahrscheinlichkeit = 75% Werden alle Kugeln gezogen: Wahrscheinlichkeit = 100% Da die Anzahl gezogener Kugeln zufällig ist, muss bei unendlich vielen Durchgängen der Durchschnittswert der Anzahl gezogenen Kugeln genau 32 sein. Somit liegt die Wahrscheinlichkeit bei 50%. Ich hab von Wahrscheinlichkeitsrechnungen absolut keine Ahnung. Also korrigiert mich wenn ich falsch liege.
be stucki schrieb: > bei unendlich vielen > Durchgängen Ich glaube da liegt der Fehler, er spricht (soweit ich das verstanden habe) von einem einzelnen Durchgang.
Und abgesehen davon, wird die Wahrscheinlichkeit nicht als Prozentzahl anzugeben sein, sondern im Verhältnis zu Anzahl gezogener Kugeln X nehme ich an? Weil sonst ist das ja irgendwie nicht möglich. Also sowas wie X * 0.1347%
blablub schrieb: > Anmerkung: > Eigentlich erwarte ich eine recht niedrige Wahrscheinlichkeit. Jedoch > habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt und > wundere mich über die Herkunft dieses hohen Wertes... Ich wäre extrem erstaunt wenn 25% die Lösung ist! Da scheint das Experiment wohl nicht ganz mit der Aufgabenstellung zu korrelieren;-)
blablub schrieb: > also im pseudocode: > > while(lange) > { > uint64 a = rand64(); > if (2bestimmte bits gesetzt) > good++; > else > bad++; > } > > good/(bad+good) = 25%; Dass da 25% rauskommt, ist ja kein Wunder. Für die zwei Bits gibt es vier Möglichkeiten: 0 und 0 0 und 1 1 und 0 1 und 1 <- der Fall wird gezählt. Alle vier Fälle sind gleich wahrscheinlich => 25% Wahrscheinlichkeit. Das ist aber erstmal nicht die korrekte Simulation für die Fragestellung. Du müsstest erst mal eine zufällige Zahl zwischen 1 und 64 generieren und dann entsprechend viele zufällige Bits auf 1 setzen. Danach kannst Du schauen, ob die beiden ersten Bits gesetzt sind. Könnte aber gut sein, dass am Ende (fast) das gleiche rauskommt, weil ja im Schnitt 32,5 Kugeln gezogen werden (Bits gesetzt sind). Wenn man auch 0 Kugeln ziehen könnte, wärens im Schnitt 32 Bits, also wie oben. Bin mir aber nicht 100% sicher, ob das man das so rechnen darf.
@xfr bingo, das ist die Lösung. In der Zwischenzeit wurde ich schon von Kollegen ausgelacht, dass ich nicht draufgekommen bin, da es ja so "eindeutig" ist :) Grund für die Eindeutigkeit ist die Gleichverteilung aller Bits
xfr schrieb: > Das ist aber erstmal nicht die korrekte Simulation für die > Fragestellung. Du müsstest erst mal eine zufällige Zahl zwischen 1 und > 64 generieren und dann entsprechend viele zufällige Bits auf 1 setzen. > Danach kannst Du schauen, ob die beiden ersten Bits gesetzt sind. inwieweit würde sich das vom pseudocode unterscheiden?
xfr schrieb: > Das ist aber erstmal nicht die korrekte Simulation für die > Fragestellung. Du müsstest erst mal eine zufällige Zahl zwischen 1 und > 64 generieren und dann entsprechend viele zufällige Bits auf 1 setzen. > Danach kannst Du schauen, ob die beiden ersten Bits gesetzt sind. So isses. Die Anzahl/Wahrscheinlichkeit der gesetzten Bits entspricht bei seinem Experiment nicht der Aufgabenstellung. > Könnte aber gut sein, dass am Ende (fast) das gleiche rauskommt, weil ja > im Schnitt 32,5 Kugeln gezogen werden (Bits gesetzt sind). Wenn man auch > 0 Kugeln ziehen könnte, wärens im Schnitt 32 Bits, also wie oben. Bin > mir aber nicht 100% sicher, ob das man das so rechnen darf. Das Ergebnis ist signifikant anders;-)
blablub schrieb: > Aus einer Urne mit 64 durchnummerierten Kugeln werden eine zufällige > Anzahl an Kugeln gezogen Wenn du zufälligerweise immer 64 Kugeln ziehen musst, liegt die Wahrscheinlichkeit bei 1. Mal im Ernst, die Angabe zufällige Anzahl Kugeln ziehen" ist Mist. Das macht den Zufall nicht wahrscheinlicher.
So ist es. Ich überlege auch schon die ganze Zeit. Das einzige Ergebnis, zu dem ich bisher gekommen bin, ist, dass die Aufgabe mit den genannten Angaben nicht eindeutig lösbar ist.
Floh schrieb: > blablub schrieb: >> Aus einer Urne mit 64 durchnummerierten Kugeln werden eine zufällige >> Anzahl an Kugeln gezogen > > Wenn du zufälligerweise immer 64 Kugeln ziehen musst, liegt die > Wahrscheinlichkeit bei 1. ??? ja ich könnte auch immer im Lotto richtig tippen... > > Mal im Ernst, die Angabe zufällige Anzahl Kugeln ziehen" ist Mist. Das > macht den Zufall nicht wahrscheinlicher. ja genau da lag auch mein Denkfehler.
Hallo blablub, > habe ich experimentell eine Wahrscheinlichkeit von 25% bestimmt und > wundere mich über die Herkunft dieses hohen Wertes... Doch, diese Wahrscheionlichkeit ist 0.25! Wenn die Anzahl der beim Experiment gezogenen Kugeln gleichverteilt ist, ist die Wahrscheinlichkeit, dass dei "1" dabei ist = 0.5 Ebenso die (unabhaengige) Wahrscheinlichkeit, dass eine "2" dabei ist. Damit ist die Ergebniswahrscheinklichkeit fuer das Experiment ("1" UND "2") = 0.25! Gruss Michael
Floh schrieb: > Mal im Ernst, die Angabe zufällige Anzahl Kugeln ziehen" ist Mist. Das > macht den Zufall nicht wahrscheinlicher. Ob das nun 'Mist' ist oder nicht, es ist auf jeden Fall wichtig für die Aufgabe bzw. das Ergebnis!
Die Antwort hängt davon ab, wie die Rahmenbedingungen genau definiert werden. Es gibt n=64 Kugeln. Ich gehe von einer Nummerierung von 1 bis 64 aus. Bei der zufälligen Anzahl an Kugeln muss man definieren, welche Zahlenmenge M man annimmt. Z.B. kann man auch 0 oder 1 Kugeln ziehen. Dann gibt es M=65 mögliche Anzahlen an gezogenen Kugeln. Nämlich {0;1;2...;63;64} Die Wahrscheinlichkeit, dass ich m Kugeln ziehe liegt bei 1/M. Also: Gezogene Kugeln Wahrscheinlichkeit 0 1/M 1 1/M 2 1/M ... m=64 1/M Als nächstes musst du für jede möglich Anzahl an gezogenen Kugeln bestimmen, wie groß die Wahrscheinlichkeit ist, dass eine 1 und eine 2 gezogen wird. Also für den Fall, dass {0;1;2...;63;64} Kugeln gezogen werden. Wenn du nun jede Teilwahrscheinlichkeit addierst kommst du auf die Gesamtwahrscheinlichkeit.
Michael Roek schrieb: > Doch, diese Wahrscheionlichkeit ist 0.25! > > Wenn die Anzahl der beim Experiment gezogenen Kugeln gleichverteilt ist, > ist die Wahrscheinlichkeit, dass dei "1" dabei ist = 0.5 > Ebenso die (unabhaengige) Wahrscheinlichkeit, dass eine "2" dabei ist. > Damit ist die Ergebniswahrscheinklichkeit fuer das Experiment ("1" UND > "2") = 0.25! Wenn wir mal keine Annahmen machen, sondern die ursprüngliche Aufgabenstellung nehmen, dann würde ich das mit den 25 % noch einmal überdenken! ;-)
blablub schrieb: > inwieweit würde sich das vom pseudocode unterscheiden? So in etwa könnte man es simulieren:
1 | while (lange) { |
2 | uint64_t bitfeld = 0; |
3 | int anzahl_gezogen = rand_zwischen(1, 64); |
4 | |
5 | for (int i = 0; i < anzahl_gezogen; i++) { |
6 | position = rand_zwischen(0, 63); |
7 | while (bit_ist_gesetzt(bitfeld, position)) { |
8 | // Bit ist schon gesetzt, nimm nächste Position
|
9 | position = (position + 1) % 64; |
10 | }
|
11 | setze_bit(bitfeld, position); |
12 | }
|
13 | |
14 | if (bit_ist_gesetzt(bitfeld, 0) && bit_ist_gesetzt(bitfeld, 1)) { |
15 | good++; |
16 | } else { |
17 | bad++; |
18 | }
|
19 | }
|
OK, nicht Geschwindigkeitsoptimiert, dafür aber lesbar...
1 | #!/usr/bin/env python
|
2 | # -*- coding: utf-8 -*-
|
3 | |
4 | import random |
5 | |
6 | Versuche = 100000 |
7 | Treffer = 0 |
8 | Kugelanzahl = 64 |
9 | |
10 | # Originalurne mit Kugeln Nr1 - Nr{Kugelanzahl} füllen
|
11 | Originalurne = [x for x in range(1,Kugelanzahl+1)] |
12 | |
13 | for i in range(Versuche): |
14 | Anzahl_ziehen = random.randint(0,Kugelanzahl) # 0 - {Kugelanzahl} Kugeln ziehen |
15 | noch_zu_ziehen = Anzahl_ziehen |
16 | |
17 | Urne = Originalurne[:] # Kopie des Originalbeutels |
18 | Gezogen = [] # 'Gezogene' leeren |
19 | while noch_zu_ziehen > 0: |
20 | n = random.randint(0,len(Urne)-1) # welche Kugel ziehen wir? |
21 | Kugel = Urne.pop(n) # aus der Urne nehmen |
22 | Gezogen.append(Kugel) # zu den Gezogenen hinzufügen |
23 | noch_zu_ziehen -= 1 |
24 | |
25 | if (1 in Gezogen) and (2 in Gezogen): |
26 | Treffer += 1 |
27 | |
28 | print Versuche,Treffer |
Hehe, cool, läuft ja sogar. :) Und ist wirklich ein anderes Ergebnis. Also Merke: Mit solchen Vereinfachungen wie "im Schnitt werden 32 Kugeln gezogen, also rechne ich damit" sollte man sehr vorsichtig sein ...
Konnte gerade nicht widerstehen, meinen Pseudocode auch noch lauffähig zu machen. Es kommt auch das gleiche raus, nur um einiges schneller. :D Interessanterweise darf man allerdings nicht einfach die nächste Bitposition benutzen, falls die erste generierte Stelle schon belegt ist, sondern muss ein neue Zahl generieren. Ansonsten erhält man ein leicht höheres Ergebnis. Hier der Code (quick and dirty ...):
1 | #include <stdint.h> |
2 | #include <stdio.h> |
3 | #include <stdlib.h> |
4 | #include <time.h> |
5 | |
6 | #define set_bit(var, bit) ((var) |= (1ULL<<(bit)))
|
7 | #define bit_is_set(var, bit) ((var) & (1ULL<<(bit)))
|
8 | |
9 | int main(void) |
10 | {
|
11 | uint64_t bitfeld; |
12 | int anzahl_gezogen; |
13 | int position; |
14 | int versuch; |
15 | int versuche = 100000; |
16 | int treffer = 0; |
17 | |
18 | srand(time(NULL)); |
19 | |
20 | for (versuch = 0; versuch < versuche; versuch++) { |
21 | bitfeld = 0; |
22 | anzahl_gezogen = rand() % 65; |
23 | |
24 | int i; |
25 | for (i = 0; i < anzahl_gezogen; i++) { |
26 | do { |
27 | position = rand() % 64; |
28 | } while (bit_is_set(bitfeld, position)); |
29 | set_bit(bitfeld, position); |
30 | }
|
31 | if (bit_is_set(bitfeld, 0) && bit_is_set(bitfeld, 1)) { |
32 | treffer++; |
33 | }
|
34 | }
|
35 | |
36 | printf("Versuche: %i, Treffer: %i\r\n", versuche, treffer); |
37 | }
|
xfr schrieb: > Konnte gerade nicht widerstehen, meinen Pseudocode auch noch lauffähig > zu machen. Es kommt auch das gleiche raus, nur um einiges schneller. :D > > Interessanterweise darf man allerdings nicht einfach die nächste > Bitposition benutzen, falls die erste generierte Stelle schon belegt > ist, sondern muss ein neue Zahl generieren. Ansonsten erhält man ein > leicht höheres Ergebnis. hmm in deinem code kann doch eine position mehrmals vergeben. also z.b die erste und zweite kugel der dritten position oder übersehe ich da was?
Wenn die Position schon belegt ist, wird so lange ein neue gewürfelt, bis man eine freie Stelle trifft:
1 | do { |
2 | position = rand() % 64; |
3 | } while (bit_is_set(bitfeld, position)); |
Ist sicherlich nicht der effizienteste Weg, aber läuft trotzdem deutlich schneller als das Python-Programm. ;-)
xfr schrieb: > Ist sicherlich nicht der effizienteste Weg, aber läuft trotzdem deutlich > schneller als das Python-Programm. ;-) Man kann das Python Programm ca. 30-50 mal schneller machen wenn man die Listenmanipulationen optimiert und unleserlich macht. <Lästermodus> Allerdings siehts's dann ähnlich aus wie C-code (also wie ein ungemachtes Bett) ;-) PS: Setz doch mal beim C-Source die Anzahl der Kugeln auf 2000 :-) </Lästermodus>
Mathematisch (unter der Voraussetzung dass die Anzahl der gezogenen Kugeln (0 bis 64) linear verteilt ist):
kann man sich natürlich sparen. Wer kann's beweisen?
Allgemein kann man sogar sagen: Wenn aus n Kugeln, die von 1 bis n durchnummeriert sind, gleichverteilt zufällig k gezogen werden (0≤k≤n), ist die Wahrscheinlichkeit, dass alle Kugeln mit den Nummern 1 bis m (1≤m≤n) darunter sind, 1/(m+1). Interessanterweise hängt diese Wahrscheinlichkeit nicht von n ab. Im obigen Beispiel ist m=2, damit ist die Wahrscheinlichkeit 1/3, wie "Name" schon richtig erkannt hat. Name schrieb: > Wer kann's beweisen? Den Beweis hast du ja praktisch schon hingeschrieben. Man muss nur noch den Term etwas vereinfachen. Als erstes lässt sich der Bruch kürzen, wodurch es leichter wird, die Summe zusammenzufassen.
> Aus einer Urne mit 64 durchnummerierten Kugeln
In ner Urne iss Asche!!
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.