Trình tạo số ngẫu nhiên không thiên vị bằng cách sử dụng máy phát số

Question

Bạn có bộ tạo số ngẫu nhiên tạo ra 1 với xác suất p và 0 với xác suất (1-p). Bạn không biết giá trị của p. Sử dụng điều này làm cho bộ tạo số ngẫu nhiên không thiên vị tạo ra 1 với xác suất 0.5 và 0 với xác suất 0.5.

Note: vấn đề này là một vấn đề tập thể dục từ Introduction to Algorithms bởi Cormen, Leiserson, Rivest, Stein (CLRS)

Answer 1

Các sự kiện (p) (1-p) và (1-p). (p) được trang bị. Lấy chúng là 0 và 1 tương ứng và loại bỏ hai cặp kết quả khác bạn nhận được một máy phát ngẫu nhiên không thiên vị.

Trong mã này được thực hiện dễ dàng như:

int UnbiasedRandom() 
{ 
    int x, y; 

    do 
    { 
     x = BiasedRandom(); 
     y = BiasedRandom(); 
    } while (x == y); 

    return x; 
} 

Answer 2

Bạn cần phải vẽ cặp các giá trị từ RNG cho đến khi bạn nhận được một chuỗi các giá trị khác nhau, tức là số không theo sau là một hoặc một tiếp theo số không. Sau đó, bạn lấy giá trị đầu tiên (hoặc cuối cùng, không quan trọng) của chuỗi đó. (ví dụ: Lặp lại miễn là cặp được rút ra là hai số không hoặc hai số không)

Toán học đằng sau điều này rất đơn giản: một 0 thì 1 chuỗi có xác suất rất giống với chuỗi 1 sau đó. Bằng cách luôn lấy phần tử đầu tiên (hoặc cuối cùng) của chuỗi này làm đầu ra của RNG mới của bạn, chúng ta có cơ hội thậm chí để có được số không hoặc một.

Answer 3

Đây là một cách, có lẽ không hiệu quả nhất. Nhai thông qua một loạt các số ngẫu nhiên cho đến khi bạn nhận được một chuỗi các hình thức [0 ..., 1, 0 ..., 1] (trong đó 0 ... là một hoặc nhiều 0s). Đếm số lượng 0. Nếu chuỗi đầu tiên dài hơn, hãy tạo một chuỗi 0, nếu chuỗi thứ hai dài hơn, hãy tạo ra 1. Nếu chúng giống nhau, hãy thử lại.)

Điều này giống như những gì HotBits tạo ra các số ngẫu nhiên từ phóng xạ phân rã hạt:

Do thời gian phân rã bất kỳ là ngẫu nhiên, thì khoảng cách giữa hai phân rã liên tiếp cũng là ngẫu nhiên. Những gì chúng tôi làm, sau đó, là đo một cặp các khoảng thời gian này và phát ra một số không hoặc một bit dựa trên độ dài tương đối của hai khoảng thời gian đó. Nếu chúng ta đo khoảng cách tương tự cho hai phân rã, chúng tôi loại bỏ các đo lường và thử lại

HotBits: How It Works

Answer 4

Bí quyết do von Neumann nhận được hai bit tại một thời điểm, có 01 tương ứng với 0 và 10 đến 1 và lặp lại cho 00 hoặc 11 đã xuất hiện. Giá trị mong muốn của bit bạn cần trích xuất để có được một bit bằng cách sử dụng phương thức này là 1/p(1-p), có thể khá lớn nếu p đặc biệt nhỏ hoặc lớn, vì vậy bạn nên hỏi liệu phương pháp có thể được cải thiện hay không. hiển nhiên rằng nó ném đi rất nhiều thông tin (tất cả 00 và 11 trường hợp).

Googling cho "von neumann trick biased" được sản xuất this paper phát triển giải pháp tốt hơn cho vấn đề. Ý tưởng là bạn vẫn nhận bit hai tại một thời điểm, nhưng nếu hai lần thử đầu tiên chỉ tạo ra 00s và 11s, bạn coi một cặp 0 là một 0 và một cặp là 1s, và áp dụng thủ thuật von Neumann cho những cặp này. Và nếu điều đó không hiệu quả, hãy tiếp tục kết hợp tương tự ở cấp độ này của cặp, v.v.Hơn nữa, bài báo phát triển điều này tạo ra nhiều bit không thiên vị từ nguồn thiên vị, về cơ bản sử dụng hai cách khác nhau để tạo bit từ các bit-bit, và đưa ra một phác thảo rằng điều này là tối ưu theo nghĩa nó tạo ra chính xác số bit mà chuỗi ban đầu có entropy trong đó.

Answer 5

Thủ tục tới produce an unbiased coin from a biased one lần đầu tiên được gán cho Von Neumann (một người đã thực hiện công việc rất lớn trong môn toán và nhiều lĩnh vực liên quan). Quy trình này rất đơn giản:

• Toss xu hai lần.
• Nếu kết quả phù hợp, hãy bắt đầu lại, quên cả hai kết quả.
• Nếu kết quả khác nhau, hãy sử dụng kết quả đầu tiên, hãy quên kết quả thứ hai.

Lý do thuật toán này hoạt động là do xác suất nhận được HT là p(1-p), giống như nhận được TH (1-p)p. Vì vậy, hai sự kiện đều có khả năng như nhau.

Tôi cũng đang đọc sách này và nó sẽ hỏi thời gian chạy dự kiến. Xác suất hai lần tung không bằng nhau là z = 2*p*(1-p), do đó thời gian chạy dự kiến ​​là 1/z.

---

Ví dụ trước đây trông đáng khích lệ (sau khi tất cả, nếu bạn có một đồng xu thiên vị với một sự thiên vị của p=0.99, bạn sẽ cần phải ném đồng xu của bạn khoảng 50 lần, mà không phải là nhiều). Vì vậy, bạn có thể nghĩ rằng đây là một thuật toán tối ưu. Đáng buồn thay nó không phải là.

Dưới đây là cách so sánh với Shannon's theoretical bound (hình ảnh được chụp từ answer) này. Nó cho thấy rằng thuật toán là tốt, nhưng xa tối ưu.

Bạn có thể đưa ra một sự cải tiến nếu bạn sẽ xem xét rằng HHTT sẽ bị loại bỏ bởi thuật toán này, nhưng trên thực tế nó có khả năng tương tự như TTHH. Vì vậy, bạn cũng có thể dừng lại ở đây và trở lại H. Điều tương tự là với HHHHTTTT và vân vân. Sử dụng những trường hợp này cải thiện thời gian chạy dự kiến, nhưng không làm cho nó tối ưu về mặt lý thuyết.

---

Và vào cuối - Mã python:

import random 

def biased(p): 
    # create a biased coin 
    return 1 if random.random() < p else 0 

def unbiased_from_biased(p): 
    n1, n2 = biased(p), biased(p) 
    while n1 == n2: 
     n1, n2 = biased(p), biased(p) 

    return n1 

p = random.random() 
print p 

tosses = [unbiased_from_biased(p) for i in xrange(1000)] 
n_1 = sum(tosses) 
n_2 = len(tosses) - n_1 
print n_1, n_2 

Nó là khá tự giải thích, và đây là một kết quả ví dụ:

0.0973181652114 
505 495 

Như bạn thấy, tuy nhiên chúng tôi đã có thiên vị của 0.097, chúng tôi có cùng số lượng 1 và 0