100Münzwürfe - P(längste Sequenz aus K oder Z = 7)

20.01.2007, 18:23

Zellerli

Auf diesen Beitrag antworten »

100Münzwürfe - P(längste Sequenz aus K oder Z = 7)

Wie hoch ist die Wahrscheinlichkeit, dass die längste zusammenhängende Sequenz aus Zahl oder Kopf bei 100 Münzwürfen gleich n ist?
Meine Simulation ergibt die höchste Wahrscheinlichkeit für n = 7. Eine allgemeine Formel konnte ich jedoch noch nicht herleiten. Ich habe nur eine von n=51 bis n=100 herleiten können (total unnütz, denn wie oft kommt schon 51mal in folge Kopf bei 100 Würfen Augenzwinkern

Augenzwinkern

), aber unter 51 wird es schwer, weil dann die Kette mehrmals in der 100er-Sequenz vorkommen kann.
Danke für jegliche Hilfe.

20.01.2007, 20:51

AD

Auf diesen Beitrag antworten »

Nettes, ziemlich vertracktes Problem, aber rekursiv unter Computereinsatz könnte man es in den Griff kriegen, mit folgender Idee:

$\begin{eqnarray*} p(n,a) \end{eqnarray*}$ ... Wkt., dass bei $\begin{eqnarray*} n \end{eqnarray*}$ Würfen die längste Sequenz Länge $\begin{eqnarray*} a \end{eqnarray*}$ hat
$\begin{eqnarray*} q(n,a,b) \end{eqnarray*}$ ... Wkt., dass bei $\begin{eqnarray*} n \end{eqnarray*}$ Würfen die längste Sequenz Länge $\begin{eqnarray*} a \end{eqnarray*}$ hat und dass die Abschlusssequenz die Länge $\begin{eqnarray*} b \end{eqnarray*}$ hat.

Für $\begin{eqnarray*} n<a \end{eqnarray*}$ ist natürlich $\begin{eqnarray*} p(n,a)=q(n,a,b)=0 \end{eqnarray*}$ .

Offenbar ist dann $\begin{eqnarray*} p(n,a) = \sum_{b=1}^a ~ q(n,a,b) \end{eqnarray*}$ . Für beliebige $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ und $\begin{eqnarray*} 1\leq b\leq a\leq n \end{eqnarray*}$ gilt nun die Rekursion

$\begin{eqnarray*} q(n,a,b) = \frac{1}{2} \cdot \begin{cases} p(n-1,a) & \;\mbox{für}\; b=1\\ q(n-1,a,b-1) & \;\mbox{für}\; a>b\geq 2\\ (q(n-1,a,a-1)+q(n-1,a-1,a-1)) & \;\mbox{für}\; a=b\geq 2 \end{cases} \end{eqnarray*}$

Die Startbedingung ist offenbar

$\begin{eqnarray*} p(1,1)=q(1,1,1)=1 \end{eqnarray*}$ .

Ich hab's jetzt nur flüchtig durchdacht, aber es könnte klappen. Wer Denkfehler findet, bitte melden!

EDIT: Hab selber einen Schreibfehler gefunden - oben musste natürlich n<a statt n>a stehen!

20.01.2007, 22:04

AD

Auf diesen Beitrag antworten »

Hmm, ich denke es klappt. Mal ein paar Werte:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

p(100, 3) = 0.000285
p(100, 4) = 0.028026
p(100, 5) = 0.164869
p(100, 6) = 0.264484
p(100, 7) = 0.227570
p(100, 8) = 0.146209
p(100, 9) = 0.081899
p(100,10) = 0.042991
p(100,11) = 0.021878
p(100,12) = 0.010969
p(100,13) = 0.005460
p(100,14) = 0.002708
p(100,15) = 0.001341
p(100,16) = 0.000663
p(100,17) = 0.000328
p(100,18) = 0.000162
p(100,19) = 0.000080
p(100,20) = 0.000040
p(100,21) = 0.000020
p(100,22) = 0.000010
p(100,23) = 0.000005
p(100,24) = 0.000002
p(100,25) = 0.000001
p(100,26) = 0.000001

21.01.2007, 15:12

bil

Auf diesen Beitrag antworten »

super gelöst arthur. auf die idee mit der abschlusssequenz wäre ich wohl nicht gekommen. wie kommt man überhaupt auf so eine idee? Augenzwinkern

