Jak uzyskać losowe numery z niewłaściwym generatorem

Question

Pytanie: Załóżmy, że masz generator liczb losowych randn(), który zwraca równomiernie rozłożoną liczbę losową między 0 a n-1. Mając dowolną liczbę m, napisz generator liczb losowych, który zwraca równomiernie rozłożoną liczbę losową między 0 a m-1.

Moja odpowiedź:

-(int)randm() { 
    int k=1; 
    while (k*n < m) { 
     ++k; 
    } 
    int x = 0; 
    for (int i=0; i<k; ++i) { 
     x += randn(); 
    } 
    if (x < m) { 
     return x; 
    } else { 
     return randm(); 
    } 
} 

Czy jest to prawidłowe?

Answer 1

Jesteś blisko, ale problem z twoją odpowiedzią jest taki, że istnieje więcej niż jeden sposób, aby napisać liczbę jako sumę dwóch innych liczb.

Jeśli m<n, to działa, ponieważ numery 0,1,...,m-1 pojawiają się z równym prawdopodobieństwem, a algorytm kończy się prawie na pewno.

Ta odpowiedź nie działa ogólnie, ponieważ istnieje więcej niż jeden sposób, aby wpisać liczbę jako sumę dwóch innych liczb. Na przykład istnieje tylko jeden sposób uzyskania 0, ale istnieje wiele sposobów uzyskania m/2, więc prawdopodobieństwa nie będą równe.

Przykład: n = 2 i m=3

0 = 0+0 
1 = 1+0 or 0+1 
2 = 1+1 

więc rozkład prawdopodobieństwa od sposobu jest

P(0)=1/4 
P(1)=1/2 
P(2)=1/4 

która nie jest jednolita.

---

Aby to naprawić, można użyć unikalnej faktoryzacji. Napisz m w bazie n, śledząc największy potrzebny wykładnik, na przykład e. Następnie znajdź największą wielokrotność m, która jest mniejsza niż n^e, nazwij ją k. Na koniec wygeneruj numery e z randn(), pobierz je jako rozszerzenie bazy n o numerze x, jeśli x < k*m, zwrócony x, w przeciwnym razie spróbuj ponownie.

Zakładając, że m < n^2, następnie

int randm() { 

    // find largest power of n needed to write m in base n 
    int e=0; 
    while (m > n^e) { 
     ++e; 
    } 

    // find largest multiple of m less than n^e 
    int k=1; 
    while (k*m < n^2) { 
     ++k 
    } 
    --k; // we went one too far 

    while (1) { 
     // generate a random number in base n 
     int x = 0; 
     for (int i=0; i<e; ++i) { 
      x = x*n + randn(); 
     } 
     // if x isn't too large, return it x modulo m 
     if (x < m*k) 
      return (x % m); 
    } 
} 

Answer 2

To nie jest poprawna.

Dodajecie jednolite liczby losowe, które nie dają wyniku równomiernie losowego. Powiedzmy n = 2 i m = 3, wtedy możliwe wartości x to 0 + 0, 0 + 1, 1 + 0, 1 + 1. Więc masz dwa razy większą szansę na uzyskanie 1, niż otrzymujesz 0 lub 2.

Co musisz zrobić, to wpisać m w bazie n, a następnie wygenerować "cyfry" reprezentacji liczby losowej numer. Kiedy masz pełny numer, musisz sprawdzić, czy jest on mniejszy niż m. Jeśli tak, to gotowe. Jeśli nie, musisz zacząć od nowa.

Answer 3

Suma dwóch jednolitych generatorów liczb losowych nie jest generowana w sposób jednolity. Na przykład, suma dwóch kostek jest prawdopodobnie większa niż 7, ponieważ aby uzyskać 12, trzeba rzucić dwie szóstki, podczas gdy można uzyskać 7 jako 1 + 6 lub 6 + 1 lub 2 + 5 lub 5 + 2 lub ...

Zakładając, że randn() zwraca liczbę całkowitą od 0 do n - 1, n * randn() + randn() jest równomiernie rozłożone między 0 a n * n - 1, dzięki czemu można zwiększyć jego zakres. Jeśli randn() zwraca liczbę całkowitą od 0 do k * m + j - 1, wywołaj ją wielokrotnie, aż otrzymasz numer < = k * m - 1, a następnie podziel wynik przez k, aby uzyskać liczbę równomiernie rozłożoną między 0 i m -1.

Answer 4

Zakładając, że n i m są dodatnimi liczbami całkowitymi, czy standardowy algorytm skalowania nie działa?

return (int)((float)randn() * m/n);