Wann ist alles da?

JediMeister

Huhu, ich sehe grade mein Account funzt hier ja immer noch ô.O Nunja wie dem auch sei xD

Also letztens hat mich 'n Kollege angesprochen wegen einer Aufgabe ausm Physikbuch. Die lautete in etwa so (Vorraussetzung is ein Gitter 20x20 Felder):

Werfe 2 W20 Würfel und kreuze immer das Feld an, welches als Ergebnis rausgekommen ist. Nach durchschnittlich wieviele Versuchen sind alle Felder (bzw. alle 400 Möglichkeiten) angekreuzt?

Ich hatte nicht den geringsten Schimmer wie man das berechnen soll also habe ich einfach mal angefangen zu Würfeln (bzw. ich habs PHP machen lassen ^^), Quick & Dirty halt.

Der Quellcode dazu ist das hier falls es einer wissen will ^^

Code:

<?

function _wievieleversuche($param)
   {
      $array = array();
      
      for($i = 0; $i < $param; $i++)
      {
         $array[$i] = $i;
      }
      
      //print_r($array);
      
      $hilfsarray = array();
      
      $foo = 0;
      
      $lol = 0;
      
      while(count($hilfsarray) < $param)
      {
         $a = rand(0, $param - 1);
         
         if(in_array($a, $hilfsarray))
            $lol++;
         else
            $hilfsarray[$a] = $a;
         
         $foo++;
      }
      
      return $foo;
   }
   
   function _durchschnitt($menge, $param)
   {
      $foobar = 0;
      
      for($i = 0; $i < $menge; $i++)
      {
         $foobar += _wievieleversuche($param);
      }
      
      $erg = $foobar / $menge;
      
      return $erg;
   }
   
   $x = $_GET['moegl'];
   $y = $_GET['wieoft'];
   
   if($x > 500)
      $x = 500;
   
   if($y > 1500)
      $y = 1500;
   
   $omg = _durchschnitt($y, $x);

?>

Nun Die Frage, kann man das irgendwie berechnen? Ich meine: Man kann selbst nach 20.000 Versuchen immer noch ein Ergebnis nicht gewürfelt haben, die Wahrscheinlichkeit dafür wird zwar dank der Binominalverteilung immer geringer, aber dennoch möglich or?

MfG

Johannes

cool, das neue forum kann auch quellcode darstellen *freu*

TranceTip · **Registriert:** Do 25. Mär 2004, 14:09 **Beiträge:** 197

Klar kann man das ausrechnen und natürlich kann es beliebig lange dauern, bis alle 400 Felder das erste mal angekreuzt werden (es wird aber immer unwahrscheinlicher). Wenn man Glück hat, sind nach 400 Würfen alle Felder angekreuzt (auch sehr unwahrscheinlich).

Es handelt sich hierbei übrigens nicht um eine Binomialverteilung.

Dass es sich um ein Gitter handelt, ist irrelevant. Mit den beiden Würfeln werden lediglich Spalte und Zeile des Gitters bestimmt. Dasselbe Ergebnis ergibt sich, wenn man mit einem W400 würfelt und fragt, wie lange es durchschnittlich dauert, bis alle 400 Zahlen das erste Mal gefallen sind.

Natürlich dauert es weitaus mehr als 400 Würfe, weil immer mehr Felder bereits angekreuzt sind und somit ein Wurf immer öfter ein bereits angekreuztes Feld trifft.

Sei W(x) die Wahrscheinlichkeit, dass beim Würfeln ein noch nicht angekreuztes Feld getroffen wird unter der Voraussetzung, dass x-1 Felder bereits angekreuzt sind.

W(x) = (401-x)/400, denn

offensichtlich ist W(1) = 400/400 = 1, denn noch kein Feld ist angekreuzt.
W(2) = 399/400 (1 Feld ist bereits angekreuzt).
W(3) = 398/400 (2 Felder sind bereits angekreuzt).
...
W(400) = 1/400 (399 Felder sind bereits angekreuzt).

Wenn W(x) die Wahrscheinlichkeit für das Treffen eines freies Feld bei x-1 angekreuzten Feldern ist, dann ist 1/W(x) = 400/(401-x) die erwartete Anzahl der Versuche, bis man hierbei erfolgreich ist.

Für das erste Feld benötigt man im Durchschnitt 400/400 = 1 Wurf.
Für das zweite Feld benötigt man im Durchschnitt 400/399 = 1,00250 Würfe
Für das dritte Feld benötigt man im Durchschnitt 400/398 = 1,005025 Würfe
...
Für das 201. Feld benötigt man im Durchschnitt 400/200 = 2 Würfe (50% der Felder sind schon angekreuzt)
...
Für das 400. Feld benötigt man im Durchschnitt 400/1 = 400 Würfe

Also ist die Gesamtzahl der Würfe (bis alle Felder angekreuzt sind) die Summe der obigen erwarteten Würfe:

Summe(400/(400-i), i=0..399) = 2627,97187

Es hätte einem aber auch auffallen können, dass es sich hier um eine
harmonische Summe handelt:

Summe(400/(400-i), i=0..399) = 400 * Summe(1/(400-i), i=0..399) =
400 * Summe(1/i), i=1..400) = 400 * H(400)

Für H(n) (die n. harmonische Partialsumme) gibt es eine einfache, aber gute Näherung:

H(n) = ln(n) + gamma (gamma ist die Euler-Mascheroni-Konstante, ~0,5772156649)

Das Ergebnis ist mit der Näherung 400 * (ln(400) + gamma) = 2627,472084, also sehr
nah an der tatsächlichen Summe 2627,97187.

TranceTip · **Registriert:** Do 25. Mär 2004, 14:09 **Beiträge:** 197

Ich habe gerade gesehen, dass dieses Problem als das "Sammler-Problem" bezeichnet wird.

Siehe http://de.wikipedia.org/wiki/Sammelalbu ... er-Problem

xueron675 · **Registriert:** Do 22. Sep 2011, 09:28 **Beiträge:** 103

888xuerong-5:

Ugg Boots UK

witzeforum.de

Wann ist alles da?

Wer ist online?