tái sử dụng số ngẫu nhiên trong hồ chứa mẫu

Question

Nó được hỏi liên quan đến một câu hỏi gần đây: Given an unknown length list, return a random item in it by scanning it only 1 time

Tôi biết bạn không nên, tôi chỉ không thể đặt ngón tay của tôi trên một lời giải thích kinh điển về việc tại sao không.

Nhìn vào mã ví dụ:

import random, sys 

def rnd(): # a function that returns a random number each call 
    return int(random.getrandbits(32)) 

class fixed: # a functor that returns the same random number each call 
    def __init__(self): 
     self._ret = rnd() 
    def __call__(self): 
     return self._ret 

def sample(rnd,seq_size): 
    choice = 0 
    for item in xrange(1,seq_size): 
     if (rnd() % (item+1)) == 0: 
      choice = item 
    return choice 

dist = [0 for i in xrange(500)] 
for i in xrange(1000): 
    dist[sample(rnd,len(dist))] += 1 
print "real",dist 
print 

dist = [0 for i in xrange(500)] 
for i in xrange(1000): 
    dist[sample(fixed(),len(dist))] += 1 
print "reuse",dist 

Các lựa chọn cho các hồ chứa mẫu thích hợp mà tạo ra một số ngẫu nhiên mới mỗi mục là độc đáo phân bố đều như nó phải được:

real [1, 3, 0, 1, 2, 3, 2, 3, 1, 2, 2, 2, 2, 0, 0, 1, 3, 3, 4, 0, 2, 1, 2, 1, 1, 4, 0, 3, 1, 1, 2, 0, 0, 0, 1, 4, 6, 2, 3, 1, 1, 3, 2, 1, 3, 3, 1, 4, 1, 1, 2, 2, 5, 1, 2, 1, 0, 3, 1, 0, 2, 6, 1, 2, 2, 1, 1, 1, 1, 3, 2, 1, 5, 4, 0, 3, 3, 4, 0, 0, 2, 1, 3, 2, 3, 0, 2, 4, 6, 3, 0, 1, 3, 0, 2, 2, 4, 3, 2, 1, 2, 1, 2, 2, 1, 4, 2, 0, 0, 1, 1, 0, 1, 4, 2, 2, 2, 1, 0, 3, 1, 2, 1, 0, 2, 2, 1, 5, 1, 5, 3, 3, 1, 0, 2, 2, 0, 3, 2, 3, 0, 1, 1, 3, 0, 1, 2, 2, 0, 1, 2, 2, 3, 2, 3, 1, 1, 0, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 3, 3, 1, 0, 1, 1, 0, 1, 3, 2, 1, 4, 3, 4, 1, 1, 1, 2, 1, 2, 0, 0, 0, 1, 1, 2, 6, 0, 1, 1, 0, 1, 0, 1, 2, 2, 3, 0, 1, 2, 2, 1, 0, 4, 2, 1, 2, 2, 0, 4, 4, 0, 3, 2, 2, 1, 2, 4, 1, 2, 1, 0, 2, 1, 1, 5, 1, 2, 2, 3, 2, 3, 0, 1, 2, 3, 2, 5, 2, 3, 0, 1, 1, 1, 1, 3, 4, 2, 4, 1, 2, 3, 2, 5, 2, 1, 0, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 2, 0, 4, 1, 1, 2, 3, 4, 3, 1, 2, 3, 3, 3, 2, 1, 2, 0, 0, 4, 3, 2, 2, 5, 5, 3, 3, 3, 1, 0, 1, 3, 1, 1, 2, 4, 3, 1, 4, 4, 2, 5, 0, 5, 4, 2, 1, 0, 4, 1, 3, 3, 2, 4, 2, 3, 3, 1, 3, 3, 4, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 2, 4, 0, 1, 3, 2, 2, 4, 2, 2, 3, 4, 5, 3, 2, 1, 2, 3, 2, 2, 2, 4, 4, 0, 1, 3, 3, 3, 4, 1, 2, 4, 0, 4, 0, 3, 2, 1, 1, 4, 2, 1, 0, 0, 0, 4, 2, 2, 1, 4, 3, 1, 1, 3, 2, 4, 3, 4, 2, 1, 1, 2, 2, 3, 3, 1, 2, 2, 1, 1, 2, 3, 1, 9, 1, 3, 4, 2, 4, 4, 0, 1, 0, 1, 0, 2, 1, 0, 1, 2, 3, 3, 6, 2, 2, 1, 2, 4, 3, 3, 3, 2, 1, 2, 1, 2, 8, 2, 3, 1, 5, 3, 0, 2, 1, 1, 4, 2, 2, 1, 2, 3, 2, 1, 0, 4, 3, 4, 3, 1, 3, 2, 3, 2, 2, 1, 0, 1, 2, 5, 3, 0, 3, 1, 2, 2, 2, 1, 0, 1, 4] 

Trong khi khi bạn sử dụng lại cùng một số ngẫu nhiên cho tất cả các mục, bạn sẽ nhận được phân phối lệch với số rất thấp:

