Vergleiche i.-größter Zahlen |
01.02.2011, 11:29 | ArmerFrager | Auf diesen Beitrag antworten » | ||||
Vergleiche i.-größter Zahlen ich habe hier das folgende Problem: Zwei Spieler ziehen jeweils n Zahlen gleichverteilt aus [0,1] und wählen dann jeweils die m größten davon aus. Nun werden die i.-größten Zahlen für 1<=i<=m paarweise miteinander verglichen. Wie groß ist die W'keit, dass der erste Spieler 0<=k<=m mal "gewinnt", also beim paarweisen Vergleich die größere Zahl als Spieler 2 hat? Das ist weder eine Schul- noch eine Übungsaufgabe, sondern taucht gerade bei meiner Arbeit auf. Da ich nie eine Stochastikvorlesung hatte, bin ich etwas hilflos. Könnt ihr mir vielleicht eine Starthilfe geben? Wenn das mit einer anderen Verteilung einfacher zu beantworten ist, bin ich da offen... weiß sowieso nicht genau, was da bei mir realistisch ist. Noch ein Beispiel für n=5 und k=3 und konkrete Werte: Spieler 1: 0.9 0.7 0.7 0.4 0.3 Spieler 2: 0.8 0.8 0.6 0.2 0.1 Spieler 1 gewinnt zweimal, da 0.9 > 0.8 und 0.7 > 0.6. Schonmal vielen Dank für eure Hilfe! |
||||||
01.02.2011, 12:14 | René Gruber | Auf diesen Beitrag antworten » | ||||
Zwar ist ziemlich schnell klar, dass Spieler 1 jeden einzelnen dieser Vergleiche mit Wahrscheinlichkeit für sich entscheidet (was zum Erwartungswert für die Anzahl der gewonnenen Vergleiche führt), allerdings sind diese Vergleiche nicht voneinander unabhängig. Alles, was ich (zusätzlich zum Erwartungswert) auf die Schnelle sagen kann ist, dass die Verteilung symmetrisch sein wird, also , aber das war dir vermutlich sowieso klar. Ich würd's an deiner Stelle auf alle Fälle mal mit Simulation versuchen, so ein paar Milliarden Durchläufe ergeben schon mal ein klareres Bild.
Es mag im ersten Moment verblüffen, aber tatsächlich spielt für die Beantwortung deiner Frage die Ausgangsverteilung keine Rolle, solange sie nur stetig ist! Und da tut es die Gleichverteilung auf genausogut wie jede andere stetige Verteilung auf . EDIT: Man kann das ganze zu folgender kombinatorischen Situation abstrahieren: Wir betrachten sämtliche Anordnungsmöglichkeiten von weißen und schwarzen (außer durch ihre Farbe) ununterscheidbaren Kugeln. Für jede Anordnungsmöglichkeit zählen wir nun, wie oft die -te weiße Kugel vor der -ten schwarzen Kugel liegt - das ist deine og. Anzahl . Noch anders formuliert, in Hinblick auf eine mögliche algorithmische Lösung: Geben die Positionen der weißen Kugeln in der Anordnung an, also , dann zählt die Anzahl der Indizes mit . |
||||||
01.02.2011, 14:02 | ArmerFrager | Auf diesen Beitrag antworten » | ||||
Hi René, vielen Dank schonmal für deine Antwort. Ich beschäftige mich noch weiter damit und melde mich später nochmal. Die Monte-Carlo Simulation habe ich schon gemacht, hier mal ein Ergebnis für n=100 und m=30: |
||||||
01.02.2011, 14:58 | René Gruber | Auf diesen Beitrag antworten » | ||||
Es ist wirklich mal erfrischend, dass jemand so gut vorbereitet und mit Elan sein Problem hier vorstellt, noch dazu angesichts dieser Aussage
Da hast du dir schon mal meinen Respekt verdient. Mal sehen, ob ich bei og. kombinatorischen Modell auch einer Formellösung näher komme, versprechen kann ich allerdings nichts: Es sieht ziemlich vertrackt aus. |
||||||
01.02.2011, 16:03 | ArmerFrager | Auf diesen Beitrag antworten » | ||||
Oh, vielen Dank für die Blumen! Ich habe in den letzten Stunden gemerkt, dass man Problem möglicherweise doch leicht anders gelagert ist, als oben beschrieben. Bin noch am Basteln. Die sauberste Lösung ist es dann ggf. einen neuen Thread zu eröffnen, und diesen hier nicht zu verwurschteln, oder? |
||||||
01.02.2011, 16:09 | Airblader | Auf diesen Beitrag antworten » | ||||
@ArmerFrager Nein, bleibe ruhig in diesem Thread. Es ist ja nicht verboten, dass sich etwas erst "entwickelt". Ein neuer Thread würde den Faden abreißen lassen. Im Übrigen auch meinen Respekt bzgl. deines Vorgehens. So manch ein Fragesteller könnte sich da eine Scheibe abschneiden. Gerade bei René sammelst du da natürlich Punkte. air |
||||||
Anzeige | ||||||
|
||||||
01.02.2011, 17:33 | ArmerFrager | Auf diesen Beitrag antworten » | ||||
Also, es ist tatsächlich noch ein bisschen anders, als ich zunächst dachte. Sorry für das Gehirnschmalz, was ihr schon investiert habt! :/ Es gibt eigentlich Spieler, aber bleiben wir hier zunächst ruhig mal bei . Weiterhin gibt es Gegenstände, die für die beiden Spieler von unterschiedlichem Interesse sind: und geben für Spieler 1 und 2 ihr Interesse an Gegenstand an. Die beiden Spieler bekunden ihr Interesse aber nur für genau der Gegenstände. Ein Spieler bekommt nun einen Gegenstand in zwei Fällen:
Das ganze habe ich auch mal durch die Simulation gejagt (wieder n=100, k=30), siehe Anhang. Was mir halt total Probleme macht, ist die Abhängigkeit der Ereignisse. Auch nur zu bestimmen, wie hoch die W'keit ist, dass Spieler 1 nichts bekommt, gelingt mir nicht, weil die Ereignisse " verliert" nicht unabhängig sind. Oder? |
||||||
01.02.2011, 20:36 | ArmerFrager | Auf diesen Beitrag antworten » | ||||
Ahhhh, Implementierungsfehler! Hier die (hoffentlich) korrekte Verteilung: |
||||||
02.02.2011, 16:33 | René Gruber | Auf diesen Beitrag antworten » | ||||
Ich muss jetzt nochmal was nachfragen:
Da du nichts weiter dazu gesagt hast, nehme ich an, dass die Interessenlage vollkommen gleichverteilt auf allen Auswahlmöglichkeiten ist, und zudem von Spieler zu Spieler unabhängig voneinander?
Benennen wir doch einfach mal die (zufällige) Anzahl der Gegenstände, für die sich beide zugleich interessieren, mit . Dann ist klar, dass sich beide Spieler jeweils für weitere Gegenstände interessieren, für die der andere kein Interesse zeigt, die ihnen also "kampflos" zufallen. Wie ist nun die Verteilung von ? Die ist hypergeometrisch, denn man kann das aus Perspektive von Spieler 2 als Auswahl von aus Elementen deuten, wobei sich letztere in zwei Gruppen unterteilen: die von Spieler 1 ausgewählten ( Stück) sowie die von Spieler 1 nicht ausgewählten ( Stück) Gegenstände. Demnach ist für . Für festes wiederum ist nun die Anzahl der in diesen "Duellen" gewonnenen Vergleiche binomialverteilt . Als zufällige Gesamtanzahl erhaltener Gegenstände für Spieler 1 (oder auch 2, ist ja symmetrisch) resultiert nun also , wobei
Damit kann man doch schon mal was anfangen. EDIT: Wenn ich das alles mal gut verrühre. dann müsste als Verteilungsgesetz für herauskommen. Ich bitte um kritische Hinterfragung, und noch mehr um eine mögliche Vereinfachung der Summe - am besten mit Eliminierung der Summation. |
||||||
02.02.2011, 23:17 | ArmerFrager | Auf diesen Beitrag antworten » | ||||
Hallo René, vielen Dank für deine ausführliche Antwort, das hat mir sehr geholfen. Ich denke ich konnte auch alles nachvollziehen, weil es so schön erklärt war. Beim Zusammensetzen am Ende habe ich allerdings noch etwas gebraucht. Um anderen das Leben vielleicht noch ein bisschen leichter zu machen, hier meine beiden wesentlichen Einsichten:
Joah, ich denke das stimmt dann so, hehe. Zum Thema Vereinfachen: Ich habe mal Herrn Wolfram gefragt und der konnte sogar die Summe entfernen. Weiß aber nicht, ob das so viel bringt. Da muss ich mir die hypergeometrische Funktion erst noch anschauen, die da verwendet wird. Noch zu deiner Frage: Wichtiger Punkt! Nach welcher Strategie wählen die Spieler die aus aus? Wenn sie möglichst viele Gegenstände bekommen wollen, wäre es wohl sinnvoll, die höchsten abzugeben. Da die Interessen und gleichverteilt und unabhängig sind, stimmt deine Annahme, soweit ich das überblicke. Was ich mich noch frage: Ist die Annahme über die Binomialverteilung dann korrekt? Ist die Chance, mit einem meiner besten einen seiner besten zu schlagen 0.5? Mittelt sich das irgendwie alles raus..? Das stimmt jedenfalls nur, wenn beide Spieler die gleiche Strategie fahren, oder? Wenn z.B. einer zufällige abgibt und der andere die besten, sind die Wahrscheinlichkeiten anders. Soweit meine Gedanken - für heute reicht's. Aber spannende Fragen, finde ich! Vielen Dank nochmal für deine Hilfe! Registrierter ArmerFrager, der jetzt auch endlich seine Beiträge editieren kann. |
||||||
03.02.2011, 07:29 | René Gruber | Auf diesen Beitrag antworten » | ||||
Da muss ich dir zustimmen, denn das dort auftauchende ist eine Reihe, deswegen sehe ich das gegenüber der Summe oben eher als Rückschritt. Aber danke für den Versuch, so scheint jetzt deutlicher zu sein, dass eine "schöne" Vereinfachung wohl gar nicht drin ist. |
||||||
03.02.2011, 11:16 | ArmerFrager | Auf diesen Beitrag antworten » | ||||
Wobei ich mich frage, ob man nicht noch vereinfachen kann. Es gibt da alle möglichen Transformationen, aber bisher bin ich nur auf gekommen, was auch nix bringt. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|