Làm thế nào để thực hiện Random (a, b) chỉ với Random (0,1)?

Question

thể trùng lặp:
how to get uniformed random between a, b by a known uniformed random function RANDOM(0,1)

Trong cuốn sách của Giới thiệu về các thuật toán, có một tiêu thụ đặc biệt:

Mô tả một thực hiện các thủ tục Random (a, b) chỉ thực hiện các cuộc gọi đến Ngẫu nhiên (0,1). Thời gian chạy dự kiến ​​của thủ tục của bạn, như là một hàm của a và b? Xác suất của kết quả ngẫu nhiên (a, b) phải được phân bố đồng đều thuần túy, như ngẫu nhiên (0,1)

Đối với hàm ngẫu nhiên, kết quả là số nguyên giữa a và b, bao hàm. Ví dụ: Random (0,1) tạo ra 0 hoặc 1; Random (a, b) tạo ra một, a + 1, a + 2, ..., b

Giải pháp của tôi là như thế này:

for i = 1 to b-a 
    r = a + Random(0,1) 
return r 

thời gian chạy là T = ba

Điều này có đúng không? Các kết quả của các giải pháp của tôi có được phân phối đồng đều không?

Cảm ơn

gì nếu giải pháp mới của tôi là như thế này:

r = a 
for i = 1 to b - a //including b-a 
    r += Random(0,1) 
return r 

Nếu nó không phải là đúng, tại sao r + = Random (0,1) làm cho r phân bố không đều?

Answer 1

Những người khác đã giải thích lý do giải pháp của bạn không hoạt động. Đây là giải pháp chính xác:

1) Tìm số nhỏ nhất, p, chẳng hạn như 2^p > b-a.

2) Thực hiện các thuật toán sau đây:

r=0 
for i = 1 to p 
    r = 2*r + Random(0,1) 

3) Nếu r lớn hơn b-a, đi đến bước 2.

4) Kết quả của bạn là r+a

Vì vậy, hãy cố gắng ngẫu nhiên (1,3).
Vì vậy b-a là 2.
2^1 = 2, vì vậy p sẽ phải 2 để 2^p lớn hơn 2.
Vì vậy, chúng tôi sẽ lặp hai lần.Hãy thử tất cả các kết quả có thể có:

00 -> r=0, 0 is not > 2, so we output 0+1 or 1. 
01 -> r=1, 1 is not > 2, so we output 1+1 or 2. 
10 -> r=2, 2 is not > 2, so we output 2+1 or 3. 
11 -> r=3, 3 is > 2, so we repeat. 

Vì vậy, 1/4 thời gian, chúng tôi xuất 1. 1/4 thời gian chúng tôi xuất 2. 1/4 thời gian chúng tôi xuất 3. Và 1/4 của thời gian chúng ta phải lặp lại thuật toán lần thứ hai. Có vẻ tốt.

Lưu ý rằng nếu bạn phải làm điều này rất nhiều, hai tối ưu hóa là tiện dụng:

1) Nếu bạn sử dụng cùng một phạm vi rất nhiều, có một lớp mà tính p một lần, do đó bạn không cần phải tính toán nó mỗi lần.

2) Nhiều CPU có cách nhanh để thực hiện bước 1 không được hiển thị ở các ngôn ngữ cấp cao. Ví dụ, các CPU x86 có lệnh BSR.

Answer 2

Không, không đúng, phương pháp đó sẽ tập trung xung quanh (a+b)/2. Đó là một phân phối nhị thức.

Bạn có chắc chắn rằng Random(0,1) tạo số nguyên không? nó sẽ có ý nghĩa hơn nếu nó tạo ra các giá trị dấu phẩy động từ 0 đến 1. Sau đó, giải pháp sẽ là một phép biến đổi affine, thời gian chạy độc lập với a và b.

Ý tưởng tôi vừa có, trong trường hợp nó là về các giá trị số nguyên: hãy sử dụng bisection. Ở mỗi bước, bạn có một phạm vi low-high. Nếu Random(0,1) trả về 0, phạm vi tiếp theo là low-(low+high)/2, khác (low+high)/2-high. Chi tiết và sự phức tạp còn lại cho bạn, vì đó là bài tập về nhà.

Điều đó sẽ tạo (xấp xỉ) phân phối đồng đều.

