Hướng dẫn is random in python actually random? - là ngẫu nhiên trong python thực sự ngẫu nhiên?

Nghịch lý sinh nhật, hoặc tại sao PRNG sản xuất trùng lặp thường xuyên hơn bạn nghĩ.

Có một vài vấn đề đang diễn ra trong vấn đề của OP. Một là nghịch lý sinh nhật như đã đề cập ở trên và thứ hai là bản chất của những gì bạn đang tạo ra, vốn không đảm bảo rằng một số nhất định sẽ không được lặp lại.

Nghịch lý sinh nhật áp dụng trong đó giá trị đã cho có thể xảy ra nhiều lần trong khoảng thời gian của trình tạo - và do đó các bản sao có thể xảy ra trong một mẫu giá trị. Hiệu quả của nghịch lý sinh nhật là khả năng thực sự có được các bản sao như vậy là khá quan trọng và khoảng thời gian trung bình giữa chúng nhỏ hơn so với người ta có thể nghĩ. Sự bất hòa này giữa các xác suất nhận thức và thực tế làm cho nghịch lý sinh nhật trở thành một ví dụ điển hình về sự thiên vị nhận thức, trong đó một ước tính trực quan ngây thơ có thể là sai lầm.

Một đoạn mồi nhanh trên các trình tạo số ngẫu nhiên giả (PRNGS)

Phần đầu tiên của vấn đề của bạn là bạn đang lấy giá trị tiếp xúc của một trình tạo số ngẫu nhiên và chuyển đổi nó thành một số nhỏ hơn nhiều, do đó, không gian của các giá trị có thể giảm. Mặc dù một số trình tạo số giả ngẫu nhiên không lặp lại các giá trị trong giai đoạn của chúng, việc chuyển đổi này thay đổi tên miền thành một số nhỏ hơn nhiều. Miền nhỏ hơn làm mất hiệu lực điều kiện 'không lặp lại' để bạn có thể mong đợi khả năng lặp lại đáng kể.

Một số thuật toán, chẳng hạn như prng (A'=AX|M) tuyến tính (A'=AX|M) đảm bảo tính duy nhất cho toàn bộ thời gian. Trong LCG, giá trị được tạo chứa toàn bộ trạng thái của bộ tích lũy và không có trạng thái bổ sung nào được giữ. Trình tạo có tính xác định và không thể lặp lại một số trong khoảng thời gian - bất kỳ giá trị tích lũy nào có thể chỉ ngụ ý một giá trị liên tiếp có thể. Do đó, mỗi giá trị chỉ có thể xảy ra một lần trong khoảng thời gian của máy phát. Tuy nhiên, khoảng thời gian của PRNG như vậy là tương đối nhỏ - khoảng 2^30 cho việc triển khai điển hình của thuật toán LCG - và có thể không lớn hơn số lượng giá trị riêng biệt.

Không phải tất cả các thuật toán PRNG đều chia sẻ đặc điểm này; Một số có thể lặp lại một giá trị nhất định trong khoảng thời gian. Trong vấn đề của OP, thuật toán Mersenne Twister (được sử dụng trong mô -đun ngẫu nhiên của Python) có một khoảng thời gian rất dài - lớn hơn nhiều so với 2^32. Không giống như prng đồng bào tuyến tính, kết quả không hoàn toàn là hàm của giá trị đầu ra trước đó vì bộ tích lũy chứa trạng thái bổ sung. Với đầu ra số nguyên 32 bit và khoảng thời gian ~ 2^19937, nó không thể cung cấp một sự đảm bảo như vậy.

Mersenne Twister là một thuật toán phổ biến cho PRNGS vì nó có tính chất thống kê và hình học tốt và một thời gian rất dài - đặc điểm mong muốn cho một PRNG được sử dụng trên các mô hình mô phỏng.

• Các thuộc tính thống kê tốt có nghĩa là các số được tạo bởi thuật toán được phân phối đều không có số có xác suất xuất hiện cao hơn đáng kể so với các số khác. Các đặc tính thống kê kém có thể tạo ra độ lệch không mong muốn trong kết quả.

• Thích thích hình học tốt có nghĩa là các bộ N số không nằm trên một siêu phẳng trong không gian N chiều. Các đặc tính hình học kém có thể tạo ra các mối tương quan giả trong mô hình mô phỏng và làm biến dạng kết quả.

• Một khoảng thời gian dài có nghĩa là bạn có thể tạo ra rất nhiều số trước khi trình tự kết thúc xung quanh để bắt đầu. Nếu một mô hình cần một số lượng lớn các lần lặp hoặc phải được chạy từ một số hạt giống thì các số có sẵn 2^30 hoặc hơn có thể từ một triển khai LCG điển hình có thể không đủ. Thuật toán MT19337 có một khoảng thời gian rất dài - 2^19337-1, hoặc khoảng 10^5821. Để so sánh, tổng số nguyên tử trong vũ trụ được ước tính khoảng 10^80.

Số nguyên 32 bit được sản xuất bởi MT19337 PRNG có thể có thể đại diện cho đủ các giá trị riêng biệt để tránh lặp lại trong một khoảng thời gian lớn như vậy. Trong trường hợp này, các giá trị trùng lặp có thể xảy ra và không thể tránh khỏi với một mẫu đủ lớn.