reuse [92, 50, 34, 19, 23, 16, 13, 9, 9, 9, 11, 10, 6, 7, 8, 5, 5, 6, 4, 2, 2, 3, 2, 3, 3, 6, 6, 1, 4, 3, 5, 2, 2, 1, 1, 2, 3, 4, 3, 4, 1, 3, 1, 0, 0, 1, 5, 3, 1, 2, 0, 2, 0, 1, 1, 6, 2, 0, 2, 2, 4, 2, 2, 0, 2, 2, 2, 0, 3, 0, 4, 1, 2, 1, 4, 2, 2, 0, 1, 0, 1, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 1, 3, 1, 0, 1, 2, 0, 4, 3, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 2, 1, 0, 1, 0, 0, 1, 1, 3, 0, 1, 1, 0, 2, 0, 1, 2, 0, 1, 1, 4, 1, 1, 1, 2, 1, 0, 1, 2, 0, 2, 1, 1, 2, 0, 1, 1, 0, 2, 0, 2, 0, 0, 2, 0, 1, 0, 2, 1, 1, 0, 0, 1, 2, 4, 1, 0, 2, 0, 1, 2, 1, 3, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 2, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 4, 1, 0, 2, 1, 0, 0, 2, 1, 1, 3, 3, 2, 0, 1, 0, 2, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 0, 3, 2, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 2, 0, 4, 1, 0, 0, 2, 0, 1, 1, 0, 0, 3, 1, 3, 2, 2, 1, 3, 1, 2, 0, 1, 1, 3, 0, 3, 1, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 3, 1, 0, 2, 3, 1, 1, 0, 1, 3, 3, 1, 1, 1, 0, 2, 1, 1, 4, 1, 1, 1, 2, 0, 3, 1, 1, 0, 4, 1, 1, 0, 1, 3, 1, 0, 1, 1, 0, 3, 3, 0, 2, 4, 0, 1, 2, 1, 6, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 4, 2, 0, 1, 2, 0, 1, 4, 1, 2, 0, 5, 2, 2, 0, 6, 2, 2, 1, 3, 0, 3, 1, 1, 0, 3, 1, 4, 2, 0, 1, 0, 1, 2, 3, 1, 1, 3, 0, 0, 0, 1, 1, 4, 3, 3, 0, 0, 1, 0, 1, 1, 2, 1, 0, 2, 1, 4, 5, 1, 1, 3, 0, 1, 1, 1, 3, 1, 1, 0, 3, 3, 1, 3, 0, 1, 0, 0, 1, 1, 3, 2, 1, 0, 3, 1, 1, 3, 1, 3, 1, 2, 2, 2, 0, 0, 5, 1, 3, 0, 1, 4, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 1, 2, 2, 3, 2, 2, 1, 0, 3, 3, 1, 3, 3, 3, 2, 1, 2, 3, 3, 3, 1, 2, 2, 2, 4, 2, 1, 5, 2, 2, 0] 

Toán học ở đây là gì? Tại sao bạn không thể sử dụng lại cùng một số ngẫu nhiên?

Answer 1

Chỉnh sửa, để phản ứng lại bình luận: hồ chứa mẫu

Cách nên làm việc là: bạn muốn chọn chính xác tỷ lệ đúng mẫu từ mỗi thùng hiện có để tạo nên một bin bổ sung với cùng xác suất. Trong vòng sample() của bạn, với điều kiện bạn đã lấy mẫu ngẫu nhiên một trong các thùng item, bạn cần chọn các mẫu từ mỗi bin với xác suất 1/(item + 1).

Tuy nhiên, với fixed(), cả quyết định chọn và số thùng trước phụ thuộc vào cùng số 32 bit cố định. Điều này có nghĩa là khả năng mẫu được lấy ra khỏi mỗi thùng sẽ không đồng đều.

---

Hãy xem xét điều gì xảy ra trong lần lặp thứ ba của vòng lặp sample(). Bạn có ba thùng hiện tại (0, 1 và 2), và bạn muốn chọn 1/4 mẫu trong mỗi và thêm chúng vào thùng mới được tạo ra 3.

Lưu ý rằng tất cả số 322 bit32 bit trong bin 1 sẽ là ngay cả (vì pass đầu tiên được chọn tất cả các số chia hết cho 2), và tất cả các số trong bin 0 sẽ là số lẻ (vì các số chẵn được chuyển đến bin 1). Đợt thứ hai di chuyển tất cả các số chia hết cho ba đến bin 2 (mà phải là OK cho đến nay, và không thay đổi phân chia đồng đều/lẻ trong các thùng 0 và 1).

Thẻ thứ ba sau đó di chuyển tất cả fixed() số chia hết cho 4 thành bin 3. Tuy nhiên, điều này sẽ chọn một nửa số từ thùng 1 (vì một nửa số chẵn có thể chia hết cho 4) và không có số nào từ thùng 0 (vì tất cả đều là lẻ). Vì vậy, mặc dù kích thước dự kiến ​​của thùng mới phải chính xác, kích thước dự kiến ​​của các thùng cũ không còn giống nhau nữa.

