Q. 3.17 - A First Course in Probability

Question

Suppose that $n$ independent trials are performed, with trial $i$ being a success with probability $1/(2i + 1)$. Let $P_n$ denote the probability that the total number of successes that result is an odd number.

(a) Find $P_n$ for $n = 1, 2, 3, 4, 5$.

(b) Conjecture a general formula for $P_n$.

(c) Derive a formula for $P_n$ in terms of $P_n-1$.

(d) Verify that your conjecture in part (b) satisfies the recursive formula in part (c). Because the recursive formula has a unique solution, this then proves that your conjecture is correct. 

Step-by-Step Solution

Answer

(a) The value of $n=1$ is $P_1=\frac{1}{3}$, $n=2$ is $P_2=\frac{2}{5}$, $n=3$ is $P_3=\frac{3}{7}$, $n=4$ is $P_4=\frac{4}{9}$and $n=5$ is $P_5=\frac{5}{11}$

(b) A general formula for $P_n$ is equal to $P_n=\frac{n}{2n+1}$

(c) A formula for $P_n$ in terms of $P_{n+1}$is $P_{n+1}=P_n\left(1-P\left(S_{n+1}\right)\right)+\left(1-P_n\right)P\left(S_{n+1}\right)$

(d) $P_{n+1}$ satisfy the formula. Therefore, this explicit formula is a solution of recursion

Step1: Derive the values of P 1     , P 2   ,   P 3 (part a)

Given:

Bernoulli trials are done in a specific order.

$S_n$-event that the $n$-th experiment is successful

$P_n$ is the probability of achieving an odd number of successes in n trials.

The sum of probability of mutually exclusive occurrences described by $S_1,S_1^c,S_2,S_2^c,S_3,\dots$ is pi, $i=1,2,3,4,5,...$

$P_1=P\left(S_1\right)=\frac{1}{2\times 1+1}$

In the second equality, use independence.

$P_2=P\left(S_1{S}_2^c\right)+P\left(S_1^c{S}_2\right)$

$=P\left(S_1\right)P\left(S_2^c\right)+P\left(S_1^c\right)P\left(S_2\right)$

$=\frac{1}{3}\times \left(1-\frac{1}{2\times 2+1}\right)+\left(1-\frac{1}{3}\right)\times \frac{1}{2\times 2+1}$

$=\frac{1}{3}\times \frac{4}{5}+\frac{2}{3}\times \frac{1}{5}$

$=\frac{2}{5}$

If we separate this event based on whether or not  $S_3$occurred, $S_3\to$ is an odd number of successes in the first two experiments, whereas $S_3^c\to$ is an even number of successes in the first two experiments.

$P_3=P\left(S_1{S}_2^c{S}_3^c\right)+P\left(S_1^c{S}_2{S}_3^c\right)+P\left(S_1{S}_2{S}_3\right)+P\left(S_1^c{S}_2^c{S}_3\right)$

$=P\left(S_1\right)P\left(S_2^c\right)P\left(S_3^c\right)+P\left(S_1^c\right)P\left(S_2\right)P\left(S_3^c\right)+P\left(S_1\right)P\left(S_2\right)P\left(S_3\right)+P\left(S_1^c\right)P\left(S_2^c\right)P\left(S_3\right)$

$=\left[P\left(S_1\right)P\left(S_2^c\right)+P\left(S_1^c\right)P\left(S_2\right)\right]P\left(S_3^c\right)+\left[P\left(S_1\right)P\left(S_2\right)+P\left(S_1^c\right)P\left(S_2^c\right)\right]P\left(S_3\right)$

$=\frac{2}{5}\times \left(1-\frac{1}{2\times 3+1}\right)+\left(1-\frac{2}{5}\right)\times \frac{1}{2\times 3+1}$

$=\frac{2}{5}\times \frac{6}{7}+\frac{3}{5}\times \frac{1}{7}$

$=\frac{3}{7}$

Step2: Derive the values of P 4 , P 5 (part a)

$P_4$ and $P_5$ in a smaller package

$P_4=P$ ( odd number of successes in the first $3$experiments $\cap S_4^c$) $+$$P$ (odd number of successes in the first $3$ experiments $\cap S_4^{}$)

$=\frac{3}{7}\times \left(1-\frac{1}{2\times 4+1}\right)+\left(1-\frac{3}{7}\right)\times \frac{1}{2\times 4+1}$

$=\frac{3}{7}\times \frac{8}{9}+\frac{4}{7}\times \frac{1}{9}$

$=\frac{4}{9}$

$P_5=P$ (odd number of successes in the first 4 experiments $\cap S_5^c$) $+P$(odd number of successes in the first $4$ experiments $\cap S_5^{}$)

$=\frac{4}{9}\times \left(1-\frac{1}{2\times 5+1}\right)+\left(1-\frac{4}{9}\right)\times \frac{1}{2\times 5+1}$

$=\frac{4}{9}\times \frac{10}{11}+\frac{5}{9}\times \frac{1}{11}$

$=\frac{5}{11}$

Step3: Find the formula for P n and P n + 1 (part b and part c)

a formula is true for the above probability is

$P_n=\frac{n}{2n+1}$

$P_{n+1}=P_n\left(1-P\left(S_{n+1}\right)\right)+\left(1-P_n\right)P\left(S_{n+1}\right)$

This is demonstrated by separating the event of an odd number of successes from the event $S_{n+1}$.

The first n attempts in an odd number of successes ($P_n$) are called $S_{n+1}$.

$S_{n+1}^c$ in the first $n$ attempts with an even number of successes $1-P_n$.

Step4: Verify conjecture in part (b) satisfies the recursive formula in part (c) (part d)

Substitute $P_{n+1}=\frac{n}{2n+1}$ into recursion

$P_{n+1}=\frac{n}{2n+1}\times \left(1-\frac{1}{2(n+1)+1}\right)+\left(1-\frac{n}{2n+1}\right)\times \frac{1}{2(n+1)+1}$

$=\frac{n}{2n+1}\times \frac{2(n+1)}{2(n+1)+1}+\frac{n+1}{2n+1}\times \frac{1}{2(n+1)+1}$

$=\frac{n\times 2(n+1)+(n+1)}{(2n+1)\left[2\right(n+1)+1]}$

$=\frac{n+1}{2(n+1)+1}$

Because $P_{n+1}$ meet the formula, this explicit formula is a recursive formula solution.

This is the only recursive formula solution.