piątek, 12 października 2012

Generator liczb losowych: rozkład Gaussa

Nie będę tu opisywał co to takiego generator liczb losowych. Zamierzam jedynie pokazać pewne jego praktyczne modyfikacje. W tym artykule chciałbym pokazać, jak generować liczbę losową o rozkładzie przypominającym rozkład Gaussa.

Idea nie jest skomplikowana. Jeśli ktoś kiedykolwiek bawił się w rzucanie kostkami (chociażby na lekcjach matematyki - pamiętam, że kiedyś w podstawówce robiliśmy coś takiego) to mógł zauważyć, że sumy oczek nie wypadają z jednakowym prawdopodobieństwem.

Słowo uzupełnienia. Okazuje się, że fakt, iż sumy oczek trzech lub więcej kostek przypominają rozkład normalny to nie przypadek. Z Wikipedii: "Jeśli jakaś wielkość jest sumą lub średnią bardzo wielu drobnych losowych czynników, to niezależnie od rozkładu każdego z tych czynników, jej rozkład będzie zbliżony do normalnego, stąd można go bardzo często zaobserwować w danych."

Rozkład prawdopodobieństwa dla jednej kostki.
Rozkład prawdopodobieństwa dla dwóch kostek.
Rozkład prawdopodobieństwa dla trzech kostek.

Dla większej ilości kostek kształt rozkładu nie zmienia się zbytnio, ulega tylko niejakiemu zawężeniu i wygładzeniu. Dla celów praktycznych wybór 3 kostek jest więc idealny (ew. można wybrać 2 kostki, jeśli komuś zależy, żeby skrajne wartości wypadały częściej).

Nie jest trudno wymyślić funkcję, która zwracała by nam zmienną losową o tego rodzaju kształcie.

int random(int m); //zwraca liczbę pseudolosową z zakresu 0 ÷ (m-1)

/*zwraca funkcję o rozkładzie podobnym do Gaussa z zakresu min ÷ max*/
int randomGauss(int min, int max)
{
    //zmienne pomocnicze służące do podziału zadanego zakresu
    int n123, n23, n1, n2, n3;

    n123=max-min;
    n1=n123/3;
    n23=n123-n1;
    n2=n23/2;
    n3=n23-n2;
    return (random(n1+1)+random(n2+1)+random(n3+1)+min);
}

Oprócz tego chciałbym tu jeszcze pokazać pewien wzór, który kiedyś sobie przepisałem z jakiejś książki o fraktalach (nie pamiętam jej tytułu, ale to była gruba księga o fraktalach i chaosie).

Jest to wzór na znormalizowaną Gaussowską zmienną losową D:

D = 1A 12n * ( Y1 + . . . + Yn ) - 3 n

gdzie:
  n - liczba rzutów
  Y1, ..., Yn - wyniki kolejnych rzutów
  A = maksymalna możliwa do wylosowania liczba (w językach C jest to stała RAND_MAX)

I to właściwie wszystko. Pozostaje tylko pytanko - po co to komu? Ano przydaje się do generowania naturalnego szumu. Rozkład w którym skrajne wartości zdarzają się rzadko, a typowe często jest bardzo naturalny i przy generowaniu czegokolwiek, co ma odzwierciedlać lub chociażby naśladować naturalne procesy, taki rozkład daje lepsze efekty (nie tylko wizualne).

„Spacer losowy” z rozkładem liniowym.
„Spacer losowy” z rozkładem Gaussa.

Na powyższych obrazkach widać porównanie przykładowych losowych krzywych utworzonych z wykorzystaniem różnych generatorów. Dolna krzywa wygląda bardziej naturalnie, z rzadszymi "skokami". Widać lepiej zaletę Gaussowskiego generatora, jeśli wyobrazimy sobie narysowane linie jako podłoże w grze Scorched Earth. Innym zastosowaniem, gdzie wybór Gaussowskiego generatora jest oczywisty to np. generowanie komputerowych krajobrazów.

Brak komentarzy:

Prześlij komentarz