On page 29, we claimed that since about a 1/n fraction of n-bit numbers are prime, on aver...

On page 29, we claimed that since about a 1/n fraction of n-bit numbers are prime, on average it is sufficient to draw O (n) 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 . Method 2: if E is the average number of coin tosses, show that E = 1 + (1 − p) E.)