Jak wdrożyć losowe (a, b) tylko losowe (0,1)?

Question

Powiel możliwe:
how to get uniformed random between a, b by a known uniformed random function RANDOM(0,1)

W Księdze Wprowadzenie do algorytmów istnieje akcyzowy:

Opisać procedury random (a, b) która wykonuje tylko połączenia losowe (0,1). Jaki jest przewidywany czas trwania procedury, w zależności od a i b? Prawdopodobieństwo wyniku losowego (a, b) powinno być czysto równomiernie rozłożone, ponieważ losowe (0,1)

Dla funkcji losowej wyniki są liczbami całkowitymi z przedziału od a do b włącznie. Na przykład Random (0,1) generuje 0 lub 1; Losowy (a, b) generuje a + 1 a + 2, ..., b

Proponowane rozwiązanie jest tak:

for i = 1 to b-a 
    r = a + Random(0,1) 
return r 

czas odtwarzania jest T = BA

Czy to prawda? Czy wyniki moich rozwiązań są równomiernie dystrybuowane?

Dzięki

Co jeśli moje nowe rozwiązanie jest tak:

r = a 
for i = 1 to b - a //including b-a 
    r += Random(0,1) 
return r 

Jeśli nie jest poprawna, dlaczego R + = Losowy (0,1) sprawia, że ​​R nie równomiernie rozmieszczone?

Answer 1

Inni wyjaśnili, dlaczego Twoje rozwiązanie nie działa. Oto poprawne rozwiązanie:

1) Znajdź najmniejszą liczbę, p, taką, że 2^p > b-a.

2) Wykonaj następujący algorytm:

r=0 
for i = 1 to p 
    r = 2*r + Random(0,1) 

3) Jeżeli r jest większa niż b-a, przejdź do kroku 2.

4) Twój wynik jest r+a

Więc spróbujmy Losowo (1,3).
Więc b-a to 2.
2^1 = 2, więc p będą musiały być tak, że 2^p 2 jest większa niż 2.
więc pętla będzie dwa razy.Spróbujmy wszystkie możliwe wyjścia:

00 -> r=0, 0 is not > 2, so we output 0+1 or 1. 
01 -> r=1, 1 is not > 2, so we output 1+1 or 2. 
10 -> r=2, 2 is not > 2, so we output 2+1 or 3. 
11 -> r=3, 3 is > 2, so we repeat. 

Więc 1/4 czasu, wyjście 1. 1/4 wyjścia my czasu 2. 1/4 wyjścia my czasu 3. I 1/4 czas, w którym musimy powtórzyć algorytm po raz drugi. Wygląda dobrze.

Pamiętaj, że jeśli masz to zrobić dużo, dwie optymalizacje są poręczne:

1) W przypadku korzystania z tego samego zakresu dużo, mają klasę, która oblicza p raz, więc nie trzeba obliczyć za każdym razem.

2) Wiele procesorów ma szybkie sposoby wykonywania kroku 1, które nie są wyświetlane w językach wysokiego poziomu. Na przykład procesory x86 mają instrukcję BSR.

Answer 2

Nie, to nie jest właściwe, ta metoda skupi się wokół numeru (a+b)/2. Jest to dwumianowa dystrybucja.

Czy jesteś pewien, że Random(0,1) tworzy liczby całkowite? byłoby bardziej sensowne, gdyby produkował wartości zmiennoprzecinkowe z zakresu od 0 do 1. Następnie rozwiązaniem byłaby transformacja afiniczna, czas działania niezależny od a i b.

Pomysł, który właśnie miałem, na wypadek, gdyby chodziło o wartości całkowite: użyj bisekcji. Na każdym kroku masz zasięg low-high. Jeśli Random(0,1) zwróci 0, następnym zakresem jest low-(low+high)/2, w innym przypadku (low+high)/2-high. Szczegóły i złożoność pozostały do ​​ciebie, ponieważ jest to praca domowa.

