Finite bit random streams and variate generation

Among the $N+1$ states $s_0,\dots ,s_N$, two must be equal, so choose $0\le i<j\le N$ with $s_i=s_j$. Put $\mu =i$ and $p=j-i$. Applying the same transition to equal states repeatedly gives $s_{n+p}=s_n$ for every $n\ge i$, and $\mu +p=j\le N$.

If $T$ is bijective, its $i$-fold iterate is injective. Applying that injectivity to $T^i(s_0)=T^j(s_0)$ gives $s_0=T^{j-i}(s_0)=s_p$. Repeated application of $T$ yields $s_{n+p}=s_n$ from $n=0$, and applying $g$ gives the same output period.

By [F1], every specified pattern on $n$ distinct coordinates has probability $2^{-n}$. Thus $K_{s,n}$ is uniform on $\{0,\dots ,2^n-1\}$. The events that the first $m$ bits after position $n$ are all zero, or all one, decrease to the corresponding constant-tail events and have probabilities $2^{-m}$. By [F4], both constant-tail events have probability zero. The partial sums defining each $U_s$ are measurable and increase to $U_s$ by [F6].

Fix a dyadic threshold $t=k{2}^{-n}$ with $0\le k\le 2^n$. If $K_{s,n}<k$, then $U_s\le t$; if $K_{s,n}>k$, then $U_s>t$; if $K_{s,n}=k$, then $U_s\le t$ only on the null event $T_{s,n}=0$. Hence $\mathbb{P}(U_s\le k{2}^{-n})=k{2}^{-n}$. For an arbitrary $t\in [0,1]$, dyadic lower and upper approximations differ by at most $2^{-n}$, so monotonicity of the CDF and passage to the limit give $\mathbb{P}(U_s\le t)=t$. Outside $[0,1]$ the CDF is $0$ or $1$.

For finitely many streams and dyadic thresholds $t_s=k_s{2}^{-n}$, the joint event ${\bigcap }_s\{U_s\le t_s\}$ differs by a null set from the event that every prefix integer $K_{s,n}<k_s$. Injectivity within each sequence and pairwise disjointness of their ranges make all prefix coordinates distinct. By [F2] these coordinate bits are independent and by [F1] each is fair, so the probability that each stream's prefix integer is below $k_s$ is the product ${\prod }_s(k_s{2}^{-n})$.

For arbitrary thresholds $t_s\in [0,1]$, dyadic lower and upper approximations squeeze the joint probability between products converging to ${\prod }_s{t}_s$. Thus the joint CDF equals the product-uniform CDF. The lower rectangles ${\prod }_s[0,t_s]$, including the whole cube, are closed under intersections. They generate each coordinate slab $\{x:x_s\le t\}$ by taking the other thresholds to be $1$; complements and finite intersections then give the intersections of the cube with all rational half-open boxes (thresholds outside $[0,1]$ give empty or full slabs). By [F7] these generate the relative Borel sigma-algebra of the cube. Both laws have total mass one there, a finite-measure exhaustion. Thus [F5] identifies the joint law with the product-uniform law. In particular every Borel rectangle has the product of its marginal probabilities, so the rectangle criterion [F3] gives independence of the generated sigma-algebras.

By the upper-tail limit in [F1], some real $b$ has $F(b)>u$, so $S_u$ is nonempty. By the lower-tail limit, some real $a$ has $F(a)<u$; monotonicity then gives $F(y)<u$ for all $y\le a$, so $S_u$ is bounded below. Fact [F2] gives a finite infimum $Q(u)$.

If $u\le F(x)$, then $x\in S_u$, hence $\inf S_u\le x$.

Conversely, suppose $Q(u)\le x$. For every $\epsilon >0$, the definition of infimum gives some $y\in S_u$ with $y<Q(u)+\epsilon \le x+\epsilon$. Monotonicity gives $F(x+\epsilon )\ge F(y)\ge u$. Right continuity at $x$ as $\epsilon \downarrow 0$ yields $F(x)\ge u$.

