Come ottenere numeri casuali con il generatore errato

Question

Domanda: Supponiamo di avere un generatore di numeri casuali randn() che restituisce un numero casuale distribuito uniformemente tra 0 e n-1. Dato un numero qualsiasi m, scrivi un generatore di numeri casuali che restituisca un numero casuale distribuito uniformemente tra 0 e m-1.

La mia risposta:

-(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(); 
    } 
} 

È corretto?

Answer 1

Sei vicino, ma il problema con la tua risposta è che c'è più di un modo per scrivere un numero come somma di altri due numeri.

Se m<n, questo funziona perché i numeri 0,1,...,m-1 appaiono ciascuno con uguale probabilità e l'algoritmo termina quasi sicuramente.

Questa risposta non funziona in generale perché esiste più di un modo per scrivere un numero come somma di altri due numeri. Ad esempio, c'è solo un modo per ottenere 0 ma ci sono molti modi per ottenere m/2, quindi le probabilità non saranno uguali.

Esempio: n = 2 e m=3

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

così la distribuzione di probabilità dal tuo metodo è

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

che non è uniforme.

---

Per risolvere questo problema, è possibile utilizzare una fattorizzazione unica. Scrivi m nella base n, tenendo traccia del più grande esponente necessario, ad esempio e. Quindi, trova il multiplo più grande di m più piccolo di n^e, chiamalo k. Infine, genera i numeri e con randn(), prendili come espansione n di base del numero x, se x < k*m, restituisci x, altrimenti riprova.

Supponendo che m < n^2, quindi

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

non è corretto.

Si aggiungono numeri casuali uniformi, che non producono un risultato casuale uniforme. Dire n = 2 e m = 3, quindi i valori possibili per x sono 0 + 0, 0 + 1, 1 + 0, 1 + 1. Quindi hai il doppio delle probabilità di ottenere 1 di quello che ottieni 0 o 2.

Quello che devi fare è scrivere m in base n, e quindi generare 'cifre' della rappresentazione base-n del casuale numero. Quando hai il numero completo, devi controllare se è inferiore a m. Se lo è, allora hai finito. Se non lo è, allora è necessario ricominciare da capo.

Answer 3

La somma di due generatori di numeri casuali uniformi non viene generata in modo uniforme. Ad esempio, la somma di due dadi è più probabile che sia 7 su 12, perché per ottenere 12 devi lanciare due sei, mentre puoi ottenere 7 come 1 + 6 o 6 + 1 o 2 + 5 o 5 + 2 o ...

Supponendo che randn() restituisce un intero compreso tra 0 e n - 1, n * randn() + randn() è distribuito uniformemente tra 0 e n * n - 1, in modo da poter aumentare la sua gamma. Se randn() restituisce un numero intero compreso tra 0 e k * m + j - 1, quindi chiamalo ripetutamente finché non ottieni un numero < = k * m - 1, quindi dividi il risultato per k per ottenere un numero uniformemente distribuito tra 0 e m -1.

Answer 4

Supponendo che entrambi n sono meri interi positivi, l'algoritmo standard del ridimensionamento non dovrebbe funzionare?

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