Erwartungswert unterscheidbarer Ergebnisse beim Würfeln

Neue Frage »

Yakazan Auf diesen Beitrag antworten »
Erwartungswert unterscheidbarer Ergebnisse beim Würfeln
Meine Frage:
Ich habe einen k-seitigen Laplacewürfel, den ich n mal würfle. Ich möchte nun in Abhängigkeit von k und n ausrechnen, wie viele unterscheidbare Würfelseiten am Ende oben gelegen haben. Alle Seiten des Würfels sind paarweise verschieden. Eine Würfelseite kann mehrmals gewürfelt werden, wird aber nur als eine unterscheidbare Seite gezählt.

Beispiel: k=6; n=5. Ich würfle einen 6-seitigen Würfel 5 mal und erhalte die Augenzahlen 4, 3, 6, 4 und 1. Das sind 4 unterscheidbare Würfelseiten. Der Erwartungswert für k=6; n=5 wäre übrigens 3,5887. Im Mittel werden also bei 5 Würfen mit einem 6-seitigen Würfel dreieinhalb unterschiedliche Seiten pro Wurfsalve gewürfelt.

Für diese Rechnung suche ich nun eine allgemeine Formel, in die ich später n und k einsetzen kann. Ein Link auf den passenden Wikipediaartikel o.Ä. hilft auch. Ich hatte leider nichts dergleichen gefunden. Danke.

Meine Ideen:
Ich habe bereits emprisch folgende Werte ermittelt:

d(x): Entspricht der Menge der Ergebnisse, die x unterschiedliche Werte besitzen.
E(k; n): Der Erwartungswert.

für k = 2; n = 2
d(1) = 2
d(2) = 2
E(2; 2) = 1,5

für k = 2; n = 3
d(1) = 2
d(2) = 6
E(2; 3) = 1,75

für k = 2; n = 4
d(1) = 2
d(2) = 14
E(2; 4) = 1,875

für k = 2; n = 5
d(1) = 2
d(2) = 30
E(2; 5) = 1,9375

für k = 2; n = 6
d(1) = 2
d(2) = 62
E(2; 6) = 1,96875

-----

für k = 3; n = 2
d(1) = 3
d(2) = 6
E(3; 2) = 1,6667

für k = 3; n = 3
d(1) = 3
d(2) = 18
d(3) = 6
E(3; 3) = 2,1111

für k = 3; n = 4
d(1) = 3
d(2) = 42
d(3) = 36
E(3; 4) = 2,4074

für k = 3; n = 5
d(1) = 3
d(2) = 90
d(3) = 150
E(3; 5) = 2,6049

für k = 3; n = 6
d(1) = 3
d(2) = 186
d(3) = 540
E(3; 6) = 2,7366

-----

für k = 4; n = 2
d(1) = 4
d(2) = 12
E(4; 2) = 1,75

für k = 4; n = 3
d(1) = 4
d(2) = 36
d(3) = 24
E(4; 3) = 2,3125

für k = 4; n = 4
d(1) = 4
d(2) = 84
d(3) = 144
d(4) = 24
E(4; 4) = 2,7344

für k = 4; n = 5
d(1) = 4
d(2) = 180
d(3) = 600
d(4) = 240
E(4; 5) = 3,0508

für k = 4; n = 6
d(1) = 4
d(2) = 372
d(3) = 2160
d(4) = 1560
E(4; 6) = 3,2881

-----

für k = 5; n = 2
d(1) = 5
d(2) = 20
E(5; 2) = 1,8

für k = 5; n = 3
d(1) = 5
d(2) = 60
d(3) = 60
E(5; 3) = 2,44

für k = 5; n = 4
d(1) = 5
d(2) = 140
d(3) = 360
d(4) = 120
E(5; 4) = 2,952

für k = 5; n = 5
d(1) = 5
d(2) = 300
d(3) = 1500
d(4) = 1200
d(5) = 120
E(5; 5) = 3,3616

für k = 5; n = 6
d(1) = 5
d(2) = 620
d(3) = 5400
d(4) = 7800
d(5) = 1800
E(5; 6) = 3,68928

-----

für k = 6; n = 2
d(1) = 6
d(2) = 30
E(6; 2) = (1*6 + 2*30) / 6^2 = 1,8333

für k = 6; n = 3
d(1) = 6
d(2) = 90
d(3) = 120
E(6; 3) = (1*6 + 2*90 + 3*120) / 6^3 = 2,5278