Augenzwinkern

aber bei einem punkt steh ich gerade auf dem schlauch und zwar:

$\begin{eqnarray*} q(n,a,a)=\frac{1}{2}\cdot(q(n-1,a,a-1)+q(n-1,a-1,a-1)) \end{eqnarray*}$ für $\begin{eqnarray*} a\geq 2 \end{eqnarray*}$

wieso wird dieser teil $\begin{eqnarray*} q(n-1,a,a-1) \end{eqnarray*}$ noch dazu addiert? das wäre doch die wahrscheinlichkeit das die längste sequenz bereits a ist und die abschlusssequenz a-1. verwirrt

verwirrt

gruss bil

edit: Hammer

Hammer

ok, schon erledigt. dumme frage gewesen. es ist ja durchaus möglich, dass die abschlusssequenz die länge a hat und davor auch eine andere sequenz der länge a existiert.

21.01.2007, 15:18

AD

Auf diesen Beitrag antworten »

Naja, das kann doch vorkommen, dass die längste Sequenz bereits vorher schon die Länge $\begin{eqnarray*} a \end{eqnarray*}$ hatte, und nun mit einer weiteren Sequenz erneut erreicht wird.

Im Fall $\begin{eqnarray*} a>\frac{n}{2} \end{eqnarray*}$ kann das natürlich nicht passieren, siehe Bemerkung von Zellerli für Sequenzen länger als 50.

Zitat:

Original von bil
auf die idee mit der abschlusssequenz wäre ich wohl nicht gekommen. wie kommt man überhaupt auf so eine idee? Augenzwinkern

Augenzwinkern

Ganz einfach: Für die Rekursion braucht man mehr Information, und die verschafft man sich durch diesen "erweiterten" Zustandsraum. Natürlich bedeutet das auch mehr Arbeit für den Iterationsschritt, da man diese erweiterte Information auch jetzt wieder für den nächsten Schritt berechnen muss. Aber nur so kommt man hier überhaupt in die Gänge - zumindest ist mir nichts anderes, besseres eingefallen. Augenzwinkern

Augenzwinkern

Dieses Prinzip ist ja auch aus so manchem Induktionsbeweis bekannt: Dass man "etwas mehr" beweist, weil so dann auch die Induktionsvoraussetzung mächtiger ist.

21.01.2007, 15:43

bil

Auf diesen Beitrag antworten »

wenn man sich die aufgabe bzw. lösung jetzt anschaut, wirkt sie leicht, aber das ist ja öfters so in der mathematik Augenzwinkern

Augenzwinkern

. selber drauf gekommen wäre ich, wie gesagt, wahrscheinlich nicht.
war aber wenigstens mal keine standardfrage, da habe ich auch noch was gelernt heute Augenzwinkern

Augenzwinkern

gruss bil

Anzeige

21.01.2007, 15:55

AD

Auf diesen Beitrag antworten »

Klingt schon irgendwie nach Standardfrage, wenn man sich mit solchen Binärsequenzen befasst. Aber komischerweise ist die mir nie so untergekommen. Augenzwinkern

Augenzwinkern

Übrigens ist der Rechenaufwand oben $\begin{eqnarray*} O(n^3) \end{eqnarray*}$ , für sehr große $\begin{eqnarray*} n \end{eqnarray*}$ wird's also auch eng, bis zum mittleren einstelligen Tausenderbereich kommt man noch ganz gut mit dem PC hin.

So intuitiv wird das Verteilungsmaximum in der Nähe von $\begin{eqnarray*} \log_2(n) \end{eqnarray*}$ liegen, aber das "ordentlich" zu formulieren und beweisen erfordert sicher noch genauere Überlegungen und Abschätzungen. smile

smile

21.01.2007, 18:00

Zellerli

Auf diesen Beitrag antworten »

WOW Super! Vielen Dank.
Also meine Simulation ergibt bei 1500mal 100Münzwürfen folgende Werte:

P(X=a) a
1 0
2 0
3 0,000662691
4 0,029821074
5 0,170974155
6 0,262425447
7 0,226640159
8 0,148442677
9 0,082173625
10 0,03843605
11 0,021868787
12 0,009940358
13 0,001988072
14 0,003313453
15 0