Steps 2.1 and 2.2 prove the equivalence, and step 1.1 proves the required well-definedness.

By [F7]–[F8], $r(u)=\sqrt{-2\log u}$ is positive on $(0,1)$, with inverse $u=e^{-r^2\mathrm{/}2}$ for $r>0$. By [F9], the angles $2\pi v$ for $0<v<1$ parametrize the unit circle with $(1,0)$ removed exactly once. Thus $T$ is bijective onto $D$, with inverse $G$. The scalar derivatives give $r^{\mathrm{\prime }}(u)=-1\mathrm{/}(ur(u))$, so $T$ is $C^1$ and $\det DT(u,v)=2\pi r(u)r^{\mathrm{\prime }}(u)=-2\pi \mathrm{/}u\mathrm{\ne }0$. The local inverse theorem [F9], together with global bijectivity, makes $G$ a $C^1$ inverse on $D$, with $\mathrm{\mid }\det DG(x,y)\mathrm{\mid }=e^{-(x^2+y^2)\mathrm{/}2}\mathrm{/}(2\pi )$.

For every nonnegative Borel $h$ on $D$, [F6] makes $h\circ T$ Borel. Apply [F1] to $G:D\to (0,1{)}^2$ with integrand $h\circ T$ on its target. Since $(U,V)$ has product Lebesgue law, this gives $\mathbb{E}[h(Z)]={\int }_{D}h(x,y)g(x,y)dxdy$. The omitted nonnegative $x$-axis is Borel and null by [F2], and $Z$ always lies in $D$, so $g$ is the density on all of ${\mathbb{R}}^2$.

By [F5], the pushforward law has total mass one, so its density integrates to $1$. By [F3] and the exponential addition law [F8], writing $A={\int }_{\mathbb{R}}{e}^{-t^2\mathrm{/}2}dt\in (0,\mathrm{\infty }]$, we have $1=(2\pi {)}^{-1}{A}^2$. Positivity of the integrand gives $A>0$, and the equality forces $A<\mathrm{\infty }$ and $A=\sqrt{2\pi }$. Therefore $g(x,y)=\varphi (x)\varphi (y)$ with each factor integrating to $1$. For arbitrary Borel sets $A,B\subseteq \mathbb{R}$, [F3] applied to ${\mathbf{1}}_A(x){\mathbf{1}}_B(y)\varphi (x)\varphi (y)$ gives $\mathbb{P}(Z_1\in A,Z_2\in B)=({\int }_A\varphi )({\int }_B\varphi )$. Taking $B=\mathbb{R}$ or $A=\mathbb{R}$ identifies the marginal probabilities. Thus the Borel-rectangle factorization criterion [F4] proves independence, with the stated marginal densities.

For $r\ge 0$, monotonicity and the inverse identities [F7]–[F8] give $\{R>r\}=\{U<e^{-r^2\mathrm{/}2}\}$; uniformity gives probability $e^{-r^2\mathrm{/}2}$, also at $r=0$. Pointwise, $R^2={\int }_0^{\mathrm{\infty }}2t{\mathbf{1}}_{\{t<R\}}dt$. By [F3], $\mathbb{E}{R}^2={\int }_0^{\mathrm{\infty }}2t{e}^{-t^2\mathrm{/}2}dt=2$, using the substitution $s=t^2\mathrm{/}2$.

The first $b$ independent fair bits give each of the $2^b$ binary prefixes probability $2^{-b}$, so $K_b$ is uniform on the stated integer set. Write the remaining binary tail as $T_b={\sum }_{j\ge 1}{B}_{b+j}{2}^{-j}\in [0,1]$. Then $U=K_b{2}^{-b}+2^{-b}{T}_b$, while $U_b=K_b{2}^{-b}+2^{-b-1}$, hence $\mathrm{\mid }U-U_b\mathrm{\mid }=2^{-b}\mathrm{\mid }{T}_b-1\mathrm{/}2\mathrm{\mid }\le 2^{-b-1}$.

