Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have here 2 methods for generating a random number, and I need to calculate the expected number of tosses for each method. In each, we let n = log(N) Ne be the bit-length of N and let B(n-1)B(n-2)....B(0) be the binary representation of N (so B(n-1) = 1) Method 1:

For i = n  1 down to 0, do {
if B(i) = 1 OR there is a j > i such that C(j) < B(j),
then use a coin toss to generate a new C(i) [0 or 1].
Otherwise, set C(i) = 0
}
Output C(n-1)C(n-2).....C(1)C(0)

Method 2:

Use n + 10 coin tosses to generate a random number M between 0 and
2^(2n+10) - 1. 
If M < N * (2^(2n+10) / N) - output M, 
otherwise repeat.

Thanks in advance

share|improve this question
1  
What have you tried? Where are you stuck? –  Did Oct 31 '12 at 15:46
    
I tried to understand what is needed to calculate here, and got stuck in understanding it....I basically need help from the beginning of it, please –  DanielY Oct 31 '12 at 15:49
    
This is homework, hence you probably have a kind of textbook defining the notions you are led to use. Which text is this? –  Did Oct 31 '12 at 16:01
    
it's academy homework, no textbook just lecture notes –  DanielY Oct 31 '12 at 16:09
    
My question still applies. (And please use @ to notify your comments.) –  Did Oct 31 '12 at 20:23

1 Answer 1

up vote 1 down vote accepted

Fix some positive integer $N$ and introduce:

  • the bit-length $n$ of $N$, that is, the unique positive integer $n$ such that $2^{n-1}\leqslant N\lt2^{n}$,
  • the binary expansion $(B_k)_{0\leqslant k\leqslant n-1}$ of $N$, that is, the unique $B_k$ in $\{0,1\}$, $B_{n-1}=1$, such that $N=B_0+2B_1+\cdots+2^{n-1}B_{n-1}$,
  • the number $L$ of leading ones in the binary expansion of $N$, defined by $B_{n-k}=1$ for every $1\leqslant k\leqslant L$ and $B_{n-L-1}=0$,
  • the length $K$ of the first block of zeroes after the $L$ leading ones, that is, $K=0$ if $L=n$ and, otherwise, $B_{n-L-i}=0$ for every $1\leqslant i\leqslant K$ and $B_{n-L-K-1}=1$,
  • the integer $U=B_0+2B_1+\cdots+2^{n-L-K-1}B_{n-L-K-1}$ which is the number $N$ stripped of its leading block of ones and of its next block of zeroes.

For example, if $N=1100010010$, then $n=10$, $L=2$, $K=3$ and $U=10010$.

Call $T$ the mean number of tosses needed in Method 1. The first zero happens at toss $k$ with probability $2^{-k}$. If $k\leqslant L$, one uses $n$ tosses. If the first $L$ tosses are ones, the $K$ next digits need no toss and one is left with the tosses needed for $U$. Hence, $$ T=(1-2^{-L})n+2^{-L}(L+T_{U}), $$ that is, $$ n-T=2^{-L}(n-L-T_{U})=2^{-L}K+2^{-L}(n_{U}-T_{U}), $$ where $n_U$ and $T_U$ are based on $U$ as $n$ and $T$ are based on $N$. If $N=1^{L_1}0^{K_1}1^{L_2}0^{K_2}1^{L_3}\ldots$, one gets $$ T_N=n-2^{-L_1}K_1-2^{-L_1-L_2}K_2-2^{-L_1-L_2-L_3}K_3-\cdots $$ For example, if $N=1100010010$, then $T_N=10-2^{-2}3-2^{-3}2-2^{-4}1=9-\frac1{16}$.

On the other hand, Method 2 as written in the post is quite odd hence I suggest to consider Method 2 below:

Use n coin tosses to generate a random number M between 0 and 2^n - 1 
If M < N then output M
Otherwise repeat

The mean number $R$ of tosses needed in this (revised version of) Method 2 is the number $n$ of tosses needed for one pass times the mean number of passes. Each pass is succesful with probability $N/2^{n}$ hence $R=n2^{n}/N$.

One sees that $n\lt R\leqslant2n$ and $T\leqslant n$ (the only case when $T=n$ being when $N=2^{n}-1$). Hence $T\lt R$, that is, Method 1 is more effective than (the revised version of) Method 2, for every positive number $N$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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