Question

On page 38, we claimed that since about a $\frac{\mathbf{1}}{\mathbf{n}}$fraction of n-bit numbers are prime, on average it is sufficient to draw $\mathit{O}\left(n\right)$random n -bit numbers before hitting a prime. We now justify this rigorously. Suppose a particular coin has a probability p of coming up heads. How many times must you toss it, on average, before it comes up heads? (Hint: Method 1: start by showing that the correct expression is$\mathbf{\sum }_{\mathbf{i}\mathbf{=}\mathbf{1}}^{\mathbf{\infty }}\mathit{i}\mathbf{(}\mathbf{1}\mathbf{-}\mathit{p}{\mathbf{)}}^{\mathbf{i}\mathbf{-}\mathbf{1}}\mathbf{}\mathit{p}$ . Method 2: if E is the average number of coin tosses, show that $\mathbf{E}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{(}\mathbf{1}\mathbf{-}\mathbf{p}\mathbf{)}\mathbf{E}\mathbf{}$).

Short answer

$\frac{1}{p}$times the coin must be tossed on average before it comes up heads.

Step-by-step solution

Explain the given information

Consider that,P is the Probability of a coin to show up heads. Let,X be the number of times the coin should be tossed before outcome is head. The following equation is used to find the average number of coin tossed:

$\mathrm{E}\left(\mathrm{X}\right)=\sum _{\mathrm{I}=1}^{\infty }\mathrm{i}\times \mathrm{P}\left(\mathrm{i}\right)$

Calculate, how may time the coin must be tossed on average, before it comes up heads.

Consider that $\left(i-1\right)$times the coins were thrown , and the $\mathit{i}$th throwis a head. The probability of this event occurring is ,

$p\left(i\right)={\left(1-p\right)}^{i-1}p$

The number of time the coin must be tossed on average can be calculated as follows,

$$\begin{gathered} \mathrm{E}=\sum _{\mathrm{i}=1}^{\infty }\mathrm{i}\times \mathrm{P}\left(\mathrm{I}\right) \\ E=\sum _{\mathrm{i}=1}^{\infty }\mathrm{i}{\left(1-\mathrm{p}\right)}^{\mathrm{i}-1}\mathrm{p} \\ \left(1-\mathrm{p}\right)E=\sum _{\mathrm{i}=1}^{\infty }i{\left(1-\mathrm{p}\right)}^{\mathrm{i}}p \end{gathered}$$

Simplify further,

localid="1659237715633" $$\begin{gathered} \mathrm{E}-(1-\mathrm{p})\mathrm{E}=\mathrm{p}+\sum _{\mathrm{i}=1}^{\infty }{\left(1-\mathrm{p}\right)}^{\mathrm{i}}\mathrm{p} \\ =\mathrm{p}+\frac{(1-\mathrm{p})\mathrm{p}}{\mathrm{p}} \\ =1 \end{gathered}$$

Find as follows,

$\begin{array}{l}\mathrm{E}-\left(1-\mathrm{p}\right)\mathrm{E}=1\\ \mathrm{E}-\mathrm{E}+\mathrm{pE}=1\\ \mathrm{pE}=1\\ \mathrm{E}=\frac{1}{\mathrm{p}}\end{array}$

Therefore, $\frac{1}{p}$times the coin must be tossed on average before it comes up heads.