Problem understanding a proof 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.
 A: 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.
A: 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\;.$$
