Stochastik - Zufallszahlen 3 größte aus 5 Zahlen

Neue Frage »

LearningBoy Auf diesen Beitrag antworten »
Stochastik - Zufallszahlen 3 größte aus 5 Zahlen
Meine Frage:
Hallo Leute,

ich stecke, wie ihr euch bestimmt denken könnt, in einem kleinem Problem.
Es geht darum die Wahrscheinlichkeit auszurechnen, ob die dritt kleinste Zahl von 5 aus n verschiedenen Zahlen in dem Intervall n/3 < gezogene Zahl <= (2n)/3 liegt.

Dh ich habe ein unsortiertes Array mit n Zahlen. Ich ziehe 5 Karten, nach dem ziehen lege ich die Karte wieder zurück, => Karten können mehrmals gezogen werden. Habe ich meine 5 Karten beisammen nehme ich mir die mittlere Karte raus. Mit welcher Wahrscheinlichkeit liegt die Karte dann im Intervall zwischen n/3 < x <= (2n)/3, sprich im mittleren Drittel.

Wem es etwas sagt, es geht um die randomisierte Variante des Quicksort Algorithmus. r(Pivot)

Ich danke euch schon mal für eure Ansätze, aus Stochastik bin ich leider komplett raus smile .

Meine Ideen:
An sich ist die Wahrscheinlichkeit eine beliebige Nummer zu ziehen 1/n.
Ich ziehe fünf Karten und nehme die mittlere ?? - keine Ahnung smile

Weis nicht wie ich das einbauen kann, erwartete Laufzeit für den Algorithmus bei zufälliger Zahl des Pivots ist O(n*log(n)) das muss sich ja irgendwie verbessern, wenn ich 5 Karten nehme und die mittlere nehme..
tianstar Auf diesen Beitrag antworten »

Ich bin LearningBoy, wusste nicht das ich noch ein Account hatte smile .

Eigentlich ist es doch egal das es n Zahlen sind da alle gleich wahrscheinlich sind. Dh mich intressiert nur , das die mittlere Karte in dem Areal in der Mitte ist.

Dh ich summiere die Wahrscheinlichkeiten von den Ereignissen, dass es so ist einfach auf.

Sprich da die Wkeit 1/3 ist aus einem der 3 Intervalle zu kommen, ergibt sich (1/3)^5 * Anzahl der guten Ereignisse.

Gutes Ereignis := 3 Karte kommt aus dem mittleren Intervall.

1. | 2. | 3.
--------------
2 | 1 | 2
0 | 5 | 0

etc.. ?

Komme da auf 9 gute Ereignisse sprich eine Wkeit von 1/27 ? Was meiner Vermutung von Oben entgegenspricht ein besseres Ereignis zu bekommen..
HAL 9000 Auf diesen Beitrag antworten »

Die Möglichkeit, mehrmals dieselbe Zahl zu ziehen, macht die exakte Berechnung zusätzlich schwierig.

Ich betrachte daher zunächst mal die Variante ohne Zurücklegen, wo das ja nicht passieren kann. Für sind die Varianten Ziehen von 5 Elementen mit/ohne Zurücklegen in der Wahrscheinlichkeitsbewertung asymptotisch gleich - und ich nehme ja an, dass es dir bei deinem Sortierproblem ohnehin erstmal auf große ankommt. Augenzwinkern


Nach der Vorrede nun zur Berechnung:

Rechnen wir der Einfachheit halber zunächst mit . Die drittgrößte Zahl darf dann die Werte annehmen Zwei andere müssen kleiner sein, die restlichen zwei der Fünferauswahl müssen größer sein.

Das ergibt Wahrscheinlichkeit



Mit CAS-Unterstützung führt das auf

für ,

d.h. für große liegt die mittlere der 5 Zahlen mit ca. 58% Wahrscheinlichkeit im mittleren Drittel des Zahlenbereichs.
tianstar Auf diesen Beitrag antworten »

Das ging doch etwas schnell Hammer .

n = 3m und [ m+1, 2m-1] sind verständlich.

Können wir einfach sagen 2 müssen größer und kleiner sein ohne auf Intervalle fest zu legen :/?

Und wir kommst du auf die Summenformen Hammer , ich stehe gerade auf dem Schlauch, sorry.

Danke, für deine Antwort erstmal !
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von tianstar
Können wir einfach sagen 2 müssen größer und kleiner sein ohne auf Intervalle fest zu legen :/?

Ich nenne die drittgrößte Zahl eben einfach mal . Damit dieses auch tatsächlich die drittgrößte der fünf Zahlen ist, müssen zwei andere der Fünferauswahl im Bereich liegen, und die restlichen zwei im Bereich .

Zur Erinnerung, ich betrachte Ziehen ohne Zurücklegen, also sind sämtliche fünf Zahlen voneinander verschieden. Zwei aus auswählen geht mit Möglichkeiten, entsprechend zwei aus auswählen mit Möglichkeiten, insgesamt also Möglichkeiten für die Auswahl der "begleitenden" vier Zahlen zur mittleren Zahl . Schließlich und endlich darf ja variieren im Bereich , daher die Summe.

Soweit zur Berechnung der Anzahl der günstigen Auswahlen. Für die Wahrscheinlichkeitsberechnung wird das ganze dividiert durch die Anzahl aller möglichen Fünferauswahlen aus , das sind .