To powinno stworzyć (w przybliżeniu) jednolity rozkład.

Edytuj:około to ważne słowo. Jednolity jeśli b-a+1 jest potęgą 2, nie za daleko, jeśli jest blisko, ale ogólnie nie jest wystarczająco dobry. Cóż, to był spontaniczny pomysł, nie można ich wszystkich naprawić.

Answer 3

Przede wszystkim zakładam, że faktycznie gromadzisz wynik, nie dodając 0 lub 1 do a na każdym kroku. Korzystając z niektórych probabilitów możesz udowodnić, że twoje rozwiązanie nie jest równomiernie dystrybuowane. Szansa, że ​​uzyskana wartość r jest (a + b)/2 jest największa.Na przykład, jeśli a wynosi 0, a b 7, szansa, że ​​otrzymasz wartość 4, jest (kombinacja 4 z 7) podzielona przez 2 podniesiona do potęgi 7. Powodem tego jest to, że bez względu na to, która 4 z 7 wartości to 1 wynik będzie nadal 4.

Szacowany czas działania jest prawidłowy. pseudokod

Answer 4

rozwiązanie powinno wyglądać następująco:

r=a 
for i = 0 to b-a 
    r+=Random(0,1) 
return r 

Jeśli chodzi o równomiernym rozkładzie, przy założeniu, że losowo realizacja to generator liczb losowych jest oparta na doskonale jednolity szanse na uzyskanie 0 lub 1 to 50%. Dlatego otrzymanie numeru, który chcesz, jest wynikiem tego wyboru dokonanego w kółko.

Dla a = 1, b = 5, zostało wybranych 5 opcji.

szanse na uzyskanie 1 obejmuje 5 decyzji same 0, szanse, które wynoszą od 0,5^5 = 3,125%

szanse na uzyskanie 5 obejmuje 5 decyzji, wszystko 1, szanse, które wynoszą od 0,5^5 = 3,125%

Jak widać z powyższego, rozkład nie jest jednolity - szanse dowolnej liczby powinny wynosić 20%.

Answer 5

W algorytmie, który utworzyłeś, naprawdę nie jest równo rozłożony.

Wynik "r" zawsze będzie "a" lub "a + 1". To nigdy nie wyjdzie poza to.

To powinno wyglądać mniej więcej tak:

r=0; 
for i=0 to b-a 
    r = a + r + Random(0,1) 

return r; 

Włączając „r” do swojego obliczeń, jesteś tym „przypadkowości” wszystkich poprzednich „dla” przebiegów pętli.

Answer 6

Nie, twoje rozwiązanie nie jest poprawne. Ta suma będzie miała rozkład dwumianowy.

Można jednak wygenerować czystą losową sekwencję 0, 1 i traktować ją jako liczbę binarną.

repeat 
    result = a 
    steps = ceiling(log(b - a)) 

    for i = 0 to steps 
    result += (2^i) * Random(0, 1) 
until result <= b 

KennyTM: moje złe.

Answer 7

Przeczytałem inne odpowiedzi. Dla zabawy, oto inny sposób na znalezienie losowej liczby:

Przydziel tablicę z elementami b-a. Ustaw wszystkie wartości na 1. Powtórz po tablicy. Dla każdego niezerowego elementu odwróć monetę, tak jak poprzednio. Jeśli pojawi się 0, ustaw element na 0.

Kiedy po całkowitym iteracji, masz tylko 1 elementem pozostały, masz liczbę losową: a+i gdzie i jest indeksem elementu niezerową (zakładając rozpoczynamy indeksowanie na 0). Wszystkie liczby są równie prawdopodobne. (Będziesz musiał zmierzyć się z przypadkiem, w którym jest remis, ale zostawiam to jako ćwiczenie dla ciebie.)

To by miało O(infinity) ... :) Średnio jednak połowa liczb byłaby wyeliminowana , więc miałby średni czas działania sprawy: log_2 (b-a).