für k = 6; n = 4
d(1) = 6
d(2) = 210
d(3) = 720
d(4) = 360
E(6; 4) = 3,1065

für k = 6; n = 5
d(1) = 6
d(2) = 450
d(3) = 3000
d(4) = 3600
d(5) = 720
E(6; 5) = 3,5887

für k = 6; n = 6
d(1) = 6
d(2) = 930
d(3) = 10800
d(4) = 23400
d(5) = 10800
d(6) = 720
E(6; 6) = 3,9906

-----

Außerdem habe ich festgestellt, wenn n = k ist, dann entspricht dieses Problem dem Gesetz der kleinen Zahlen.

Als Formelansätze habe ich bisher:

d(x) = k!/(k-x)!*z

z ist ein ganzzahliger Faktor, mit dem multipliziert man d(x) erhält. Bei x=1 und x=k ist z immer 1. Ansonsten lässt sich z (zumindest, wenn k<n ist, für k>n hab ichs noch nicht getestet) durch folgenden Algorithmus beschreiben:

z=0;
y=n-z;
For i_1=1 to x do
For i_2=p_1 to x do
...
For i_y=p_(y-1) to x do
z = z + i_1 * i_2 * ... * i_y;
EndFor
...
EndFor
EndFor
Return z;

Ich find derzeit keine Lösung, z zu einer vernünftigen Formel zusammenzubauen und finde auch keinen anderen Ansatz, an das Problem ranzugehen. Ich nehme mal an, ich hab es mir wieder viel zu umständlich gemacht.
Dopap Auf diesen Beitrag antworten »

zumindest eine Umschreibung ist denkbar:

wenn k>n ist, läuft das auf die Wkt von Pokerblättern hinaus. Beispiel k=6,n=5

Strasse: 5 Verschiedene
Full House: 2 Verschiedene
2 Paare: 3 Verschiedene
Drilling : 3 Verschiedene
Vierling: 2 Verschiedene
Fünfling: 1 Verschiedene

dazu gibt es Formeln zur Wkt. Ob die aber für k<n gelten ?

Sollte auch nur eine Anregung sein. smile
Yakazan Auf diesen Beitrag antworten »

Ein kleiner Nachtrag:

ich hatte mir auch einen Baum aufgemalt und bin die verschiedenen Zweige abgelaufen. Daraus hatte ich die Schlussfolgerungen gezogen, die im vorigen Beitrag unten stehen. Hier sind die Berechnungen für k=6; n=4, als Beispiel.

p(x) = Eintrittswahrscheinlichkeit für x verschiedene Seiten beim Würfeln

p(1) = 6/6 * 1/6 * 1/6 * 1/6
= (6!/5! * 1*1*1) / 6^4
= 6 / 6^4

p(2) = 6/6 * 1/6 * 1/6 * 5/6
+ 6/6 * 1/6 * 5/6 * 2/6
+ 6/6 * 5/6 * 2/6 * 2/6
= (6!/4! * (1*1 + 1*2 + 2*2)) / 6^4
= 210 / 6^4

p(3) = 6/6 * 1/6 * 5/6 * 4/6
+ 6/6 * 5/6 * 2/6 * 4/6
+ 6/6 * 5/6 * 4/6 * 3/6
= (6!/3! * (1 + 2 + 3)) / 6^4
= 720 / 6^4

p(4) = 6/6 * 5/6 * 4/6 * 3/6
= (6!/2!) / 6^4
= 360 / 6^4

p(1) + p(2) + p(3) + p(4) = 1
1*p(1) + 2*p(2) + 3*p(3) + 4*p(4) = 3,1065 = E(6; 4)

-----

Hier ist dann noch ein Beispiel, wie die empirischen Daten bei mir für k=2; n=4 aussehen und wie hier der berechnete Erwartungswert zustande kommt.

