Xác suất của các kết quả Thuật toán

Question

Tôi có một vấn đề xác suất, mà tôi cần phải mô phỏng trong một khoảng thời gian hợp lý. Ở dạng đơn giản, tôi có 30 đồng tiền không công bằng với mỗi xác suất khác nhau. Sau đó tôi muốn hỏi những thứ như "xác suất chính xác là 12 sẽ là người đứng đầu là gì?", Hoặc "xác suất mà AT LEAST 5 sẽ là đuôi là gì?".

Tôi biết lý thuyết xác suất cơ bản, vì vậy tôi biết tôi có thể liệt kê tất cả (30 lựa chọn x) khả năng, nhưng đó không phải là đặc biệt khả năng mở rộng. Trường hợp xấu nhất (30 chọn 15) có hơn 150 triệu kết hợp. Có cách nào tốt hơn để tiếp cận vấn đề này từ quan điểm tính toán không?

Bất kỳ trợ giúp nào được đánh giá cao, cảm ơn! :-)

Answer 1

Bạn có thể sử dụng phương pháp lập trình động.

Ví dụ: để tính xác suất 12 người đứng đầu trong số 30 xu, hãy cho P (n, k) là xác suất có k đầu từ n tiền xu đầu tiên.

Sau đó, P (n, k) = p_n * P (n - 1, k - 1) + (1 - p_n) * P (n - 1, k)

(ở đây p_i là xác suất các i'th đồng xu là người đứng đầu).

Bây giờ bạn có thể sử dụng mối quan hệ này trong thuật toán lập trình động. Có vectơ 13 xác suất (đại diện cho P (n - 1, i) cho i trong 0..12). Xây dựng một vectơ mới 13 cho P (n, i) sử dụng quan hệ lặp lại ở trên. Lặp lại cho đến n = 30. Tất nhiên, bạn bắt đầu với vectơ (1, 0, 0, 0, ...) cho n = 0 (vì không có đồng xu, bạn chắc chắn sẽ không có đầu).

Trường hợp xấu nhất sử dụng thuật toán này là O (n^2) thay vì theo cấp số mũ.

Answer 2

Đây thực sự là một vấn đề thú vị. Tôi đã được truyền cảm hứng để viết một bài đăng blog về nó bao gồm chi tiết công bằng và không công bằng đồng xu ném tất cả các cách để tình hình của OP có một xác suất khác nhau cho mỗi đồng xu. Bạn cần một kỹ thuật được gọi là lập trình động để giải quyết vấn đề này trong thời gian đa thức.

Vấn đề chung: Với C, một loạt các n tiền xu p-p_n nơi p_i đại diện cho xác suất của số i -th co trong đầu sắp tới, xác suất của k người đứng đầu từ việc tung tất cả tiền xu là gì?

Điều này có nghĩa việc giải quyết các mối quan hệ tái phát sau:

P (n, k, C, i) = p_i x P (n -1, k -1, C, i +1) + (1- p_i) x P (n, k, C, i +1)

Đoạn mã Java thực hiện điều này là:

private static void runDynamic() { 
    long start = System.nanoTime(); 
    double[] probs = dynamic(0.2, 0.3, 0.4); 
    long end = System.nanoTime(); 
    int total = 0; 
    for (int i = 0; i < probs.length; i++) { 
    System.out.printf("%d : %,.4f%n", i, probs[i]); 
    } 
    System.out.printf("%nDynamic ran for %d coinsin %,.3f ms%n%n", 
     coins.length, (end - start)/1000000d); 
} 

private static double[] dynamic(double... coins) { 
    double[][] table = new double[coins.length + 2][]; 
    for (int i = 0; i < table.length; i++) { 
    table[i] = new double[coins.length + 1]; 
    } 
    table[1][coins.length] = 1.0d; // everything else is 0.0 
    for (int i = 0; i <= coins.length; i++) { 
    for (int j = coins.length - 1; j >= 0; j--) { 
     table[i + 1][j] = coins[j] * table[i][j + 1] + 
      (1 - coins[j]) * table[i + 1][j + 1]; 
    } 
    } 
    double[] ret = new double[coins.length + 1]; 
    for (int i = 0; i < ret.length; i++) { 
    ret[i] = table[i + 1][0]; 
    } 
    return ret; 
} 

Điều này đang làm là xây dựng một bảng hiển thị xác suất mà một chuỗi các đồng xu từ p _i-p _n chứa k đầu.

Để biết giới thiệu sâu hơn về xác suất nhị thức và thảo luận về cách áp dụng lập trình động, hãy xem Coin Tosses, Binomials and Dynamic Programming.

Answer 3

Mã giả:

procedure PROB(n,k,p) 
/* 
    input: n - number of coins flipped 
      k - number of heads 
      p - list of probabilities for n-coins where p[i] is probability coin i will be heads 
    output: probability k-heads in n-flips 
    assumptions: 1 <= i <= n, i in [0,1], 0 <= k <= n, additions and multiplications of [0,1] numbers O(1) 
*/ 

A =()() //matrix 
A[0][0] = 1 // probability no heads given no coins flipped = 100% 

for i = 0 to k                //O(k) 
    if i != 0 then A[i][i] = A[i-1][i-1] * p[i] 
    for j = i + 1 to n - k + i            //O(n - k + 1 - (i + 1)) = O(n - k) = O(n) 
     if i != 0 then A[i][j] = p[j] * A[i-1][j-1] + (1-p[j]) * A[i][j-1] 
     otherwise  A[i][j] = (1 - p[j]) * A[i][j-1] 
return A[k][n] //probability k-heads given n-flips 

tệ nhất trường hợp = O (kn)