احتمال خوارزمية النتائج

Question

لدي مشكلة احتمالية ، والتي أحتاج إلى محاكاة في فترة زمنية معقولة. في شكل مبسط ، لدي 30 قطعة نقدية غير عادلة لكل منها احتمال معروف مختلف. ثم أريد أن أسأل أشياء مثل "ما هو احتمال أن يكون 12 رؤوسًا بالضبط؟" ، أو "ما هو احتمال أن يكون 5 ذيول على الأقل؟".

أعلم أن نظرية الاحتمالات الأساسية ، لذلك أعلم أنه يمكنني تعداد جميع احتمالات (30 اختيار x) ، لكن هذا ليس قابلاً للتطوير بشكل خاص. أسوأ حالة (30 اختيار 15) لديها أكثر من 150 مليون مجموعة. هل هناك طريقة أفضل للتعامل مع هذه المشكلة من وجهة نظر حسابية؟

أي مساعدة يحظى بتقدير كبير، وذلك بفضل! :-)

Answer 1

يمكنك استخدام نهج البرمجة الديناميكية.

على سبيل المثال ، لحساب احتمال 12 رأسًا من بين 30 قطعة نقدية ، دع P (N ، K) يكون احتمال وجود رؤوس K من أول عملات معدنية.

ثم p (n ، k) = p_n * p (n - 1 ، k - 1) + (1 - p_n) * p (n - 1 ، k)

(هنا p_i هو احتمال أن تكون عملة ITH هي رؤساء).

يمكنك الآن استخدام هذه العلاقة في خوارزمية البرمجة الديناميكية. لديك ناقل من 13 احتمالات (التي تمثل p (n - 1 ، i) لأني في 0..12). قم بإنشاء متجه جديد من 13 لـ P (n ، i) باستخدام علاقة التكرار أعلاه. كرر حتى n = 30. بالطبع ، تبدأ بالمتجه (1 ، 0 ، 0 ، 0 ، ...) لـ n = 0 (لأنه بدون عملات معدنية ، من المؤكد أنك لن تحصل على رؤوس).

أسوأ حالة باستخدام هذه الخوارزمية هي O (n^2) بدلاً من الأسي.

Answer 2

هذه في الواقع مشكلة مثيرة للاهتمام. لقد ألهمت كتابة منشور مدونة حول هذا الموضوع الذي يغطي بالتفصيل مع Fair vs Coin غير العادلة على طول الطريق إلى وضع OP المتمثل في وجود احتمال مختلف لكل عملة معدنية. تحتاج إلى تقنية تسمى البرمجة الديناميكية لحل هذه المشكلة في وقت متعدد الحدود.

المشكلة العامة: معطى ج, ، سلسلة من ن عملات معدنية ص₁ إلى ص_ن أين ص_أنا يمثل احتمال أنا-العمون القادم رؤساء ، ما هو احتمال ك الرؤوس القادمة من رمي جميع العملات المعدنية؟

هذا يعني حل علاقة التكرار التالية:

ص(ن,ك,ج,أنا) = ص_أنا x ص(ن-1,ك-1,ج,أنا+1) + (1-ص_أنا) x ص(ن,ك,ج,أنا+1)

مقتطف رمز Java الذي يقوم بذلك هو:

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;
}

ما يفعله هذا هو بناء جدول يوضح احتمال تسلسل العملات المعدنية من ص_أنا إلى ص_ن يحتوي ك رؤساء.

للحصول على مقدمة أعمق إلى احتمال ذي الحدين ومناقشة حول كيفية تطبيق البرمجة الديناميكية ، ألق نظرة على إرم العملات المعدنية ، الحدين والبرمجة الديناميكية.

Answer 3

كود مزيف:

    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

أسوأ حالة = o (kn)