Làm thế nào để tạo ra một số ngẫu nhiên từ phân phối rời rạc được chỉ định?

Question

Cho phép nói rằng chúng tôi có một số phân phối riêng biệt với số lượng hữu hạn kết quả có thể tạo ra một số ngẫu nhiên từ phân phối này nhanh hơn trong O (logn), trong đó n là số kết quả có thể?

Làm thế nào để làm cho nó trong thời gian O (logn):
- Thực hiện một mảng với xác suất tích lũy (Array [i] = Xác suất mà số ngẫu nhiên sẽ ít hoặc bằng i)
- Tạo số ngẫu nhiên từ phân phối đồng đều (cho phép biểu thị nó bằng k)
- Tìm số i nhỏ nhất sao cho k < Mảng [i]. Nó có thể được thực hiện bằng cách sử dụng tìm kiếm nhị phân.
- tôi là số ngẫu nhiên của chúng tôi.

Answer 1

Phương thức bí danh của trình đi có thể vẽ một mẫu trong trường hợp xấu nhất liên tục, sử dụng một số mảng phụ có kích thước n cần được precomputed. Phương pháp này được mô tả trong Chương 3 của Devroye's book on sampling và được thực hiện trong hàm R(). Bạn có thể lấy mã từ mã nguồn của R hoặc this thread. Yêu cầu 1991 paper by Vose để giảm chi phí khởi tạo.

Lưu ý rằng câu hỏi của bạn không được xác định rõ, trừ khi bạn chỉ định biểu mẫu chính xác của dữ liệu nhập và số lượng ngẫu nhiên bạn muốn vẽ. Ví dụ, nếu đầu vào là một mảng cho xác suất của mỗi kết quả, thì thuật toán của bạn không phải là O (log n) bởi vì nó yêu cầu đầu tiên tính toán xác suất tích lũy trong đó có thời gian O (n) từ mảng đầu vào.

Nếu bạn có ý định vẽ nhiều mẫu thì chi phí tạo một mẫu đơn không quá quan trọng. Thay vào đó những gì quan trọng là tổng chi phí để tạo ra kết quả m, và bộ nhớ cao điểm cần thiết. Về vấn đề này, phương pháp bí danh rất tốt. Nếu bạn muốn tạo các mẫu cùng một lúc, hãy sử dụng thuật toán O (n + m) được đăng here và sau đó trộn các kết quả.