1 1 1 1 - 1 verschiedene Seite
1 1 1 2 - 2 verschiedene Seiten
1 1 1 3 - 2 verschiedene Seiten
1 1 2 1 - 2 verschiedene Seiten
1 1 2 2 - 2 verschiedene Seiten
1 1 2 3 - 3 verschiedene Seiten
1 1 3 1 - 2 verschiedene Seiten
1 1 3 2 - 3 verschiedene Seiten
1 1 3 3 - 2 verschiedene Seiten
1 2 1 1 - 2 verschiedene Seiten
1 2 1 2 - 2 verschiedene Seiten
1 2 1 3 - 3 verschiedene Seiten
1 2 2 1 - 2 verschiedene Seiten
1 2 2 2 - 2 verschiedene Seiten
1 2 2 3 - 3 verschiedene Seiten
1 2 3 1 - 3 verschiedene Seiten
1 2 3 2 - 3 verschiedene Seiten
1 2 3 3 - 3 verschiedene Seiten
1 3 1 1 - 2 verschiedene Seiten
1 3 1 2 - 3 verschiedene Seiten
1 3 1 3 - 2 verschiedene Seiten
1 3 2 1 - 3 verschiedene Seiten
1 3 2 2 - 3 verschiedene Seiten
1 3 2 3 - 3 verschiedene Seiten
1 3 3 1 - 2 verschiedene Seiten
1 3 3 2 - 3 verschiedene Seiten
1 3 3 3 - 2 verschiedene Seiten
2 1 1 1 - 2 verschiedene Seiten
2 1 1 2 - 2 verschiedene Seiten
2 1 1 3 - 3 verschiedene Seiten
2 1 2 1 - 2 verschiedene Seiten
2 1 2 2 - 2 verschiedene Seiten
2 1 2 3 - 3 verschiedene Seiten
2 1 3 1 - 3 verschiedene Seiten
2 1 3 2 - 3 verschiedene Seiten
2 1 3 3 - 3 verschiedene Seiten
2 2 1 1 - 2 verschiedene Seiten
2 2 1 2 - 2 verschiedene Seiten
2 2 1 3 - 3 verschiedene Seiten
2 2 2 1 - 2 verschiedene Seiten
2 2 2 2 - 1 verschiedene Seite
2 2 2 3 - 2 verschiedene Seiten
2 2 3 1 - 3 verschiedene Seiten
2 2 3 2 - 2 verschiedene Seiten
2 2 3 3 - 2 verschiedene Seiten
2 3 1 1 - 3 verschiedene Seiten
2 3 1 2 - 3 verschiedene Seiten
2 3 1 3 - 3 verschiedene Seiten
2 3 2 1 - 3 verschiedene Seiten
2 3 2 2 - 2 verschiedene Seiten
2 3 2 3 - 2 verschiedene Seiten
2 3 3 1 - 3 verschiedene Seiten
2 3 3 2 - 2 verschiedene Seiten
2 3 3 3 - 2 verschiedene Seiten
3 1 1 1 - 2 verschiedene Seiten
3 1 1 2 - 3 verschiedene Seiten
3 1 1 3 - 2 verschiedene Seiten
3 1 2 1 - 3 verschiedene Seiten
3 1 2 2 - 3 verschiedene Seiten
3 1 2 3 - 3 verschiedene Seiten
3 1 3 1 - 2 verschiedene Seiten
3 1 3 2 - 3 verschiedene Seiten
3 1 3 3 - 2 verschiedene Seiten
3 2 1 1 - 3 verschiedene Seiten
3 2 1 2 - 3 verschiedene Seiten
3 2 1 3 - 3 verschiedene Seiten
3 2 2 1 - 3 verschiedene Seiten
3 2 2 2 - 2 verschiedene Seiten
3 2 2 3 - 2 verschiedene Seiten
3 2 3 1 - 3 verschiedene Seiten
3 2 3 2 - 2 verschiedene Seiten
3 2 3 3 - 2 verschiedene Seiten
3 3 1 1 - 2 verschiedene Seiten
3 3 1 2 - 3 verschiedene Seiten
3 3 1 3 - 2 verschiedene Seiten
3 3 2 1 - 3 verschiedene Seiten
3 3 2 2 - 2 verschiedene Seiten
3 3 2 3 - 2 verschiedene Seiten
3 3 3 1 - 2 verschiedene Seiten
3 3 3 2 - 2 verschiedene Seiten
3 3 3 3 - 1 verschiedene Seite

d(1) = 3
d(2) = 42
d(3) = 36

E(3; 4) = 1*3/3^4 + 2*42/3^4 + 3*36/3^4
= 2,4074


p(1) = 3/3 * 1/3 * 1/3 * 1/3
= (3!/2! * 1*1*1)/3^4
= 3/3^4

