Vergleiche i.-größter Zahlen

Neue Frage »

ArmerFrager Auf diesen Beitrag antworten »
Vergleiche i.-größter Zahlen
Hallo liebes Matheboard,

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. Augenzwinkern

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!
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. verwirrt

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. Augenzwinkern

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.


Zitat:
Original von ArmerFrager
Wenn das mit einer anderen Verteilung einfacher zu beantworten ist, bin ich da offen

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 . Augenzwinkern



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 .
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:
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

Zitat:
Original von ArmerFrager
Da ich nie eine Stochastikvorlesung hatte

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. verwirrt
ArmerFrager Auf diesen Beitrag antworten »

Oh, vielen Dank für die Blumen! smile

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?
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. Augenzwinkern

air
 
 
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:
  • er bekundet Interesse UND der andere Spieler bekundet kein Interesse
  • er UND der andere Spieler bekunden Interesse UND

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?
ArmerFrager Auf diesen Beitrag antworten »

Ahhhh, Implementierungsfehler! geschockt
Hier die (hoffentlich) korrekte Verteilung:
René Gruber Auf diesen Beitrag antworten »

Ich muss jetzt nochmal was nachfragen:

Zitat:
Original von ArmerFrager
Die beiden Spieler bekunden ihr Interesse aber nur für genau der Gegenstände.

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?

Zitat:
Original von ArmerFrager
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?

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
  • der og. hypergeometrischen Verteilung unterliegt, sowie
  • von die bedingte Verteilung unter der Bedingung bekannt ist, eben jene genannte Binomialverteilung.

Damit kann man doch schon mal was anfangen. Augenzwinkern


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. Augenzwinkern
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. Freude 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:
  • Man braucht mindestens Duelle, damit überhaupt sein kann (sonst kann man "nicht genug verlieren", um auf g zu kommen). Und man kann höchstens Duelle haben. Deswegen läuft von bis .
  • Wenn man Duelle hat, muss man davon verlieren, damit man auf das korrekte kommt. Und weil gilt, kommt man auf den hinteren Teil der Gesamtformel.
smile
Joah, ich denke das stimmt dann so, hehe. Zum Thema Vereinfachen: Ich habe mal Herrn Wolfram gefragt und der konnte sogar die Summe entfernen. Augenzwinkern 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. Augenzwinkern Aber spannende Fragen, finde ich!

Vielen Dank nochmal für deine Hilfe!

Registrierter ArmerFrager, der jetzt auch endlich seine Beiträge editieren kann.
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von ArmerFrager
Zum Thema Vereinfachen: Ich habe mal Herrn Wolfram gefragt und der konnte sogar die Summe entfernen. Augenzwinkern Weiß aber nicht, ob das so viel bringt.

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. Augenzwinkern

Aber danke für den Versuch, so scheint jetzt deutlicher zu sein, dass eine "schöne" Vereinfachung wohl gar nicht drin ist.
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.
Neue Frage »
Antworten »



Verwandte Themen

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