passt für die "wenigen" Durchgänge ja super auf die Berechnung. [edit] War wohl etwas unglücklich die erste Simulation mit dem höchsten Wert bei 7.[/edit] Rekursion ist mir (Abiturient) ein Fremdwort, also kann man es nicht mit Mitteln der Schulmathematik lösen. Wie gesagt, das FA-Thema ist ja auch die Erstellung der Simulation und der anschließende Vergleich mit den theoretischen Werten. Da mir die Methode nicht bekannt ist, weiß ich auch nicht, wie ich das genau formulieren muss... der Abschnitt lautet so (L ist die Zufallsgröße "längste Sequenz"):

Für die Wahrscheinlichkeit P(L=n) ergibt sich:
- Formel -

Was muss ich da dann jetzt hinschreiben? Mein Lehrer verlangte die Berechnung der Wahrscheinlichkeiten der Zufallsgrößen, aber mein Konzept verlangt, das Vorhandensein der Zufallsgröße L...

21.01.2007, 18:20

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Zellerli
Für die Wahrscheinlichkeit P(L=n) ergibt sich:
- Formel -

Was muss ich da dann jetzt hinschreiben?

Mit einer expliziten Formel kann ich dir nicht dienen. Wenn ich eine kennen würde, hätte ich das oben nicht so gemacht.

Soll jetzt nicht heißen, dass es keine gibt - musst du mal noch ein wenig recherchieren...

23.01.2007, 13:37

Zellerli

Auf diesen Beitrag antworten »

Jetzt muss ich doch nochmal fragen...
Hab mir jetzt ne Menge Text über Rekursion gegeben und leider nicht viel verstanden. Nach Rücksprache mit dem Lehrer, kamen er zum Entschluss: es genügt, wenn ich den Ansatz und was man wie in welches Programm eingeben muss in die FA schreibe. Da es Hochschulmathematik ist, verlangt er keine genaue Formel (zumal das Thema ohnehin die Theorie nicht in den Fokus stell).
Wenn du mir also sagen könntest, wie du zu dieser Tabelle kamst, wär ich sehr dankbar.
Sorry für den Aufwand, aber ich fand keinen anderen Weg.

23.01.2007, 13:56

AD

Auf diesen Beitrag antworten »

Das stand doch alles im Beitrag vorher! Alles ein wenig umsortiert, um es einem algorithmischen Ablauf nahe zu bringen:

Zitat:

Original von Arthur Dent
Die Startbedingung ist offenbar

$\begin{eqnarray*} p(1,1)=q(1,1,1)=1 \end{eqnarray*}$ .

Für beliebige $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ und $\begin{eqnarray*} 1\leq b\leq a\leq n \end{eqnarray*}$ gilt nun die Rekursion

$\begin{eqnarray*} q(n,a,b) = \frac{1}{2} \cdot \begin{cases} p(n-1,a) & \;\mbox{für}\; b=1\\ q(n-1,a,b-1) & \;\mbox{für}\; a>b\geq 2\\ (q(n-1,a,a-1)+q(n-1,a-1,a-1)) & \;\mbox{für}\; a=b\geq 2 \end{cases} \end{eqnarray*}$

$\begin{eqnarray*} p(n,a) = \sum_{b=1}^a ~ q(n,a,b) \end{eqnarray*}$ .

Für $\begin{eqnarray*} n<a \end{eqnarray*}$ ist natürlich $\begin{eqnarray*} p(n,a)=q(n,a,b)=0 \end{eqnarray*}$ .

23.01.2007, 16:16

Zellerli

Auf diesen Beitrag antworten »

den ansatz hab ich soweit begriffen, aber wo hast du es eingegeben? danke übrigens für die extra umformung

23.01.2007, 16:26

AD

Auf diesen Beitrag antworten »

In der Programmiersprache deiner Wahl! Da kannst du so gut wie alle nehmen, wo du mit Feldern operieren kannst.

24.01.2007, 12:23

Zellerli

Auf diesen Beitrag antworten »

ich kann nur HTML und gerade mal genug VB für excel... wenn mein lehrer mich nicht zu excel verdonnert hätte, hätte ich ohnehin die simulation direkt in VB geschrieben (und mir die entsprechenden kenntnisse angeeignet), da übersichtlicher und schneller.
hoffentlich stimmt wenigstens die schleife verwirrt