Zur Kontrolle: Ohne die Forderung nach dem mittleren Drittel kann prinzipiell Werte von bis annehmen. Und tatsächlich ist dann auch

,

wie es auch sein sollte. Augenzwinkern



Zitat:
Original von tianstar
Und wir kommst du auf die Summenformen Hammer

Ich hab nur die Summenformel aufgestellt - deren Auswertung habe ich wie gesagt dem CAS überlassen.


Man kann sich dem ganzen für auch so nähern, dass man die Sache "verstetigt", d.h., fünf gleichmäßig stetig [0,1]-verteilte Zufallsgrößen nimmt und nach der Wahrscheinlichkeit fragt, dass die mittlere der fünf im Intervall liegt. Das Ergebnis dazu ist

,

in Übereinstimmung mit den "diskreten" Betrachtungen oben.
tianstar Auf diesen Beitrag antworten »

Ich danke dir viel viel mals !

Eine minimale Verständnisfrage bleibt.

Das erste n über k : ist k - 1 über 2 für k:= m + 1 dh es läuft doch von m bis 2m.

Also nicht von 1 bis k - 1. Aber die Intervalle sind ja gleich groß es macht also keinen unterschied ob man schreibt m - 1 über 2 oder wie in deinem fall k - 1 über 2 ?


Das mit dem verstetigen blende ich mal ganz dezent aus Prost .

Ich danke dir sehr!
 
 
HAL 9000 Auf diesen Beitrag antworten »

Ich verstehe deine Ausdrucksweise nicht, z.B. hier schon mal nicht

Zitat:
Original von tianstar
Das erste n über k : ist k - 1 über 2 für k:= m + 1 dh es läuft doch von m bis 2m.

von welchem es du redest. Bemühe dich doch bitte mal um klare exakte Ausdrucksweise.
tianstar Auf diesen Beitrag antworten »

Dein erstes n über k ( k - 1 über 2) läuft nicht von 1 bis k -1 sondern von m bis 2m - 1, oder ?

Ich gehe davon aus, dass das keinen Unterschied macht, weil die Intervalle 1 bis k - 1 ( sprich 1 bis m ) und m + 1 bis 2m gleich groß sein sollten.


mit "es" war die Summenfolge k = m + 1 gemeint
HAL 9000 Auf diesen Beitrag antworten »

Schreibe ich denn so undeutlich? Die Summe läuft nicht von bis , sondern von bis .

Und lass das bitte mit dem "n über k". Sowohl n als auch k haben hier ganz andere Bedeutungen, nirgendwo taucht hier ein "n über k" auf. Rede also von "Binomialkoeffizient", wenn du darauf abzielst - nur weil du den Binomialkoeffizient im Kontext "n über k" kennengelernt hast, heißt das nicht, alles und jeden Binomialkoeffizienten einfach als "n über k" zu bezeichnen, das ist vollkommen daneben. Und es ist in etwa so sinnvoll, wie jeden Deutschen "Fritz" und jeden Russen "Iwan" zu nennen. unglücklich


EDIT: So langsam drängt sich mir ein Verdacht auf. Kann es sein, dass du keine Ahnung hast, wie ein Summensymbol zu lesen ist? Anders kann ich mir deine schräg anmutenden Auslassungen nicht erklären. Nun gut, in "Pünktchenschreibweise" geschrieben ist das hier

.
tianstar Auf diesen Beitrag antworten »

Ich weis wie man ein Summenzeichen liest, danke. Die Aufgabe erschließt sich mir jedoch nicht vollständig, deshalb frage ich.

Mein Problem ist mehr der Binomialkoeffizient, wie du vielleicht schon gemerkt hast.
Ich denke ich habe dich mittlerweile verstanden und danke dir. Ich komme nicht aus der Mathematik, weshalb ich den Binomialkoeffizient nicht häufig über den Weg laufe.

Du legst k als eine Zahl fest, welche im mittleren Drittel des Arrays liegt. Ausgehend von k bestimmt der erste Binomialkoeffizient alle Möglichkeiten 2 kleinere Zahlen zu wählen und der zweite alle Möglichkeiten 2 größere Zahlen zu wählen. Die Möglichkeiten multiplizierst du und summierst die Ergebnisse für alle k, sodass du am Ende viele günstige Ereignisse durch alle Möglichen teilen kannst.

Ich habe den ersten Binomialkoeffizient anders interpretiert, da dort eben die Zahlen m bis 2m - 2 vorkommen. Irgendwie war in meinem Kopf verankert, dass dann dort nach Tupel in diesem Bereich gesucht wird und nicht immer von 1 bis zu dem Wert m bis 2m - 2.

Jetzt macht das schon mehr Sinn !

Nimm mir meine falschen Ausdrücke nicht zu übel, ich werde lernen mich in der Mathematik besser auszudrücken.
HAL 9000 Auf diesen Beitrag antworten »

Ich habe "n über k" hier deswegen so übel genommen, weil es nicht eine kleine verzeihbare kosmetische Ungenauigkeit war, sondern wegen der vollkommen anderen Bedeutung der Variablen n und k hier regelrecht zu total falschen Aussagen geführt hat.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »