Cách nhận số ngẫu nhiên với trình tạo sai

Question

Câu hỏi: Giả sử bạn có một trình tạo số ngẫu nhiên randn() trả về một số ngẫu nhiên được phân phối đồng đều giữa 0 và n-1. Cho bất kỳ số nào m, hãy viết một trình tạo số ngẫu nhiên trả về một số ngẫu nhiên được phân phối đồng đều giữa 0 và m-1.

câu trả lời của tôi:

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

Đây có phải là đúng?

Answer 1

Bạn thân thiết, nhưng vấn đề với câu trả lời của bạn là có nhiều cách viết một số làm tổng của hai số khác.

Nếu m<n, thì điều này hoạt động vì các số 0,1,...,m-1 xuất hiện từng có xác suất bằng nhau và thuật toán chấm dứt gần như chắc chắn.

Câu trả lời này không có tác dụng nói chung vì có nhiều cách viết một số làm tổng của hai số khác. Ví dụ, chỉ có một cách để có được 0 nhưng có rất nhiều cách để có được m/2, vì vậy xác suất sẽ không bằng nhau.

Ví dụ: n = 2 và m=3

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

nên phân bố xác suất từ ​​phương pháp của bạn là

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

mà không phải là thống nhất.

---

Để khắc phục điều này, bạn có thể sử dụng hệ số duy nhất. Viết m trong cơ sở n, theo dõi số mũ cần thiết lớn nhất, nói e. Sau đó, tìm bội số lớn nhất của m nhỏ hơn n^e, gọi số đó là k. Cuối cùng, tạo số e với randn(), lấy chúng làm cơ sở n mở rộng một số số x, nếu x < k*m, trả lại x, nếu không hãy thử lại.

Giả sử rằng m < n^2, sau đó

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

Nó không phải là chính xác.

Bạn đang thêm số ngẫu nhiên đồng nhất, không tạo ra kết quả ngẫu nhiên thống nhất. Nói n = 2 và m = 3, thì giá trị có thể cho x là 0 + 0, 0 + 1, 1 + 0, 1 + 1. Vì vậy, bạn có khả năng nhận được 1 lần so với số 0 hoặc 2.

Những gì bạn cần làm là viết m trong cơ sở n và sau đó tạo 'chữ số' của đại diện cơ sở-n của ngẫu nhiên con số. Khi bạn có số đầy đủ, bạn phải kiểm tra xem nó có nhỏ hơn m không. Nếu có, thì bạn đã hoàn tất. Nếu không, thì bạn cần phải bắt đầu lại.

Answer 3

Tổng của hai bộ tạo số ngẫu nhiên đồng nhất không được tạo đồng đều. Ví dụ, tổng của hai con xúc xắc có nhiều khả năng là 7 hơn 12, bởi vì để có được 12 bạn cần phải ném hai sáu, trong khi bạn có thể nhận được 7 là 1 + 6 hoặc 6 + 1 hoặc 2 + 5 hoặc 5 + 2 hoặc ...

Giả sử randn() trả về một số nguyên giữa 0 và n - 1, n * randn() + randn() được phân bố đồng đều giữa 0 và n * n - 1, vì vậy bạn có thể tăng phạm vi của nó. Nếu randn() trả về một số nguyên nằm trong khoảng từ 0 đến k * m + j - 1, sau đó gọi nó lặp lại cho đến khi bạn nhận được số < = k * m - 1, và sau đó chia kết quả cho k để nhận số phân bố đồng đều giữa 0 và m -1.

Answer 4

Giả sử cả n và m là số nguyên dương, sẽ không phải là thuật toán chuẩn của việc mở rộng quy mô?

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