p(2) = 3/3 * 1/3 * 1/3 * 2/3
+ 3/3 * 1/3 * 2/3 * 2/3
+ 3/3 * 2/3 * 2/3 * 2/3
= (3!/1! * (1*1 + 1*2 + 2*2))/3^4
= 42/3^4

p(3) = 3/3 * 1/3 * 2/3 * 1/3
+ 3/3 * 2/3 * 2/3 * 1/3
+ 3/3 * 2/3 * 1/3 * 3/3
= (3!/0! * (1+2+3))/3^4
= 36/3^4

E(3; 4) = 1*p(1) + 2*p(2) + 3*p(3)
= 1*3/3^4 + 2*42/3^4 + 3*36/3^4
= 2,4074


-----

Auf Poker bin ich noch nicht gekommen, aber ich hatte mir schon Kniffel angeschaut, da ich annahm aus den Formeln für die Wahrscheinlichkeit für Päsche vielleicht was für mich ableiten zu können. Leider hab ich nichts passendes gefunden.
Beim Poker werden die Karten nicht zurückgelegt, fällt mir gerade auf. Beim Würfel habe ich jedes mal die gleiche Wahrscheinlichkeit eine bestimmte Seite zu würfeln. Beim Poker ändert sich die Wahrscheinlichkeit eine Karte zu ziehen mit jeder gezogenen Karte. Poker eignet sich als Vergleich also glaub ich nicht so gut.
Dopap Auf diesen Beitrag antworten »

ich meinte selbstredend Poker mit Würfeln. Nicht Kartenpoker.

Hintergrund: beim Testen von Zufallszahlen wird auch dieser "Pokertest" verwendet.
Yakazan Auf diesen Beitrag antworten »

Es gibt Poker mit Würfeln? Ich kenn das nur mit Karten. Muss ich wohl mal googlen.
Dopap Auf diesen Beitrag antworten »

Zitat:
Original von Yakazan
Es gibt Poker mit Würfeln? ...


nein, nicht wirklich, es ist nur eine sinngemässe Übertragung der Ausfälle auf Würfel
 
 
Yakazan Auf diesen Beitrag antworten »

Ich hab nunmal die Wikipediaseite de.wikipedia.org/wiki/W%C3%BCrfelpoker#Die_Kombinationen mit den Werten verglichen, die ich als Ergebnisse raus hatte.

Meins:
für k = 6; n = 5
d(1) = 6
d(2) = 450
d(3) = 3000
d(4) = 3600
d(5) = 720

Wikipedia:
Five of a kind (AAAAA) = 6 = d(1)
Passt

Four of a kind (AAAAB) = 150
Full house (AAABB) = 300
150 + 300 = 450 = d(2)
Passt

Three of a kind (AAABC) = 1.200
Two pairs (AABBC) = 1.800
1200 + 1800 = 3000 = d(3)
Passt

One pair (AABCD) = 3.600 = d(4)
Passt

Straight (ABCDE) = 240
Runt (ABCDE) = 480
240 + 480 = 720 = d(5)
Passt


Das Problem lässt sich tatsächlich in die Wahrscheinlichkeiten vom Würfelpoker übertragen. Ich werd mir mal die Formeln dort genauer anschauen und gucken, ob ich damit weiterkomme.

Danke smile
Dopap Auf diesen Beitrag antworten »

ich versuche immer zu helfen, auch wenn ich manchmal danebenliege.

Ich seh' nur das Problem: die Pokerformeln sind mehr auf k>n , also weniger Würfel wie "Würfelflächen" zugeschnitten. Also Vorsicht.
Yakazan Auf diesen Beitrag antworten »

Für k=6; n=5 gilt:







So sieht das nun zusammengesammelt bei mir aus. Darin suche ich nach einem System und habe so halb eins gefunden (was leider nicht gerade effizient ist). Ich kann mir die 1/2 bei d(3) nicht herleiten. Ich weiß, dass sie richtig ist, ich weiß aber nicht, warum. Ebenso wundert mich, dass bei d(5) kein am Anfang steht. Das passt derzeit auch noch nicht in mein System rein. Ideen, wie man das ordnen könnte?
Dopap Auf diesen Beitrag antworten »

ich kenn die Formeln aus:

Arthur Engel: Wahrscheinlichkeitsrechnung und Statistik : Ernst Klett Verlag Stuttgart 1973

gewisse Schemen sind erkennbar, trotzdem muss jeder Einzelfall genau geprüft werden.

