Probabilité de l'algorithme Résultats

Question

J'ai un problème de probabilité, que je dois simuler dans un laps de temps raisonnable. Sous une forme simplifiée, je 30 pièces injustes chacune avec une probabilité différente connue. Je veux donc demander des choses comme « quelle est la probabilité que exactement 12 sera la tête? », Ou « quelle est la probabilité que AU MOINS 5 sera queue? ».

Je sais la théorie des probabilités de base, donc je sais que je peux énumérer tous (30 x choisir) possibilités, mais ce n'est pas particulièrement évolutive. Le pire des cas (30 choisissez 15) a plus de 150 millions de combinaisons. Y at-il une meilleure façon d'aborder ce problème du point de vue de calcul?

Toute aide est grandement appréciée, merci! : -)

Answer 1

Vous pouvez utiliser une approche de programmation dynamique.

Par exemple, pour calculer la probabilité de 12 têtes de 30 pièces de monnaie, soit P (n, k) la probabilité qu'il y ait des têtes de k à partir de la première des pièces de monnaie n.

Alors P (n, k) = P p_n * (n - 1, k - 1) + (1 - p_n) * P (n - 1, k)

(ici est p_i la probabilité de la pièce de i'th est la tête).

Vous pouvez maintenant utiliser cette relation dans un algorithme de programmation dynamique. Avoir un vecteur de 13 probabilités (qui représentent P (n - 1, i) pour i dans 0..12). Construire un nouveau vecteur de 13 P (n, i) en utilisant la relation de récurrence ci-dessus. Répétez l'opération jusqu'à n = 30. Bien sûr, vous commencez avec le vecteur (1, 0, 0, 0, ...) pour n = 0 (car sans pièces de monnaie, vous êtes sûr d'obtenir aucune tête).

Le pire des cas en utilisant cet algorithme est O (n ^ 2) plutôt que exponentielle.

Answer 2

Ceci est en fait un problème intéressant. Je me suis inspiré d'écrire un billet de blog à ce sujet couvrant en détail juste contre injuste monnaie jette tout le chemin à la situation de l'OP d'avoir une probabilité différente pour chaque pièce. Vous avez besoin d'une technique appelée programmation dynamique pour résoudre ce problème en temps polynomial.

Général Problème: Vu C , une série de n pièces p ₁ p _n où p _i représente la probabilité des i coin -ème à venir têtes, quelle est la probabilité de k têtes à venir de lancer toutes les pièces?

Ce moyen de résolution de la relation de récurrence suivante:

P ( n , k , C , i ) = < em> p _i x P ( n -1, k -1, C , i 1) + (1- p _i ) x P ( n , k , C , i 1)

Un extrait de code Java qui fait cela est:

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

Ce que cela fait est la construction d'une table qui montre la probabilité qu'une séquence de pièces de p _i p _n contient k têtes.

Pour une introduction plus profonde à la probabilité binomiale et une discussion sur la façon d'appliquer une programmation dynamique jeter un oeil à Coin Tosses, et Binômes de programmation dynamique.

Answer 3

pseudocode:

    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

Le pire cas = O (kn)