Algorytm prawdopodobieństwa wykonania pętli nad losowo uporządkowaną tablicą

Question

Problem jest dość prosty, jak sądzę, patrząc na kod. Mam randomizowaną tablicę (tablica musi być randomizowana, jakiś kod został wykluczony, ponieważ nie odnosi się do rzeczywistego problemu, ale wymaga randomizacji). Dla każdego elementu w tablicy istnieje indeks "prawdopodobieństwa" (opisany tutaj jako sama wartość, w $rules), który ma na celu wskazanie, że jeśli spełnione są inne warunki (które są tutaj usuwane ze względu na brak trafności) prawdopodobieństwo, że element tablicy będzie „wyzwalane” (w tym przypadku, że wynik elementu tablicy będzie zwiększać się przez 1)

Rozważmy kod:

<?php 
    // Taken from php.net/shuffle user notes 
    // Shuffles an array order for the sake of foreach while maintaining 
    // key => value associations 
    function shuffle_assoc(&$array) { 
    $keys = array_keys($array); 
    shuffle($keys); 
    foreach($keys as $key) { 
     $new[$key] = $array[$key]; 
    } 
    return $new; 
    } 

    $i = 1000000; // How many tests to perform 

    // This is my rule list. Each key is a simple color 
    // and each value is a probability represented as a percent 
    $rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

    // Initialize the scores array with all 0's 
    // The "outs" will be used when the probability does not 
    // occur in any of the rules 
    $scores = array('outs' => 0); 
    foreach($rules as $k => $v) { 
    $scores[$k] = 0; 
    } 

    $count = count($rules); 

    for($x = 0; $x < $i; $x++) { 
    $rules = shuffle_assoc($rules); 

    foreach($rules as $k => $probability) { 
     $rand = mt_rand(1,100); 
     //$probability = ??; I've tried applying many different operations here to "correct" the probability 

     if($rand > $probability) { 
     continue; 
     } else { 
     $scores[$k]++; 
     continue 2; 
     } 
    } 
    $scores['outs']++; 
    } 


    foreach($scores as $k => $v) { 
    echo "$k: " . (($v/$i)*100) . "% ($v/$i)\n"; 
    } 

?> 

oczekiwany wynik (pseudo). Uwaga procenty odpowiadają wartościom $rules

outs: less than 1% (.../1000000) 
black: 20% (.../1000000) 
white: 10% (.../1000000) 
red: 40% (.../1000000) 
green: 5% (.../1000000) 
blue: 25% (.../1000000) 

Przykâadowa:

outs: 30.7128% (307128/1000000) 
black: 13.2114% (132114/1000000) 
white: 6.3381% (63381/1000000) 
red: 29.5247% (295247/1000000) 
green: 3.1585% (31585/1000000) 
blue: 17.0545% (170545/1000000) 

Czego próbowałem & przesłankach:

• Jak widać, w obrębie pętli I skomentowałem sekcję $probability = ??, w której wypróbowałem różne oczywiste metody obliczania rzeczywistego prawdopodobieństwa użycia element, w tym gra z $count (liczba reguł), dlatego ta zmienna istnieje i nie jest używana.

• Nie musi to być dokładnie oczywiste, ale najlepiej ma stabilne wyniki przy mniejszym zestawie liczb (np. 1000 powtórzeń).

• Może być dość rozmyte. Wariancja +/- 5% nie zaszkodziłaby moim uczuciom, szczególnie w mniejszej liczbie iteracji, rozumiem, że tu gra duża teoria liczb.

• Liczba outsów nie jest duża, o ile wynoszą mniej niż 1% -2%. Próbowałem również wyeliminować outs przy użyciu różnych metod, aby zobaczyć, czy same outy były przekrzywione, i co ciekawe, gdy zrobiłem to przy jednej okazji, dostałem 20% podział na całym (to jest nawet).

