What is the probability?#1571

What is the probability? (Editorial)

Let us consider the game from the perspective of probability theory:

Each throw is independent of the others;
The probability of winning on a single throw is $p$ ;
The probability of failure on a single throw is $1 - p$ 1 - p;
The players take turns in a cycle: $1, 2, ..., n, 1, 2, ...$ 1, 2, ..., n, 1, 2, ...;
The game ends immediately as soon as someone wins.

We are interested in the probability that the $i$ -th player wins.

The fact that the $i$ -th player wins means that:

no one has won before his winning throw;
the winning event occurs on his turn.

Moreover, the $i$ -th player may win:

on his first throw;
on his second throw;
on his third throw;
and so on.

The final probability is equal to the sum of the probabilities of all these cases.

For the $i$ -th player to win on his first turn, two conditions must be satisfied:

The first $i - 1$ i - 1 players do not win. The probability of this event is $(1 - p)^{i - 1}$ (1 - p)^{i - 1}
The $i$ -th player wins. The probability of this event is $p$ .

Since the events are independent, the probability that the $i$ -th player wins on his first turn is equal to

p \cdot (1 - p)^{i - 1}

p \cdot (1 - p)^{i - 1}

The $i$ -th player wins on his second turn if:

All $n$ players make one throw each and lose: $(1 - p)^{n}$ (1 - p)^n
The first $i - 1$ i - 1 players lose again in the second round. The probability of this event is $(1 - p)^{i - 1}$ (1 - p)^{i - 1}.
The $i$ -th player wins. The probability of this event is $p$ .

The probability that the $i$ -th player wins on his second turn is equal to

p \cdot (1 - p)^{i - 1} \cdot (1 - p)^{n}

p \cdot (1 - p) ^ {i - 1} \cdot (1 - p)^n

By reasoning in the same way, we obtain that the probability for the $i$ -th player to win on his $k$ -th turn is equal to

p \cdot (1 - p)^{i - 1} \cdot (1 - p)^{n (k - 1)}

p \cdot (1 - p)^{i - 1} \cdot (1 - p)^{n(k - 1)}

Now it remains to sum the obtained probabilities. The overall probability that the $i$ -th player wins is equal to

p \cdot (1 - p)^{i - 1} (1 + (1 - p)^{n} + (1 - p)^{2 n} + .. + (1 - p)^{k n} + ...)

p \cdot (1 - p)^{i-1} (1 + (1 - p)^n + (1 - p)^{2n} + .. + (1 - p)^{kn} + ...)

The expression in parentheses is an infinite geometric progression with first term equal to $1$ and common ratio $(1 - p)^{n}$ (1 - p)^n. The winning probability is equal to

p \cdot (1 - p)^{i - 1} \frac{1}{1 - ( 1 - p ) ^{n}} = \frac{p \cdot ( 1 - p ) ^{i - 1}}{1 - ( 1 - p ) ^{n}}

p \cdot (1 - p)^{i - 1} \frac{1}{1-(1-p)^n} = \frac{p \cdot (1 - p)^{i - 1}}{1 - (1 - p)^n}

It should be noted separately that when $p = 0$ p = 0, the answer is $0$ .

Algorithm implementation

Read the input data.

scanf("%d",&t);
while(t--)
{
  scanf("%d %lf %d",&n,&p,&i);

If the probability $p$ is equal to $0$ , print $0$ .

  if (p == 0) printf("0\n");
  else
  {

Otherwise, compute the required probability using the formula given above. Print the result with $4$ digits after the decimal point.

    res = p * pow(1 - p,i - 1) / (1 - pow(1 - p,n));
    printf("%.4lf\n",res);
  }
}