algorithm 키워드 결과 알고리즘의 확률



키워드 검색 알고리즘 (3)

나는 적당한 시간 내에 시뮬레이션 할 확률 문제가있다. 단순화 된 형태로, 나는 각각 다른 확률로 30 개의 불공정 동전을 가지고 있습니다. 그런 다음 정확히 12 명이 머리가 될 확률은 무엇입니까? 또는 "적어도 5 점이 꼬리가 될 확률은 얼마입니까?"와 같은 질문을하고 싶습니다.

나는 기본적인 확률 이론을 안다. 그래서 나는 모든 (30 가지 선택 x) 가능성을 열거 할 수 있다는 것을 안다. 그러나 그것은 특별히 확장 성이 없다. 최악의 경우 (30 개 중 30 개 선택)에는 1 억 5 천만 개가 넘는 조합이 있습니다. 계산상의 관점에서이 문제에 접근하는 더 좋은 방법이 있습니까?

어떤 도움이라도 대단히 감사합니다. :-)


이것은 실제로 흥미로운 문제입니다. 나는 공정한 동전 대 부당한 동전이 각 동전에 대해 다른 확률을 갖는 OP의 상황에 이르기까지 자세하게 다루는 블로그 게시물을 작성하는 데 영감을 받았다. 다항식 시간에이 문제를 풀기 위해 동적 프로그래밍이라는 기술이 필요합니다.

일반적인 문제 : C가 주어지면 일련의 n 개의 동전 p 1 ~ p np ii 번째 동전이 머리 위로 올 가능성을 나타내고, k 머리가 모든 동전을 던질 확률은 얼마인가?

이는 다음과 같은 반복 관계를 풀어야 함을 의미합니다.

P ( n , k , C , i + 1 ) = P i x P ( n -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;
}

이것이하는 일은 p i 에서 p n 까지의 동전이 k 개의 머리를 가질 확률을 보여주는 표를 만드는 것입니다.

이항 확률에 대해 더 자세히 소개하고 동적 프로그래밍을 적용하는 방법에 대한 논의는 Coin Tosses, Binomials 및 Dynamic Programming을 살펴보십시오.


의사 코드 :

    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)


동적 프로그래밍 방식을 사용할 수 있습니다.

예를 들어 30 개의 동전 중 12 개의 확률을 계산하려면 P (n, k)를 첫 번째 n 개의 동전에서 k 개의 머리가 나올 확률이라고합시다.

그러면 P (n, k) = p_n * P (n-1, k-1) + (1 - p_n) * P (n-1, k)

(여기서 p_i는 i 번째 동전이 머리 일 확률입니다.)

이제 동적 프로그래밍 알고리즘에서이 릴레이션을 사용할 수 있습니다. 0.1의 확률로 13 개의 확률 벡터를 구하십시오. (P (n - 1, i)를 나타냅니다. 위의 되풀이 관계를 사용하여 P (n, i)에 대해 13의 새 벡터를 작성하십시오. n = 30이 될 때까지 반복하십시오. 물론 동전이 없으므로 머리가 없어 지므로 n = 0에 대해 벡터 (1, 0, 0, 0, ...)로 시작하십시오.

이 알고리즘을 사용하는 최악의 경우는 지수가 아니라 O (n ^ 2)입니다.





probability-theory