Eine globale formale Formel konnte ich dabei nicht erkennen.

Deine Werte kann ich momentan nicht mehr überprüfen.
Yakazan Auf diesen Beitrag antworten »




























Ich bin mir bei dem, was ich hier zusammengeschustert hab nicht sonderlich sicher (ich werd langsam müde), aber immerhin wird es so langsam so halbwegs systematisch.

Zitat:
Original von Dopap
gewisse Schemen sind erkennbar, trotzdem muss jeder Einzelfall genau geprüft werden.

Eine globale formale Formel konnte ich dabei nicht erkennen.


Naja, das ist genau mein Problem. Ich brauche diese Formel, um den Speicherplatzbedarf einer Datenbank zu optimieren. Ich habe da zwei Designs, die ich gegeneinander abwägen möchte. Dabei wird k zwischen 20 und 100 liegen und n zwischen 10 und 1000. Da möchte ich einige Fälle durchtesten. Für die kleinen Zahlen, mit denen ich bisher bastel lassen sich die Formeln noch händisch erstellen. Bei den größeren geht das nur mit ziemlich viel Aufwand. Deshalb ist das, was ich mir hier zusammenbaue bisher eher nutzlos in der Praxis, weil ich die Formeln nicht computergeneriert erzeugen kann. Ich müsste zum Schluss im Idealfall eine Formel nach einem festen System haben, in die ich nur noch n und k einzusetzen brauche.

Wüsste jemand einen anderen Ansatz, mit dem ich möglicherweise direkt den Erwartungswert berechnen kann, ohne den Umweg über die Zwischenwerte d(x)?

Dopap, danke für die Hilfe bisher. Ohne dich wäre ich wahrscheinlich noch nicht so weit gekommen, wie ich inzwischen bin. Warum ist es bei dir 6 Uhr?
Dopap Auf diesen Beitrag antworten »

Zitat:
Original von Yakazan
[...] Ich müsste zum Schluss im Idealfall eine Formel nach einem festen System haben, in die ich nur noch n und k einzusetzen brauche.
Wüsste jemand einen anderen Ansatz, mit dem ich möglicherweise direkt den Erwartungswert berechnen kann, ohne den Umweg über die Zwischenwerte d(x)?


#1 für eine solche Frage ist : HAL 9000

Zitat:


Dopap, danke für die Hilfe bisher. Ohne dich wäre ich wahrscheinlich noch nicht so weit gekommen, wie ich inzwischen bin. Warum ist es bei dir 6 Uhr?


Wie verwirrt , muss ein Tippfehler gewesen sein. Augenzwinkern
Yakazan Auf diesen Beitrag antworten »

dann setz ich lieber auf #2. HAL 9000, vorrausgesetzt wir reden über das Gleiche, hat die dumme Angewohnheit einen umbringen zu wollen, wenn man behauptet er hätte sich verrechnet Augenzwinkern
Yakazan Auf diesen Beitrag antworten »

Hat jemand eine neue Idee für mich?
Yakazan Auf diesen Beitrag antworten »

Gelöst smile

Ich hab wieder die Erwartungswerte ermittelt, indem ich alle möglichen Kombinaktionen für die verschiedenen Instanzen von n und k aufgeschrieben haben und das kam in eine Tabelle. Dort ließ sich dann gut sehen, dass die Zahlen irgendwie zusammenhängen müssen. Als Ergebnisformel habe ich nun folgendes raus:

k = Anzahl der Seiten des Würfels
n = Anzahl der Würfe
E(k; n) = Erwartungswert der Anzahl der unterschiedlichen Seiten, die ich mit einem k-seitigen Würfel nach n-Seiten im Durchschnitt werfen werde.



Die Formel hab ich anschließend nochmal mit einigen empirisch ermittelten Zahlen durchgetestet und sie scheint zu stimmen. Einen formalen Beweis für die Richtigkeit habe ich aber nicht.
Yakazan Auf diesen Beitrag antworten »

Ich hab nun nochmal geschaut, ob die Formel kürzbar ist und nun folgende Formel erhalten:

k = Anzahl der Seiten des Würfels
n = Anzahl der Würfe
E(k; n) = Erwartungswert der Anzahl der unterschiedlichen Seiten, die ich mit einem k-seitigen Würfel nach n-Seiten im Durchschnitt werfen werde.



bzw.

Neue Frage »
Antworten »



Verwandte Themen

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