The displayed coupling gives $W_1(\mathcal{L}(U),\mathcal{L}(U_b))\le \mathbb{E}\mathrm{\mid }U-U_b\mathrm{\mid }\le {\delta }_b$ by the infimum definition of $W_1$. For non-strict CDFs, $\{U\le x-{\delta }_b\}\subseteq \{U_b\le x\}\subseteq \{U\le x+{\delta }_b\}$; for strict CDFs, $\{U<x-{\delta }_b\}\subseteq \{U_b<x\}\subseteq \{U<x+{\delta }_b\}$. Since both uniform CDFs equal the clipped identity by [A1], these inclusions bound each absolute discrepancy by ${\delta }_b$.

The law of $U_b$ is supported on its finite midpoint grid, which has probability $1$ under $U_b$ and probability $0$ under the continuous uniform law of $U$. By [F2], this event gives $d_{\mathrm{T}\mathrm{V}}(\mathcal{L}(U),\mathcal{L}(U_b))=1$, the maximal possible value.

For $m\ge 1$, let $S_m={\sum }_{j=0}^{m-1}{a}^j$. Induction on $m$ in the affine recurrence gives $x_m\equiv a^m{x}_0+c{S}_m(\mathrm{m}\mathrm{o}\mathrm{d}{2}^w)$, and the same formula holds from any starting state.

For every $k\ge 0$, $a^{2^k}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{k+2})$. The base case is $a\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$. If $a^{2^k}=1+q{2}^{k+2}$, then squaring gives $a^{2^{k+1}}=1+q{2}^{k+3}+q^2{2}^{2k+4}$, whose difference from $1$ is divisible by $2^{k+3}$.

Write $S_{2^k}=2^k{q}_k$. For $k=0$, $q_0=1$ is odd. The identity $S_{2^{k+1}}=S_{2^k}(1+a^{2^k})$ and $a^{2^k}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$ show that $(1+a^{2^k})\mathrm{/}2$ is odd; hence $q_{k+1}=q_k(1+a^{2^k})\mathrm{/}2$ is odd.

For every $0\le k<w$, the affine iterate in step 1.1 and facts from steps 2.1 and 3.1 give $x_{2^k}-x_0\equiv (a^{2^k}-1)x_0+c{S}_{2^k}\equiv 2^k(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{k+1})$. Indeed, the first summand is divisible by $2^{k+2}$, while $S_{2^k}=2^k{q}_k$ with $q_k$ odd and $c$ odd; thus a return at $2^k$ is impossible modulo $2^{k+1}$.

Taking $k=w$ in the affine iterate from step 1.1 shows $x_{2^w}\equiv x_0(\mathrm{m}\mathrm{o}\mathrm{d}{2}^w)$: the first summand $(a^{2^w}-1)x_0$ is divisible by $2^{w+2}$ and $c{S}_{2^w}$ by $2^w$. Thus a least positive return time $d$ exists.

This least return time divides $2^w$. Indeed, write $2^w=qd+r$ with $0\le r<d$. Determinism and $x_d=x_0$ imply $x_{n+d}=x_n$ for all $n\ge 0$, so $x_{2^w}=x_r$. Since $x_{2^w}=x_0$, minimality of $d$ forces $r=0$, hence $2^w=dh$ for some positive integer $h$. By [F3], factor $d$ and $h$ into primes; their combined list is a prime factorization of $2^w$, whose prime list consists of $w$ copies of the prime $2$. Uniqueness in [F3] implies every prime factor of $d$ is 2, so $d=2^j$ for some $0\le j\le w$. If $j<w$, step 4.1 shows $x_{2^j}\mathrm{\ne }{x}_0$ modulo $2^{j+1}$ and therefore modulo $2^w$, contradiction. Hence $d=2^w$, for every seed.

