1
$\begingroup$

I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $N$ (with $p$ as the probability of success). Basically, the idea is to generate a uniformly distributed random variable $U$ in $[0,1]$. Then, we can apply a simple formula $N = \left\lceil\frac{\ln(U)}{\ln(1-p)}\right\rceil$.

Additionally, Professor Knuth mentions a special case when $p=1/2$. Then, the aforementioned formula transforms into $N = \left\lceil -\log_2 U \right\rceil$. And then he states that N is simply "one more than the number of leading zero bits in the binary representation of $U$. I'm confused by the last statement since I tried different interpretations of this statement and nothing gives the correct result:

  1. Let's interpret the statement as it is. We consider the binary representation of real number $U$. On modern machines, this is either float or double. If we take float, then we have 1 bit for sign and then 8 bits for exponent. If we consider $U=0.25$ and $U=0.5$, we will see that the first 8 bits of their corresponding binary representations are $7d$ and $7e$, respectively. Binary representation have the same number of leading zeros, although $\log_2(1/0.25) \not= \log_2(1/0.5)$.

  2. Let's assume that Knuth means binary representation of $\left\lceil 1/U \right \rceil$. Then, $\left\lceil \log_2 \left\lceil 1/U \right \rceil \right \rceil$ is exactly what we need. But $\left\lceil \log_2(x) \right \rceil = 32 - \mathrm{nlz}(x-1)$ for 32-bit integer, where $\mathrm{nlz}$ is the number of leading zeros. So this is again not what is originally proposed by the author.

Maybe you understand what was meant by Professor Knuth? Could you please explain it? Thanks in advance!

$\endgroup$
2
$\begingroup$
  • If $1/2 \leq U < 1$ then $\lceil -\log_2 U \rceil = 1$.
  • If $1/4 \leq U < 1/2$ then $\lceil -\log_2 U \rceil = 2$.
  • If $1/8 \leq U < 1/4$ then $\lceil -\log_2 U \rceil = 3$.

And so on.

Now,

  • $1/2 \le U < 1$ if the binary expansion of $U$ starts $0.1$.
  • $1/4 \le U < 1/2$ if the binary expansion of $U$ starts $0.01$.
  • $1/8 \le U < 1/4$ if the binary expansion of $U$ starts $0.001$.
$\endgroup$
1
  • $\begingroup$ Thank you. Although I think the words "binary representation" is confusing. Only when you wrote binary expansion with example I understood what was meant. $\endgroup$ – rbtrht May 30 at 23:30

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.