Losowanie elementów z zadanym rozkładem prawdopod.

0

Hej.

Dana jest tablica n elementów. Każdy element ma przypisaną jakąś wartość prawdopodobieństwa.
Potrzebuję wydajnego algorytmu wyboru losowego elementu zgodnie z tak określonym rozkladem prawdopodobieństa. Uwaga - pomiędzy losowaniami pewna niewielka liczba elementów (<< n) może zmienić drastycznie wartości swoich prawdopodobieństw. Algorytm powinien mieć jak najniższą złożoność zarówno losowania elementu, jak i aktualizacji stanu swoich struktur w przypadku zmiany żądanego prawdopodobieństwa wylosowania niektórych elementów. Jako złozoność algorytmu przyjmuje się złożoność "gorszej" z tych operacji.

Klasyczny algorytm z konstruowaniem dystrybuanty w tablicy ma złożoność O(n), ze wzgledu na złożoność operacji tworzenia dystrybuanty, mimo że samo losowanie da się zrobić w O(log n). Myślałem o czymś z drzewami, co powinno dać ostatecznie O(log n), ale implementacja nie mieści się w 10 linijkach, a nie mam duzo czasu, ani wysokiego priorytetu na ten algorytm. Zresztą w ostateczności O(n) ujdzie.

Czy istnieje jakiś prosty algorytm o lepszej złożoności, najlepiej wykorzystujący gotowe struktury danych dostępne w Javie? A może jest gdzieś gotowa biblioteka rozwiazująca ten problem?

0

Zmiana rozkładu gęstości prawdopodobieństwa, pozwala na przejście pomiędzy dwoma różnymi rozkładami w czasie O(1), pod warunkiem, że znamy oba rozkłady (dokładniej funkcje je opisujące) i ręcznie znajdziemy funkcję przejścia, czyli wynik:

g(y)=f(x(y))(dx/dy)

Można zatem pracować na rozkładzie płaskim, który z natury jest "szybki", a potem wynik przekształcać do pożądanego rozkładu.

0

Problem w tym, że rozkład jest dyskretny, a nie zadany funkcją gęstości prawdopodobieństwa, a tym bardziej jakimś "ładnym" wzorem. Wzór, który podałeś nie pasuje do tego przypadku.

BTW:

pod warunkiem, że znamy oba rozkłady (dokładniej funkcje je opisujące)

Tu w nawiasie naprawdę nie powinno byc przypadkiem "wzory je opisujące"? Wydaje mi się, że treść nawiasu jest tożsama z tym co napisałeś przed. Rozkład to JEST funkcja. Ale wzór funkcji to nie to samo co funkcja.
No i w związku z tym, nie jestem wcale pewien, że da się zrobić to w O(1) jeśli masz daną funkcję, ale nie masz zwięzłego wzoru a tablicę - tak jak jest w tym przypadku.

0

Funkcje (bardziej ogólne). Zresztą mam trochę naleciałości z wydziału fizyki...

Wracając do tematu. hm... Tak sobie myślę może generator losowy metodą v. Neumann, albo Butlera? Nie... też ciągły...

Opis generatora dyskretnego jest w 3.4:
http://www.im.pwr.wroc.pl/~misiorek/ms.pdf

Hm... muszę się jeszcze zastanowić i poszukać skryptu ze statystyki..

0

To zadanie można zrealizować metodą odwracania dystrybuanty z porządkowaniem prawdopodobieństw. Wątpię by istniała metoda szybsza. Bez porządkowania szybciej napiszesz dystrybuantę ale za to oczywiście średni czas losowania będzie dłuższy.

0

proponuję podejscie 'geometryczne'. dla każdego elementu i bierzesz patyk o dlugosci odpowiadjacej prawdopodobienstwu jego wylosowania p[i]. wszystkie patyki ukladasz jeden obok drugiego i z pewnwj odleglosci puszczasz kule do kregli. po ktorym patyku przejedzie - ten element zwracasz. ponizszy kod dziala wg tej idei. formalnie rzecz biorac sprowadza sie to do wspominanego juz odwracania dystrybuanty, lecz jest chyba latwiejsze do wyczucia.

function RandomElement(p:tab)
begin
  for i:=1 to length(p)-1 do
    p[i]:=p[i-1]+p[i]; //ukladanie patykow jeden obok drugiego
  los:=random*p[length(p)-1]; //losowy wskaznik patyka -'kula' 
  for i:=0 to length(p)-1 do
    if los<p[i] then // sprawdzenie po ktorym patyku przejechala 'kula'
      begin
        RandomElement:= i
        Exit
      end;
end;
0

To jest standardowa metoda, złożoność losowania O(n).
Ciekawsza wydaje się metoda von Neumanna - losowanie wprawdzie w O(n), ale z mniejszą stałą, natomiast jeśli zrobi się dodatkowe założenie, że rozkład jest "w miarę równomierny", to można uzyskać O(1). Niestety większość rozkładów, a zwłaszcza te, do których to potrzebuję nie są "w miarę równomierne".

1 użytkowników online, w tym zalogowanych: 0, gości: 1