The map $x\mapsto [ax+c{]}_{2^w}$ is injective: if two outputs agree then $2^w\mid a(x-y)$. Since $a$ is odd, $2\mid ad$ implies $2\mid d$; canceling a factor $2$ and repeating $w$ times gives $2^w\mid x-y$. Thus the map is a permutation of the finite state set. By [F2], a uniform seed therefore remains uniform at every time. The adjacent-pair law is supported on exactly the $2^w$ pairs $(x,[ax+c{]}_{2^w})$, while the product of two uniform marginals assigns positive mass to all $2^{2w}$ pairs. Since $w\ge 2$, $2^w<2^{2w}$, so the adjacent states are dependent.

If $c\mathrm{\ne }{c}^{\mathrm{\prime }}$ are counters in the interval, injectivity of ${\pi }_k$ gives ${\pi }_k(c)\mathrm{\ne }{\pi }_k(c^{\mathrm{\prime }})$. The procedure uses each counter at most once before returning exhausted, so no output repeats in that interval.

On the full counter set, the injective map ${\pi }_k$ has $2^w$ distinct outputs in a set of size $2^w$, hence its range is all of $S$. Thus every word appears exactly once, with no probability assertion.

By [F1], the two disjoint subsequences give a joint-uniform pair on $[0,1{]}^2$; [F4] shows the pair lies in $(0,1{)}^2$ almost surely. The chosen endpoint convention changes no law. Applying [F2] gives a pair with independent marginals, each the probability law with density $\varphi$. The existence of this finite bit pair uses Dependent Choice through [F1].

By [A1], the Axiom of Choice supplies Countable Choice for the hypotheses of [F1] and is the exact axiom required by [F3]. Thus each density-$\varphi$ marginal is the canonical $N(0,1)$ law, and the pair remains independent.

By minimality of $k$, $n\le N<2n$ for $n>1$. [F1] gives acceptance probability $a=n\mathrm{/}N>1\mathrm{/}2$ and rejection probability $r=1-a<1\mathrm{/}2$. On one accepted block, the $n$ possible accepted integers have equal probability $1\mathrm{/}N$, with $m$ of them returning $1$ and $n-m$ returning $0$.

By independence of attempts, the probability that the first accepted block occurs at attempt $j$ and returns $1$ is $r^{j-1}m\mathrm{/}N$, while the probability that it occurs at attempt $j$ is $r^{j-1}n\mathrm{/}N$. Summing over $1\le j\le M_{\max }$ gives success probability $1-r^{M_{\max }}$ and returned-one probability $(m\mathrm{/}n)(1-r^{M_{\max }})$; dividing yields conditional success probability $m\mathrm{/}n$. The no-acceptance event has probability $r^{M_{\max }}<2^{-M_{\max }}$.

With no cap, $r^M\to 0$, so the probability of never accepting is zero. Let $J$ be the first accepted attempt, setting $J=\mathrm{\infty }$ on the null nontermination event. For each $M$, $J\wedge M={\sum }_{j=0}^{M-1}{\mathbf{1}}_{\{J>j\}}$; these truncations increase to $J$, and independence gives $\mathbb{P}(J>j)=r^j$. By [F3] and the geometric identity [F4] with $0\le r<1\mathrm{/}2$, $\mathbb{E}J={\sum }_{j\ge 0}{r}^j=(1-r{)}^{-1}=N\mathrm{/}n<2$. Taking $M\to \mathrm{\infty }$ in step 2.1 gives output-one probability $m\mathrm{/}n$ and hence the exact Bernoulli$(m\mathrm{/}n)$ law. Each attempt consumes $k$ bits, so the expected bit cost is $kN\mathrm{/}n<2k$. The cases $m=0$ and $m=n$ use the explicit zero-bit branches in the algorithm.