verwirrt

für n = 100:

for a = 1 to 100
for b = 1 to a

wenn ich da ma eh nicht total aufm holzweg bin... helpz!

24.01.2007, 12:28

AD

Auf diesen Beitrag antworten »

Du brauchst auf alle Fälle auch noch eine äußere n-Schleife, du musst dich ja vom Start n=1 bis zu 100 hocharbeiten!

Mit VB arbeite ich nicht. Als schnöder C-Code könnte das z.B. so aussehen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:

#define NMAX 100

double q[NMAX+1][NMAX+1][NMAX+1];
double p[NMAX+1][NMAX+1];

void main()
{
  int a, b, n;
  p[1][1]    = 1.0;
  q[1][1][1] = 1.0;

  for (n = 2; n <= NMAX; n++)
  {
    for (a = 1; a < n; a++)
    {
      q[n][a][1] = 0.5*p[n-1][a];
      p[n][a] = q[n][a][1];
      for (b = 2; b < a; b++)
      {
        q[n][a][b] = 0.5*q[n-1][a][b-1];
        p[n][a] += q[n][a][b];
      }
      if (a > 1)
      {
        q[n][a][a] = 0.5*(q[n-1][a][a-1]+q[n-1][a-1][a-1]);
        p[n][a] += q[n][a][a];
      }
    }
    for (b = 1; b < n; b++)
    {
      q[n][n][b] = 0.0;
    }
    if (n > 1)
    {
      q[n][n][n] = 0.5*q[n-1][n-1][n-1]);
    }
    p[n][n] = q[n][n][n];
  }
  /**** Ausgabe der Ergebnisse p[NMAX][a] für a=1..NMAX, lass ich hier weg. ****/
}

Geht natürlich alles effizienter - z.B. brauch man ja die "älteren" Zwischenergebnisse ja gar nicht - aber bei heutigen PC's kann man ja in gewissen Grenzen Speicherverschwendung betreiben. Big Laugh

Big Laugh

Der Fall a=n wurde bewusst aus der Berechnung ausgeklammert, da er auf Nullwerte q(n-1,n,b) bzw. p(n-1,n) zurückgreift, die so gar nicht gespeichert wurden.

24.01.2007, 12:48

Zellerli

Auf diesen Beitrag antworten »

paar operationen sind mir da geläufig. der rest ergibt sich. dass man n von 1 bis 100 setzen muss, erklärt einiges, unter anderem warum ich den einen teil bisher nicht verstanden hatte Hammer

Hammer

danke dir nochmal.

25.01.2007, 13:41

Zellerli

Auf diesen Beitrag antworten »

hab die FA endlich soweit fertig Augenzwinkern

Augenzwinkern

das C programm muss ich dann beilegen. wie schreib ich da noch eine ausgabesequenz für a=1 bis 100?

25.01.2007, 15:33

AD

Auf diesen Beitrag antworten »

Ich weiß nicht, ob es so besonders klug ist, jetzt plötzlich mit C zu anzufangen, ohne dass du die Sprache kennst - so hatte ich das mit meinem Beispiel-Code nicht gemeint!

Du hast doch auch die Simulationen durchgeführt - warum nimmst du nicht gleich diese Sprache, dann ist die Sache etwas einheitlicher! So schwer kann die Übertragung doch nicht sein.

25.01.2007, 22:31

Zellerli

Auf diesen Beitrag antworten »

Naja ich muss Excel benutzen, weil mein Lehrer nichts anderes checkt. Ich kann VB nicht sonderlich gut und viel Zeit hab ich auch nicht (übrigens für den Teil der FA auch nie viel eingeplant). Ich würde das Programm beilegen, die Werte so übernehmen (und daraus E, Var und sigma errechnen) und auch in der Simulation vorgeben.
Momentan seh ich keine andere Möglichkeit als das so zu übernehmen unglücklich

unglücklich

26.01.2007, 09:10

Zellerli

Auf diesen Beitrag antworten »

Mir bleibt dann jetzt nichts anderes übrig, als den Code so zu nehmen. Hmm aber is ohne Ausgabe.
Mit C will ich nicht anfangen, aber irgend ein Programm brauche ich und ich kenne keine Sprache gut genug, obendrein ist der Ansatz auch für mich ungewohnt und schwer.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »