Bernoulli scheme#11726

Bernoulli scheme (Editorial)

A Bernoulli trial is an experiment with two possible outcomes:

Success (the event occurs) with probability $p$ ,
Failure (the event does not occur) with probability $1 - p$ 1 - p.

A trial is called "Bernoulli" if it is independent and the probability of success remains constant throughout all trials.

The Bernoulli trial scheme is a series of independent trials, each of which is a Bernoulli trial. Let the number of trials be denoted by $n$ . In each trial, the probability of success is $p$ and the probability of failure is $1 - p$ 1 - p, and these probabilities remain constant.

An example could be repeatedly flipping a coin. If we are interested in how many times heads will appear out of $n$ flips, this would represent a Bernoulli trial scheme.

The number of successes in a series of $n$ Bernoulli trials follows a binomial distribution. Let $X$ be a random variable representing the number of successes in $n$ trials. Then:

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}

where

$p$ is the probability of success in each trial,
$k$ is the number of successes out of n trials.

Proof. Consider a specific sequence of trials in which:

$k$ trials are successes (with success probability $p$ )
$n - k$ n - k trials are failures (with failure probability $q = 1 - p$ q = 1 - p)

Since the trials are independent, the probability of this particular sequence is equal to the product of the probabilities of the individual trials:

To obtain exactly $k$ successes, we need to choose the $k$ positions in which they will occur. The number of such choices is given by the binomial coefficient $C_{n}^{k}$ C_n^k.

Therefore, the probability of having exactly $k$ successes is

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}

To compute the value of the binomial coefficient with real numbers, we'll use the following approach:

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)!

It is known that $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

Store the values of $l n i!$ in the cells of an array $l f [i]$ . Then we calculate

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],

After that

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

C_n^k = e^{res}

Example

In the first test, $n = 8$ n = 8 trials are conducted. The probability of event $A$ occurring in each trial is $p = 0.3$ p = 0.3. We want to find the probability that event A occurs exactly $k = 2$ k = 2 times. The desired probability is:

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

Algorithm implementation

Declare an array $l f$ , where $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];

Read the input data.

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

Fill the array $l f$ .

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

Compute the value of the binomial coefficient $r es = C_{n}^{k}$ res = C_n^k.

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

Compute the answer $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;

Print the answer.

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