• Ponadto na „out”, udało mi się dostać całkiem blisko do prawidłowego split z bardzo małymi outów przez zasadzie brute-zmuszając „numery” prawdopodobieństwa (czyli wartości $rules) począwszy od 100 do tyłu , ale nigdy nie udało mi się znaleźć precyzyjnej, optymalnej metody. Za każdym razem zbliżałem się do wyniku jednego koloru, który skosiłby inne kolory na małej, ale zauważalnej skali. Nie było łatwej do zrozumienia korelacji w tych liczbach i były pozornie przypadkowe, chociaż jest oczywiste, że wyniki dobrze grają z prawdopodobieństwem vs duże liczby.

Proszę mi powiedzieć, że istnieje dokładny sposób obliczenia tego. To doprowadza mnie do szału.

Edit: Mam ostateczna wersja mojego kodu, z pomocą dwóch odpowiedzi poniżej, że robi to bez potrzeby znajomości procentowe prawdopodobieństwa przed rozpoczęciem pętli i bez dodatkowych lub zagnieżdżonych pętli (Właśnie tego potrzebowałem, wydaje mi się, że powinienem być bardziej bezpośredni w tej części). W znaczeniu każdej iteracji można dynamicznie podnosić prawdopodobieństwo w oparciu o te specyficzne właściwości iteracji.Wszystkie odpowiedzi tutaj były bezcenne, oto moja wersja ostatniego kodu: http://pastebin.com/eB3TVP1E

Answer 1

pomysł Jacka zaimplementowane w kodzie (jeżeli suma prawdopodobieństw wynosi> 100 to nie zadziała):

php fiddle

<?php 
    // Taken from php.net/shuffle user notes 
    // Shuffles an array order for the sake of foreach while maintaining 
    // key => value associations 
    function shuffle_assoc(&$array) { 
    $keys = array_keys($array); 
    shuffle($keys); 
    foreach($keys as $key) { 
     $new[$key] = $array[$key]; 
    } 
    return $new; 
    } 

    $i = 1000000; // How many tests to perform 

    // This is my rule list. Each key is a simple color 
    // and each value is a probability represented as a percent 
    $rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

    // Initialize the scores array with all 0's 
    // The "outs" will be used when the probability does not 
    // occur in any of the rules 
    $scores = array('outs' => 0); 
    foreach($rules as $k => $v) { 
    $scores[$k] = 0; 
    } 

    $count = count($rules); 
//$limits is what Jack called $rules_norm 
$limits=array(); 
$limit=0; 
foreach($rules as $k=>$v) 
{ 
    $limit+=$v; 
    $limits[$k]=$limit; 
} 
    for($x = 0; $x < $i; $x++) { 
     $rand = mt_rand(1,100); 
foreach($limits as $k=>$v) 
{ 
    if($v>=$rand) 
    { 
     $scores[$k]++; 
     continue(2); 
    } 

} 
    $scores['outs']++; 
    } 


    foreach($scores as $k => $v) { 
    echo "$k: " . (($v/$i)*100) . "% ($v/$i)\n"; 
    } 

?> 

Answer 2

Wystarczy znormalizować wyniki, zebrać je i gotowe.

Chodzi mi o to:

• suma wszystkich prawdopodobieństw podane dla każdego elementu tablicy, aby uzyskać całkowitą (co jest 100 w Twoim przypadku, ale to łatwo uogólnić)
• podzielić każdy prawdopodobieństwo sumy

Tak na przykład:

$rules = array(
    'black' => 20, 
    'white' => 10, 
    'red' => 40, 
    'green' => 5, 
    'blue' => 25, 
); 

zostaną znormalizowane do:

$rules_norm = array(
    'black' => 0.2, 
    'white' => 0.1, 
    'red' => 0.4, 
    'green' => 0.05, 
    'blue' => 0.25, 
); 

• teraz gromadzić wynik tak, że dla każdego elementu w $rules_norm obliczyć sumę wszystkich poprzednich elementów plus bieżącej.

Więc:

$rules_norm = array(
    'black' => 0.2, 
    'white' => 0.3, 
    'red' => 0.7, 
    'green' => 0.75, 
    'blue' => 1.0, 
); 

Teraz to można po prostu wydobyć losową liczbę zmiennoprzecinkową w zakresie [0,1) i wybrać, które elementy są zwiększane w zależności od wyniku: aby podwyższyć wynik jednego elementu po prostu zacząć od pierwsza w tablicy i przyrost jeden taki, że $rand > $rules_norm[k]