Схема Бернуллі#11726

Схема Бернуллі (Розбір)

Випробування Бернуллі — це експеримент з двома можливими наслідками:

Успіх (подія відбувається) з ймовірністю $p$ ,
Невдача (подія не відбувається) з ймовірністю $1 - p$ 1 - p.

Випробування називається "бернуллівським", якщо воно незалежне і ймовірність його успіху залишається сталою протягом усіх випробувань.

Схема випробувань Бернуллі — це серія незалежних випробувань, кожне з яких є випробуванням Бернуллі. Позначимо кількість випробувань через $n$ . У кожному випробуванні ймовірність успіху $p$ та невдачі $1 - p$ 1 - p залишаються незмінними.

Прикладом може служити багаторазове підкидання монети. Якщо нас цікавить, скільки разів випаде орел з $n$ підкидань, то це і буде схема випробувань Бернуллі.

Число успіхів у серії з $n$ випробувань Бернуллі підпорядковується біноміальному розподілу. Нехай $X$ — випадкова величина, яка позначає число успіхів у $n$ випробуваннях. Тоді:

P (X = k) = C_{n}^{k} \cdot p^{k} \cdot (1 - p)^{n - k}

P(X = k) = C_n^k \cdot p^k \cdot (1 - p)^{n - k}

де

$p$ — ймовірність успіху в кожному випробуванні,
$k$ — кількість успіхів з $n$ випробувань.

Доведення. Розглянемо конкретну послідовність випробувань, в якій:

$k$ випробувань успішні (ймовірність успіху $p$ )
$n - k$ n - k випробувань невдалі (ймовірність невдачі $q = 1 - p$ q = 1 - p)

Оскільки випробування незалежні, ймовірність цієї конкретної послідовності дорівнює добутку ймовірностей окремих випробувань:

Щоб отримати рівно $k$ успіхів, необхідно вибрати, у яких саме $k$ місцях вони відбуватимуться. Число таких способів дорівнює числу сполучень $C_{n}^{k}$ C_n^k.

Отже, ймовірність того, що буде рівно $k$ успіхів, дорівнює

P (X = k) = C_{n}^{k} \cdot p^{k} \cdot (1 - p)^{n - k}

P(X = k) = C_n^k \cdot p^k \cdot (1 - p)^{n - k}

Для обчислення значення біноміального коефіцієнта в дійсних числах скористаємося таким прийомом:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}, l n C_{n}^{k} = l n n! - l n k! - l n (n - k)!

C_n^k = {n! \over k! (n - k)!}, \\ ln~C_n^k = ln~n! - ln~k! - ln~(n - k)!

Відомо, що $l n n! = l n (1 \cdot 2 \cdot ... \cdot n) = l n 1 + l n 2 + ... + l n n$ ln~n! = ln~(1 \cdot 2 \cdot ... \cdot n) = ln~1 + ln~2 + ... + ln~n

Значення $l n i!$ запам'ятовуємо в комірках масиву $l f [i]$ . Далі обчислюємо

r es = l n n! - l n k! - l n (n - k)! = l f [n] - l f [k] - l f [n - k],

res = ln~n! - ln~k! - ln~(n - k)! = lf[n] - lf[k] - lf[n - k],

після чого

C_{n}^{k} = e^{r es}

C_n^k = e^{res}

Приклад

У першому тесті проводиться $n = 8$ n = 8 випробувань. Ймовірність настання події $А$ в кожному випробуванні дорівнює $p = 0.3$ p = 0.3. Ми хочемо знайти ймовірність того, що подія $А$ відбудеться рівно $k = 2$ k = 2 рази. Шукана ймовірність дорівнює:

P (X = 2) = C_{8}^{2} \cdot 0. 3^{2} \cdot 0. 7^{6} \approx 0.296475

P(X = 2) = C_8^2 \cdot 0.3^2 \cdot 0.7^6 ≈ 0.296475

Реалізація алгоритму

Оголосимо робочий масив $l f$ , де $l f [i] = l n i! = l n 1 + l n 2 + ... + l n i$ lf[i] = ln~i! = ln~1 + ln~2 + ... + ln~i.

#define MAX 1001
double lf[MAX];

Читаємо вхідні дані.

scanf("%d %d", \&n, \&k);
scanf("%lf", \&p);
q = 1 - p;

Заповнюємо масив $l f$ .

lf[1] = 0;
for (i = 2; i \<= n; i++)
  lf[i] = lf[i - 1] + log(i);

Обчислюємо значення біноміального коефіцієнта $r es = C_{n}^{k}$ res = C_n^k.

res = lf[n] - lf[k] - lf[n - k];
res = exp(res);

Обчислюємо відповідь $r es = C_{n}^{k} \cdot p^{k} \cdot (1 - p)^{n - k}$ res = C_n^k \cdot p^k \cdot (1 - p)^{n - k}.

for (i = 0; i \< k; i++)
  res = res * p;
for (i = 0; i \< n - k; i++)
  res = res * q;

Виводимо відповідь.

printf("%lf\n", res);