Nghịch lý sinh nhật một cách ngắn gọn

Vấn đề này ban đầu được định nghĩa là xác suất của bất kỳ hai người nào trong phòng chia sẻ cùng một sinh nhật. Điểm mấu chốt là bất kỳ hai người nào trong phòng đều có thể chia sẻ sinh nhật. Mọi người có xu hướng hiểu sai vấn đề vì xác suất của một người nào đó trong phòng chia sẻ sinh nhật với một cá nhân cụ thể, đó là nguồn gốc của sự thiên vị nhận thức thường khiến mọi người đánh giá thấp xác suất. Đây là giả định không chính xác - không có yêu cầu nào đối với trận đấu với một cá nhân cụ thể và bất kỳ hai cá nhân nào cũng có thể phù hợp.any two people in the room could share a birthday. People tend to naively misinterpret the problem as the probability of someone in the room sharing a birthday with a specific individual, which is the source of the cognitive bias that often causes people to underestimate the probability. This is the incorrect assumption - there is no requirement for the match to be to a specific individual and any two individuals could match.

Xác suất của một trận đấu xảy ra giữa bất kỳ hai cá nhân nào cao hơn nhiều so với xác suất của một trận đấu với một cá nhân cụ thể vì trận đấu không phải đến một ngày cụ thể. Thay vào đó, bạn chỉ phải tìm hai cá nhân có chung sinh nhật. Từ biểu đồ này (có thể tìm thấy trên trang Wikipedia về chủ đề này), chúng ta có thể thấy rằng chúng ta chỉ cần 23 người trong phòng để có 50% cơ hội tìm kiếm hai người phù hợp theo cách này.

Từ mục Wikipedia về chủ đề này, chúng tôi có thể nhận được một bản tóm tắt tốt đẹp. Trong vấn đề của OP, chúng tôi có 4.500 'sinh nhật' có thể, thay vì 365. Đối với một số lượng giá trị ngẫu nhiên nhất định được tạo (tương đương với 'người'), chúng tôi muốn biết xác suất của bất kỳ hai giá trị giống hệt nhau nào xuất hiện trong chuỗi.

Tính toán hiệu ứng có khả năng của nghịch lý sinh nhật đối với vấn đề của OP

Đối với một chuỗi gồm 100 số, chúng tôi có các cặp (xem hiểu vấn đề) có khả năng khớp (nghĩa là số thứ nhất có thể khớp với số thứ hai, thứ ba, v.v., số thứ hai có thể khớp với số thứ ba, thứ tư, v.v.) Số lượng các kết hợp có khả năng phù hợp hơn là chỉ hơn 100.

Từ việc tính toán xác suất, chúng ta nhận được một biểu hiện của. Đoạn mã sau của mã Python dưới đây thực hiện đánh giá ngây thơ về xác suất của một cặp phù hợp xảy ra.

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

Điều này tạo ra kết quả trông hợp lý của p = 0,669 cho trận đấu xảy ra trong vòng 100 số được lấy mẫu từ dân số 4500 giá trị có thể. (Có lẽ ai đó có thể xác minh điều này và đăng bình luận nếu sai). Từ đó, chúng ta có thể thấy rằng độ dài của các lần chạy giữa các số khớp được quan sát bởi OP dường như khá hợp lý.p=0.669 for a match occurring within 100 numbers sampled from a population of 4500 possible values. (Maybe someone could verify this and post a comment if it's wrong). From this we can see that the lengths of runs between matching numbers observed by the OP seem to be quite reasonable.

Chú thích: Sử dụng xáo trộn để có được một chuỗi các số giả ngẫu nhiên duy nhất

Xem câu trả lời này dưới đây từ S. Mark để biết phương tiện để có được một bộ số ngẫu nhiên được đảm bảo duy nhất. Kỹ thuật áp phích đề cập đến một loạt các số (mà bạn cung cấp, vì vậy bạn có thể làm cho chúng trở nên độc đáo) và chuyển chúng thành một thứ tự ngẫu nhiên. Vẽ các số theo trình tự từ mảng bị xáo trộn sẽ cung cấp cho bạn một chuỗi các số giả ngẫu nhiên được đảm bảo không lặp lại.

Chú thích: PRNGS an toàn về mặt mật mã

Thuật toán MT không an toàn về mặt mật mã vì nó tương đối dễ dàng để suy ra trạng thái bên trong của trình tạo bằng cách quan sát một chuỗi các số. Các thuật toán khác như Blum Blum Shub được sử dụng cho các ứng dụng mật mã nhưng có thể không phù hợp để mô phỏng hoặc các ứng dụng số ngẫu nhiên chung. Các prng an toàn bằng mã hóa có thể tốn kém (có thể yêu cầu tính toán bignum) hoặc có thể không có tính chất hình học tốt. Trong trường hợp của loại thuật toán này, yêu cầu chính là nó phải tính toán không khả thi để suy ra trạng thái bên trong của trình tạo bằng cách quan sát một chuỗi các giá trị.

Là sự lựa chọn ngẫu nhiên () thực sự ngẫu nhiên?

Python Randint có thực sự ngẫu nhiên không?

Có phải Numpy ngẫu nhiên thực sự ngẫu nhiên?

Làm thế nào để ngẫu nhiên hoạt động trên Python?