Midpoint categorical frequencies have at most one-grid-cell error

Apart from the null event $U=0$, outcome $i$ is returned exactly when $C_{i-1}<U\le C_i$, an interval of length $C_i-C_{i-1}=p_i$. Its uniform probability is the interval length $C_i-C_{i-1}=p_i$, so the ideal law is exactly the specified categorical law.

Put $N=2^b$. For any threshold $C\in [0,1]$, the number of midpoints $(k+1\mathrm{/}2)\mathrm{/}N\le C$ is $\min (N,\max (0,\lfloor NC+1\mathrm{/}2\rfloor ))$. Thus its normalized count differs from $C$ by at most $1\mathrm{/}(2N)$. Applying this to $C_i$ and $C_{i-1}$, the frequency of outcome $i$ is the difference of their cumulative frequencies, so its error from $p_i$ is at most $1\mathrm{/}N=2^{-b}$.

The cumulative and individual bounds in step 1.2 give the stated finite-grid error, while step 1.1 proves the ideal-input clause.

For positive $v\le 1=C_r$, the least admissible index exists. Initially it lies in $[L,H]=[1,r]$. If $v\le C_j$, monotonicity of the cumulative sums puts that index in $[L,j]$; otherwise it lies in $[j+1,H]$. Thus both updates preserve the invariant, and at $L=H$ the returned index is the least admissible one. When the interval contains $n>1$ indices, $j=\lfloor (L+H)\mathrm{/}2\rfloor$ leaves at most $\lceil n\mathrm{/}2\rceil$ indices and uses one cumulative-array comparison. After $k$ updates at most $\lceil r\mathrm{/}{2}^k\rceil$ remain, by induction; at $k=\lceil {\log }_{2}r\rceil$ this is one. When $r=1$ the loop has zero updates. The zero-input branch returns immediately as specified.