2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Shouldn't the sum start with $j=0$ (or contain $j-1$ in the exponent)? $\endgroup$ – Peter Košinár Jun 2 '13 at 6:35
  • $\begingroup$ @BrianM.Scott: Right, edited. $\endgroup$ – Gigili Jun 2 '13 at 6:38
  • $\begingroup$ @PeterKošinár: You'r right, the second sum should start from $j=0$. $\endgroup$ – Gigili Jun 2 '13 at 6:39
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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\;.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.