Generating random numbers of prescribed distribution using physical sources

摘要

When constructing uniform random numbers in [0, 1] from the output of a physical device, usually n independent and unbiased bits B_j are extracted and combined into the machine number Y := ∑_(j=1)~n 2~(-j) B_j. In order to reduce the number of data used to build one real number, we observe that for independent and exponentially distributed random variables X_n (which arise for example as waiting times between two consecutive impulses of a Geiger counter) the variable U_n := X_(2n-1)/(XX_(2n-1) + X_(2n)) is uniform in [0, 1]. In the practical application X_n can only be measured up to a given precision v (in terms of the expectation of the X_n); it is shown that the distribution function obtained by calculating U_n from these measurements differs from the uniform by less than v/2. We compare this deviation with the error resulting from the use of biased bits B_j with P~ε{B_j = 1} = 1/2 + ε(where ε∈] - 1/2, 1/2[) in the construction of Y above. The influence of a bias is given by the estimate that in the p-total variation norm ‖Q‖_p~(TV) = (∑_ω∣Q(ω)∣~p)~(1/p) (p ≥ 1) we have ‖P_Y~ε- P_Y~0 ‖_p~(TV) ≤ (c_n~(1/2)·ε)~(1/p) with c_n → p 8/π(1/2) for n →∞. For the distribution function ‖F_Y~ε - F_Y~0‖≤ 2(1- 2~(-n)∣ε∣ holds.