TAOCP 3.4.1 Exercise 2

Let $U$ be a random variable uniformly distributed on $[0,1)$, and suppose that $mU$ is interpreted as a random integer between $0$ and $m-1$, namely $U_m = \lfloor mU \rfloor.$ Thus $\Pr{U_m = j} = 1...

taocpmathematicsalgorithmsvolume-2math-medium

Section 3.4.1: Numerical Distributions

Exercise 2. [M16] Assuming that $mU$ is a random integer between 0 and $m - 1$, what is the exact probability that $\lfloor kU \rfloor = r$, if $0 \le r < k$? Compare this with the desired probability $1/k$.

Verified: yes
Solve time: 1m26s

Solution

Let $U$ be a random variable uniformly distributed on $[0,1)$, and suppose that $mU$ is interpreted as a random integer between $0$ and $m-1$, namely

$U_m = \lfloor mU \rfloor.$

Thus $\Pr{U_m = j} = 1/m$ for each integer $0 \le j < m$. We wish to compute the exact probability that

$X = \lfloor kU \rfloor = r,$

where $0 \le r < k$.

We first express $X$ in terms of $U_m$. Write

$X = \left\lfloor k \frac{U_m + V}{m} \right\rfloor,$

where $V = mU - U_m$ is the fractional part of $mU$, so that $0 \le V < 1$. Then $U = (U_m + V)/m$, and

$X = \left\lfloor \frac{k}{m} U_m + \frac{k}{m} V \right\rfloor.$

For fixed $U_m = j$, $0 \le j < m$, the fractional term $(k/m)V$ satisfies $0 \le (k/m)V < k/m$. Therefore, $\lfloor (k/m)U_m + (k/m)V \rfloor$ equals either $\lfloor (k/m) j \rfloor$ or $\lfloor (k/m) j \rfloor + 1$, depending on the value of $V$.

Define $s_j = \lfloor (k/m) j \rfloor$. Then $X = r$ occurs for those $j$ such that either $s_j = r$ or $s_j + 1 = r$. Equivalently, $X = r$ occurs precisely when $j$ satisfies

$\frac{m}{k} r \le j < \frac{m}{k} (r+1). \eqno(1)$

Since $U_m$ is uniform over $0,1,\ldots,m-1$, the probability that $X = r$ is the fraction of integers $j$ in the interval $[m r/k,, m (r+1)/k)$. Denote by $J_r$ the set of integers in this interval:

$J_r = \left{ j \in {0,1,\ldots,m-1} : \frac{m r}{k} \le j < \frac{m (r+1)}{k} \right}.$

Then

$\Pr{X = r} = \frac{|J_r|}{m}. \eqno(2)$

To compute $|J_r|$, observe that the smallest integer in $J_r$ is $\lceil m r/k \rceil$ and the largest integer less than $m(r+1)/k$ is $\lfloor m(r+1)/k \rfloor - 1$. Therefore,

$|J_r| = \left\lfloor \frac{m(r+1)}{k} \right\rfloor - \left\lceil \frac{m r}{k} \right\rceil + 1.$

Substituting into (2) gives the exact probability:

$\Pr{\lfloor kU \rfloor = r} = \frac{\lfloor m(r+1)/k \rfloor - \lceil m r/k \rceil + 1}{m}. \eqno(3)$

This formula shows the discrepancy from the ideal probability $1/k$. When $m$ is an integer multiple of $k$, say $m = qk$, then $\frac{m(r+1)}{k} = q(r+1)$ and $\frac{m r}{k} = qr$, which are integers. In this case, $|J_r| = q$, so that

$\Pr{\lfloor kU \rfloor = r} = \frac{q}{m} = \frac{1}{k},$

matching the desired uniform probability exactly. If $k$ does not divide $m$, the probability differs slightly from $1/k$, but the deviation is at most $1/m$.

This completes the proof.

∎

Notes

The expression (3) is exact for any positive integers $k$ and $m$, and it reduces to the familiar uniform case when $k$ divides $m$. The rounding functions $\lfloor \cdot \rfloor$ and $\lceil \cdot \rceil$ account for the integer lattice structure of the discrete approximation of the uniform distribution.