Chỉnh sửa:khoảng là từ quan trọng ở đó. Đồng phục nếu b-a+1 là một sức mạnh của 2, không quá xa nếu nó gần, nhưng không đủ tốt nói chung. Ah, đó là một ý tưởng tự phát, không thể làm cho họ ổn.

Answer 3

Trước hết, tôi giả sử bạn đang thực sự tích luỹ kết quả, không thêm 0 hoặc 1 vào mỗi bước. Sử dụng một số xác suất bạn có thể chứng minh rằng giải pháp của bạn không bị phân biệt đồng đều. Cơ hội giá trị kết quả r là (a + b)/2 là lớn nhất.Ví dụ nếu a là 0 và b là 7, cơ hội bạn nhận được giá trị 4 là (kết hợp 4 của 7) chia cho 2 được tăng lên thành lũy thừa 7. Lý do cho điều đó là không có vấn đề gì trong số 4 giá trị trong số 7 giá trị 1 kết quả sẽ vẫn là 4.

Thời gian chạy bạn ước tính là chính xác. giả

Answer 4

của giải pháp của bạn sẽ giống như thế:

r=a 
for i = 0 to b-a 
    r+=Random(0,1) 
return r 

Đối với phân bố đồng đều, giả định rằng việc thực hiện ngẫu nhiên tạo số ngẫu nhiên này được dựa trên là hoàn toàn thống nhất tỷ lệ cược nhận được 0 hoặc 1 là 50%. Do đó nhận được số bạn muốn là kết quả của sự lựa chọn đó được thực hiện hơn và hơn nữa.

Vì vậy, đối với a = 1, b = 5, có 5 lựa chọn được thực hiện.

Các tỷ lệ cược nhận được 1 bao gồm 5 quyết định, tất cả các 0, tỷ lệ cược đó là 0,5^5 = 3.125%

Các tỷ lệ cược nhận được 5 bao gồm 5 quyết định, tất cả 1 sự chênh lệch đó là 0,5^5 = 3.125%

Như bạn có thể thấy từ điều này, phân phối không đồng đều - tỷ lệ cược của bất kỳ số nào phải là 20%.

Answer 5

Trong thuật toán bạn đã tạo, nó thực sự không được phân phối như nhau.

Kết quả "r" sẽ luôn là "a" hoặc "a + 1". Nó sẽ không bao giờ vượt khỏi điều đó.

Nó sẽ giống như thế này:

r=0; 
for i=0 to b-a 
    r = a + r + Random(0,1) 

return r; 

Bằng cách đưa "r" vào tính toán của bạn, bạn đã bao gồm các "ngẫu nhiên" của tất cả các trước "cho" vòng chạy.

Answer 6

Không, giải pháp của bạn không chính xác. Số tiền này sẽ có phân phối nhị thức.

Tuy nhiên, bạn có thể tạo chuỗi ngẫu nhiên thuần túy là 0, 1 và coi đó là số nhị phân.

repeat 
    result = a 
    steps = ceiling(log(b - a)) 

    for i = 0 to steps 
    result += (2^i) * Random(0, 1) 
until result <= b 

KennyTM: xấu.

Answer 7

Tôi đã đọc các câu trả lời khác. Để giải trí, dưới đây là một cách khác để tìm số ngẫu nhiên:

Phân bổ mảng bằng các yếu tố b-a. Đặt tất cả các giá trị thành 1. Lặp lại qua mảng. Đối với mỗi phần tử nonzero, lật đồng xu, như nó được. Nếu nó xuất hiện 0, hãy đặt thành phần là 0.

Bất cứ khi nào, sau khi lặp lại hoàn toàn, bạn chỉ còn lại 1 phần tử, bạn có số ngẫu nhiên: a+i trong đó i là chỉ mục của phần tử không đồng bộ (giả sử chúng tôi bắt đầu lập chỉ mục trên 0). Tất cả các con số đều có khả năng như nhau. (Bạn sẽ phải đối phó với trường hợp đó là một tie, nhưng tôi để lại rằng như là một tập thể dục cho bạn.)

Điều này sẽ có O(infinity) ... :) Trung bình, mặc dù, một nửa số sẽ được loại bỏ , vì vậy nó sẽ có thời gian chạy trung bình là log_2 (b-a).