Đó là cách fixed() tạo phân phối không đồng đều: giả định ngầm định rằng bạn có thể chọn một phần chính xác của mỗi thùng bằng cách chọn một số ngẫu nhiên, bị vi phạm nếu số đó phụ thuộc vào cách có thể dự đoán được trên các số được sử dụng để chọn thùng ban đầu.

---

Thuộc tính cơ bản của các số ngẫu nhiên là mỗi mẫu phải được phân phối độc lập với các mẫu trước, theo nghĩa thống kê. Các thuật toán dựa trên các số ngẫu nhiên phụ thuộc vào thuộc tính này.

Trình tạo số giả ngẫu nhiên (PRNG's) không thực sự là ngẫu nhiên; như bạn đã biết, kết quả của họ thực sự là một chuỗi cố định. Các kết quả PRNG được cố ý tranh giành để chúng hoạt động đủ giống như các số ngẫu nhiên thực tế cho hầu hết các mục đích. Tuy nhiên, nếu PRNG là "yếu" đối với một ứng dụng cụ thể, các hoạt động bên trong của PRNG có thể tương tác với các chi tiết của ứng dụng theo những cách kỳ lạ, đến các kết quả rất không ngẫu nhiên.

Những gì bạn đang cố gắng ở đây, bằng cách sử dụng lại cùng một số ngẫu nhiên, đang xây dựng một PRNG xấu. Kết quả thực tế phụ thuộc vào các chi tiết về cách thức ứng dụng sử dụng những con số ngẫu nhiên ...

Mặc dù fixed() là một PRNG cố ý phá vỡ, nhiều thư viện thương mại PRNG của là "yếu", và có thể kết thúc với sự tương tác kỳ lạ tương tự với một số ứng dụng. Như một vấn đề thực tế, "điểm yếu" liên quan đến ứng dụng - và, trong khi có các bài kiểm tra thống kê được sử dụng rộng rãi để cố gắng phơi bày PRNG yếu, không có gì đảm bảo rằng ứng dụng của bạn sẽ không vấp phải một số tương quan kỳ lạ PRNG "mạnh".

Answer 2

Hãy nghĩ về điều này: Điều gì sẽ xảy ra khi số cố định của bạn thực sự nhỏ?

Answer 3

Nếu bạn chọn một số ngẫu nhiên mỗi lần, mục tiếp theo từ luồng có 1/CURRENTSIZE khả năng đánh bại mục đã chọn trước đó.

Vì vậy, vấn đề với một số ngẫu nhiên cho mỗi luồng là gì? Tại sao nó nghiêng phân phối?

Tôi chưa tìm thấy câu trả lời hoàn chỉnh, nhưng tôi có ý tưởng. Ví dụ:

Ví dụ: cho phép lấy 100 dòng và chọn số ngẫu nhiên 0 ... 999. Bây giờ chúng ta nhìn vào nó từ quan điểm của mục thứ hai.

Khi nào chiến thắng? Vâng, trước hết, nó cần phải là N% 2 == 0. Vì vậy, nó phải là một số chẵn. Ngoài ra, nó cũng bị đánh bại bởi mỗi bội số khác của mỗi bội số của 2 trong luồng, 4 ... 6 ... 8 .... 10 v.v. Nhưng nó thắng ví dụ trên 106.

Tính tất cả các số nó thắng với, 0,999 và chúng tôi nhận được 81 lần!

Bây giờ cho phép mất 4, nó cần phải được N% 4 == 0 và nó bị đánh bại bởi tất cả bội số của 4 đến N (8 ... 12 .... 16). Nếu chúng ta tính toán bao nhiêu lần 4 có thể thắng, chúng ta sẽ có 45 lần ...! Vì vậy, phân phối không công bằng.

Điều này có thể được khắc phục nếu bạn tạo số ngẫu nhiên tối đa kích thước của luồng, sau đó tất cả đều có 1 cơ hội giành chiến thắng, làm cho nó trở thành phân phối đồng đều trở lại. Ví dụ: nếu chúng tôi có kích thước luồng là 100 và chúng tôi chọn số ngẫu nhiên là 0..199. Chúng ta biết 100 con số ngẫu nhiên đầu tiên tất cả đều có 1 trận đấu exacly, vì vậy chúng được phân bố đồng đều. Nhưng điều gì xảy ra với những con số ngẫu nhiên 99 ... 199? Sự phân phối thậm chí không! Ví dụ 101 sẽ chỉ cho 101% X == 0 cho 1. Điều này đúng cho tất cả các số nguyên tố (101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199). Vì vậy, mục một có nhiều cơ hội lớn hơn để giành chiến thắng hơn những người khác.

Đây không phải là trường hợp nếu bạn chọn một số ngẫu nhiên mới cho mỗi mục, trong trường hợp đó cơ hội có thể được thêm vào. Ví dụ: khi mục hàng đến cùng, cơ hội trúng thưởng là:

KHÔNG (1/2 + 1/3 + 1/4 + 1/5 + 1/6 (... vv))