Problem understanding a proof

Question

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there's this example:

Choosing an integer $a \in_R \{0,\dots,n\}$ using random bits.

We assume that we are given an infinite sequence of independent random bits. To choose a random integer $a \in_R {0, . . . , n}$ we use the following procedure (we suppose that $2^{k−1} ≤ n < 2^k$ ),
read $k$ random bits $b_1, . . . , b_k$ from our sequence. If $a = b_1, \dots, b_k$ belongs to $\{0, . . . , n\}$ (where a is encoded in binary)
then output a
else repeat.
On a single iteration the probability that an output is produced is $$Pr[a \in \{0, . . . , n\}] = \dfrac{n + 1}{2^k} > \frac 12$$ Thus the expected number of iterations before an output occurs is less than two and, with probability at least $1 − 1/2^{100}$, an output occurs within a hundred iterations. Moreover when an output occurs it is chosen uniformly at random from $\{0, . . . , n\}$. Since if $m \in \{0, . . . , n\}$ and we let $a_j$ denote the value of a chosen on the j-th iteration of this procedure then $$Pr[\text{Output is m}] \\= \Sigma_{j=1}^{\infty}Pr[a_j = m \text { and } a_1, . . . , a_{j−1} \geq n + 1]\\= \frac{1}{2^k}\Sigma_{j=0}^{\infty}(1-\dfrac{n+1}{2^k})^j \tag{1}\\= \frac{1}{n +1}$$

I have problem understanding two things:

• Why is this: "Thus the expected number of iterations before an output occurs is less than two"?
• The formul tagged $(1)$ (the third and fourth line)

Thank you.

Answer 1

In case of independent trials, the expected number of repetitions is equal to reciprocal of the probability of success. Since the probability is greater than $\frac{1}{2}$, the expected number of iterations is smaller than $2$.

The formula (1) considers the possibilities of output $m$ being produced eventually. The variable $j$ in the sum goes over possible numbers of steps it could have taken to produce this output. In order to produce $m$ in $j$-th step, all the previous steps must have produced a "bad" number (one which is strictly greater than $n$ and thus rejected) and the last one must have produced precisely our desired number $m$. The rejection probability is $(1-\frac{n+1}{2^k})$ (complement of probability of success) and the probability of getting a specific $k$-bit string is $\frac{1}{2^k}$. Put together, we get a sum $$\sum_{j=1}^\infty \frac{1}{2^k}\left(1-\frac{n+1}{2^k}\right)^{j-1}$$ which can easily be seen to be equal to your sum. Since it's just geometric series, calculating the sum is easy and the $2^k$ terms cancel out.

Answer 2

Peter’s covered the second question thoroughly; here’s a more detailed look at the first question.

Let $X_k=1$ if the first $k$ iterations produce no output and $0$ otherwise, and let $X=\sum_{k\ge 1}X_k$; then the $(X+1)$-st iteration is the first to produce output. Let $p=\frac{n+1}{2^k}$; then

$$\Bbb E(X_k)=\Bbb P[X_k=1]=(1-p)^k\;.$$

By linearity of expectation

$$\Bbb E(X)=\sum_{k\ge 1}\Bbb E(X_k)=\sum_{k\ge 1}(1-p)^k=\frac{1-p}{1-(1-p)}=\frac{1-p}p=\frac1p-1\;,$$

so

$$\Bbb E(X+1)=\left(\frac1p-1\right)+1=\frac1p<2\;.$$