Trình tạo số giả ngẫu nhiên - Phân phối số mũ

Question

Tôi muốn tạo một số số giả ngẫu nhiên và cho đến bây giờ tôi đã rất hài lòng với chức năng Random.Next(int min, int max) của thư viện .Net. PRNG của giống này là giả sử để sử dụng Uniform distribution, nhưng tôi rất muốn tạo một số bằng cách sử dụng Exponential Distribution.

Tôi đang lập trình bằng C#, mặc dù tôi sẽ chấp nhận mã giả hoặc C++, Java hoặc tương tự.

Bất kỳ đề xuất/đoạn mã/thuật toán/suy nghĩ nào?

Answer 1

Vì bạn có quyền truy cập vào bộ tạo số ngẫu nhiên đồng nhất, tạo số ngẫu nhiên được phân phối với phân phối khác mà CDF bạn biết là dễ dàng bằng cách sử dụng inversion method.

Vì vậy, tạo một số ngẫu nhiên thống nhất, u, trong [0,1), sau đó tính toán x bởi:

x = log(1-u)/( − & lambda; ),

nơi & lambda; là thông số tốc độ của phân phối mũ. Bây giờ, x là một số ngẫu nhiên với phân phối mũ. Lưu ý rằng log ở trên là ln, logarit tự nhiên.

Answer 2

Nếu tôi hiểu vấn đề của bạn, và bạn có thể chấp nhận một số hữu hạn các PRNG, bạn có thể làm theo một cách tiếp cận như:

• Tạo một mảng mà mỗi phần tử là trong phân phối mũ của bạn
• Tạo một PRNG đó là một chỉ số nguyên vào mảng. Trả về phần tử trong mảng tại chỉ mục đó.

Answer 3

Đây là những gì tôi sử dụng khi phải đối mặt với yêu cầu tương tự:

// sorry.. pseudocode, mine was in Tcl: 

int weighted_random (int max) { 
    float random_number = rand(); 
    return floor(max - ceil(max * random_number * random_number)) 
} 

Tất nhiên đây là công thức của bình phương các số ngẫu nhiên, do đó bạn đang tạo ra một số ngẫu nhiên dọc theo một đường cong bậc hai.

Answer 4

Nếu bạn muốn có số ngẫu nhiên tốt, hãy xem xét liên kết đến các thói quen gsl: http://www.gnu.org/software/gsl/. Họ có thường lệ gsl_ran_exponential. Nếu bạn muốn tạo các số ngẫu nhiên bằng cách sử dụng bộ tạo sẵn có phân phối đồng đều trên [0, 1) (ví dụ u = Random.Next (0, N-1)/N, đối với một số N lớn), thì chỉ cần sử dụng:

-mu * log (1-u) 

Xem randist/exponential.c trong nguồn gsl.

CHỈNH SỬA: chỉ để so sánh với một số câu trả lời sau - điều này tương đương với mu = 1/lambda. mu ở đây là trung bình của phân phối, còn được gọi là tham số tỷ lệ trên trang wikipedia mà OP được liên kết đến và lambda là tham số tốc độ.

Answer 5

Định lý cơ bản về lấy mẫu giữ rằng nếu bạn có thể bình thường hóa, tích hợp và đảo ngược phân phối mong muốn, bạn ở nhà miễn phí.

Nếu bạn có phân phối mong muốn F(x) được chuẩn hóa trên [a,b].Bạn tính toán

C(y) = \int_a^y F(x) dx 

nghịch rằng để có được C^{-1}, ném z thống nhất trên [0,1) và tìm

x_i = C^{-1}(z_i) 

mà sẽ có sự phân bố mong muốn.

---

Trong trường hợp của bạn: F(x) = ke^{-kx} và tôi sẽ cho rằng bạn muốn [0,infinity]. Chúng tôi nhận được:

C(y) = 1 - e^{-ky} 

đó là invertable để cung cấp cho

x = -1/k ln(1 - z) 

cho z ném thống nhất trên [0,1).

---

Tuy nhiên, thẳng thắn, sử dụng thư viện được sửa lỗi cũng thông minh hơn trừ khi bạn đang thực hiện việc này để chỉnh sửa.

Answer 6

Một thuộc tính thú vị của phân bổ theo cấp số nhân: Xem xét quy trình đến với thời gian liên kết theo cấp số mũ. Dành bất kỳ khoảng thời gian nào (t1, t2) và những khách đến trong khoảng thời gian đó. Những người đến đó là UNIFORMLY phân phối giữa t1 và t2. (Sheldon Ross, Stochastic Processes).

Nếu tôi có trình tạo số giả ngẫu nhiên và vì lý do nào đó (ví dụ: phần mềm của tôi không thể tính nhật ký), bạn không muốn thực hiện chuyển đổi ở trên, nhưng muốn có hàm mũ. với giá trị trung bình là 1.0.

Bạn có thể:

1) Tạo 1001 U (0,1) biến ngẫu nhiên.

2) Sắp xếp theo thứ tự

3) Trừ thứ hai từ thứ nhất, thứ ba từ thứ hai, ... để nhận 1000 khác biệt.

4) Những khác biệt này là RV theo cấp số nhân với từ phân bố có giá trị trung bình = 1,0.

Ít hiệu quả hơn, tôi nghĩ, nhưng là phương tiện cho cùng một kết thúc.

Answer 7

Mã nguồn mở Uncommons Maths library by Dan Dyer cung cấp trình tạo số ngẫu nhiên, phân phối xác suất, tổ hợp và thống kê cho Java.

Trong số các lớp học có giá trị khác, ExponentialGenerator về cơ bản đã triển khai ý tưởng được giải thích bởi @Alok Singhal. Trong its tutorial blog, một đoạn mã được đưa ra để mô phỏng một số sự kiện ngẫu nhiên xảy ra trung bình 10 lần một phút:

final long oneMinute = 60000; 
Random rng = new MersenneTwisterRNG(); 

// Generate events at an average rate of 10 per minute. 
ExponentialGenerator gen = new ExponentialGenerator(10, rng); 
boolean running = true; 
while (true) 
{ 
    long interval = Math.round(gen.nextValue() * oneMinute); 
    Thread.sleep(interval); 

    // Fire event here. 
} 

Tất nhiên, nếu bạn muốn đơn vị thời gian per second (thay vì a minute đây), bạn chỉ cần để đặt final long oneMinute = 1000.

Đi sâu hơn vào source code của phương pháp nextValue() của ExponentialGenerator, bạn sẽ tìm thấy cái gọi là nghịch đảo lấy mẫu được mô tả trong Generating_exponential_variates [wiki]:

public Double nextValue() 
{ 
    double u; 
    do 
    { 
     // Get a uniformly-distributed random double between 
     // zero (inclusive) and 1 (exclusive) 
     u = rng.nextDouble(); 
    } while (u == 0d); // Reject zero, u must be positive for this to work. 
    return (-Math.log(u))/rate.nextValue(); 
} 

PS: Gần đây tôi đang sử dụng Uncommons Toán thư viện. Cảm ơn Dan Dyer.