Generation of random bits from Poisson processes

Abstract

In a recent work, Bernardini and Rinaldo generalize and attempt to improve upon Elias method to obtain unbiased random bits from a geometric distribution resulted from a Poisson process. As a response, we analyse the output rates of their method and compare with the original binary Elias method applied on a Bernoulli process resulted from the same Poisson process, which turns out to be much simpler to implement and to have a higher output rate.

Keywords

random bits Poisson process Bernoulli process geometric distribution Elias algorithm

1 Introduction

This paper is a response to a recent work by Bernardini and Rinaldo [1], which is summarized as follows: with an appropriate discretization, the interarrival time of a Poisson process is approximated by a geometric distribution on which Elias’s method can be applied to obtain independent and unbiased random bits, and their main contribution is to go further and take advantage of the geometric distribution to generalize Elias method to get a better output rate than directly applying classic Elias method.

Given a coin that turns heads (denoted H) with probability p, and thus turns tails (T) with probability q = 1 - p, the celebrated von Neumann’s trick [19] takes two coin flips; if the result is HT, then output 1; if the result is TH, then output 0; if we have HH or TT, then ignore the result and repeat the process until we get 0 or 1. The obtained bit is unbiased because Pr(HT) = Pr(TH) = pq. By applying this procedure repeatedly on a sequence of independent coin flips, taking two flips each time, we obtain a sequence of random bits which are unbiased and independent.

Generalizing and formalizing this idea [4 , 12], an extracting functionfcolon {0, 1} ⁿ → {0, 1} ^* takes as input n independent bits of bias p (called Bernoulli source of bias p) and returns a string of independent and unbiased random bits. For example, the function Ψ₁colon {0, 1} ² → {0, 1} ^*, defined by $Ψ_{1} (00) = Ψ_{1} (11) = λ; Ψ_{1} (01) = 1; Ψ_{1} (10) = 0,$

where λ is an empty string, corresponds to the von Neumann’s procedure. This is the simplest non-trivial extracting function [12].

The output rate of an extracting function is the average number of output bits per one input bit. It is known to be bounded above by Shannon entropy H (p), which we also call the entropy bound. When p = 1/3, the output rate of von Neumann’s procedure is pq = 2/9 ≈ 0.22 (See, for example, exercise 5.1-3 in [17]) while the entropy bound H (1/3) ≈0.92; the discrepancy is quite large. There are extracting functions that achieve output rates arbitrarily close to the entropy bound, which we call asymptotically optimal. Such methods were proposed by Elias [4] and Peres [13], and Elias’s method is easily generalized to a source of s-sided dice, in which case, again, it is asymptotically optimal so that its output rate approaches the entropy bound H (p₀, …, p_s-1), where ‹p₀, …, p_s-1› is the probability distribution of the dice.

Let X be an s-sided dice with an unknown probability distribution. Elias’s original method takes n samples from the source X and partitions the sample space Xⁿ into equiprobable subsets, that is, subsets of permutations of inputs of given numbers of symbols, for which it outputs the maximum possible number of unbiased random bits. Bernardini and Rinaldo’s work takes advantage of the fact that the obtained samples from Poisson process make a (truncated) geometric distribution. This fact makes it possible to have a better partition of sample space than Elias’s original partition. The proposed partition congregates subsets of the original Elias partition, hence results in bigger equiprobable subsets, and thus higher output rate. Since the original Elias method is asymptotically optimal, their proposed method is also asymptotically optimal.

On the other hand, we can obtain another discrete distribution from a Poisson process; instead of sampling interarrival time and thus getting a geometric distribution, we can get a Bernoulli process by checking whether an arrival happened in each sampling interval. We can then apply classical binary Elias method, which turns out to be better than their method based on geometric distribution, because the output rate is higher and computation is, arguably, simpler.

In Sections 2 and 3, we explain the Elias method and the discretization of Poisson process. Section 4 comprises the main part of this paper, in which we explain the two method based on geometric distribution and Bernoulli process, and make arguments for the latter. To compare the output rates of the two methods, we don’t simply simulate the methods on samples as in [1], but we derive exact output rates and perform a numerical calculations of them. Also, discussions on how to make a proper comparison of output rates between two methods are given. To argue for the simplicity of the method based on the Bernoulli process, we discuss the complexity of the method based on the geometric distribution.

2 Elias Method

Elias Suppose that we have a s-faced dice whose probability distribution of outcomes is ‹p₀, …, p_s-1›. Elias method converts n die rolls into unbiased random bits. When s = 2 and n = 2, it is the same as the famous von Neumann’s trick for converting biased coin flips into unbiased random bits, and there is a rich literature on this problem of generating uniform random bits from biased randomness source [3 , 18].

As a function, Elias method can be written as $E_{n} {0, 1, \dots, s - 1}^{n} \to {0, 1}^{*} .$ In the same spirit as von Neumann’s, in which the equiprobable events HT and TH are exploited, the input space is first decomposed into equiprobable subsets: ${0, 1, \dots, s - 1}^{n} = ⋃_{n_{0} + \dots + n_{s - 1} = n} S_{(n_{0}, \dots, n_{s - 1})},$ where S_{(n₀,…,n_s-1)} is the set of inputs in which a symbol i appears n_i times. For example, when s = 5, m = 8, an input 20110241 is in S_(2,3,2,0,1). Note that, for every x in the equiprobable set, $Pr (x \in S_{(n_{0}, \dots, n_{s - 1})}) = p_{0}^{n_{0}} \dots p_{s - 1}^{n_{s - 1}} .$ Now, each equiprobable set S_{(n₀,…,n_s-1)} is mapped onto {0, 1} ^l of a maximal sizes possible. For example, $| S_{(2, 3, 2, 0, 1)} | = (\begin{matrix} 8 \\ 2, 3, 2, 0, 1 \end{matrix}) = \frac{8!}{2! 3! 2! 0! 1!} = 1680 .$

The maximal size of {0, 1} ^l that fits into is 2¹⁰ = 1024. The remaining 1680 - 1024 = 656 inputs are mapped similarly into full binary sets of sizes 2⁹ = 512, 2⁷ = 128, and 2⁴ = 16. In general, these sizes are determined by the binary expansion of the size of the equiprobable set. In the above example, 1680 = 2¹⁰ + 2⁹ + 2⁷ + 2⁴, and the total number of output bits is 10 · 2¹⁰ + 9 ·2⁹ + 7 ·2⁷ + 4 ·2⁴. Note that the above description does not specify a value E_n (x) but rather an image of equiprobable sets. Assume that we fixed a mapping and call it Elias function.

This method works for an arbitrary probability distribution ‹p₀, …, p_s-1›, and it is optimal in the output rate for a given distribution and for each input size. Elias method is asymptotically optimal.

When s = 2, an equiprobable set S_(l,k) is also written as S_n,k, where n = l + k, or S_k when n is assumed fixed, and its size can also be written as an equivalent binomial coefficient as well as the multinomial one: $(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ l, k \end{matrix}) .$

Now, the total number α (u) of outputs on an equiprobable set is determined by the size u of the equiprobable set. More precisely, α (u) = ∑_iia_i2ⁱ, where ∑_ia_i2ⁱ is the standard binary expansion of u with a_i either 0 or 1. When a_i = 1, since E_n outputs i bits for each string in the equiprobable set S, and there are 2ⁱ strings in S, the sum of output lengths over S is i2ⁱ. So the sum of output lengths over S is ∑_ia_i · i · 2ⁱ = α (|S|). The average output length of E_n over the entire input set {0, 1, …, s - 1} ⁿ is, therefore, $\frac{1}{n} \sum_{n_{0} + \dots + n_{s - 1} = n} α (| S_{(n_{0}, \dots, n_{s - 1})} |) p_{0}^{n_{0}} \dots p_{s - 1}^{n_{s - 1}} .$ (1)

Figure 1 shows a graph of α. The function α is monotone increasing. In fact, it increases somewhat faster than linear; α (u) ≥ u for u ≥ 2, and it is bounded above by u log ₂u with the bound met when u is a power of 2.

Fig.1

A plot of the function α

Lemma 1. For a positive integer u, we have $α (2 u) = 2 α (u) + 2 u .$

Proof. For u = ∑_ia_i2ⁱ, we have $\begin{matrix} α (2 u) - 2 α (u) & = \sum_{i} (i + 1) a_{i} 2^{i + 1} - \sum_{i} i a_{i} 2^{i + 1} \\ = \sum_{i} i a_{i} 2^{i + 1} = 2 u . \end{matrix}$ So we have the lemma.

In fact, the function α has a little stronger property that is used by Bernardini and Rinaldo to take advantage of their partition of larger equiprobable sets of geometric samples.

Proposition 2. For positive integers u and v, we have $α (u) + α (v) \leq α (u + v) .$

Proof. Assume that u ≤ v, without loss of generalization. Let u = ∑_ia_i2ⁱ, v = ∑_ib_i2ⁱ and u + v = ∑_id_i2ⁱ be the standard binary expansions, and let c_i+1 be the carry that occurs at ith position when the two binary numbers are added, so that d_i+1 = a_i+1 + b_i+1 + c_i+1 mod2.

If a_i + b_i is 0 or 1, that is c_i+1 = 0, for all i, then a_i + b_i = d_i for all i and we have $\begin{matrix} α (u) + α (v) & = \sum_{i} {ia}_{i} 2^{i} + \sum_{i} {ib}_{i} 2^{i} \\ = \sum_{i} i (a_{i} + b_{i}) 2^{i} \\ = \sum_{i} i c_{i} 2^{i} \\ = α (u + v) . \end{matrix}$ Otherwise, we have a nonzero carry, and let $k = max {i ∣ c_{i} = 1} .$ Then, we conclude that a_k = b_k = 0, and d_k = 1, and that $α (\sum_{i \geq k + 1} a_{i} 2^{i}) + α (\sum_{i \geq k + 1} b_{i} 2^{i}) = α (\sum_{i \geq k + 1} d_{i} 2^{i})$ by the similar reason as above.

Now, since a_k = b_k = 0, $\begin{matrix} α (\sum_{i = 0}^{k} a_{i} 2^{i}) + α (\sum_{i = 0}^{k} b_{i} 2^{i}) & \leq 2 α (\sum_{i = 0}^{k - 1} 2^{i}) \\ = 2 \sum_{i = 0}^{k - 1} i 2^{i} \\ = k 2^{k} - 1 \\ < k 2^{k} \\ \leq α (d_{k} 2^{k}) \\ \leq α (\sum_{i = 0}^{k} d_{i} 2^{i}) . \end{matrix}$ Therefore, we have α (u) + α (v) ≤ α (u + v).

By applying Proposition 2 repeatedly, we obtain

Proposition 3. For positive integers u₁, …, u_k, we have $α (u_{1}) + \dots + α (u_{k}) \leq α (u_{1} + \dots + u_{k}) .$

3 Discretization of Poisson Process

discretization The arrival time T of a Poisson process with intensity λ has the probability density function $Pr (T = t) = λ e^{- λ t} .$ Arrivals in a sequence of time intervals of an equal size τ give rise to a Bernoulli process {X_i} with success probability Pr(X_i = 1) = p, where $p = \int_{0}^{τ} λ e^{- λ t} = 1 - e^{- λ τ},$ and q = 1 - p = e^-λτ. Also we obtain the induced random variable Y of geometric distribution with parameter p, whose probability mass function is $Pr (Y = k) = {pq}^{k},$ that is, the probability of a success after k failures.

4 Elias-Geometric vs. Elias-Bernoulli

bernoulli-vs-geometric As we saw above, from a Poisson process, we can obtain a Bernoulli source X and an associated source Y of a geometric distribution. Since a sample from geometric random variable can be arbitrarily large and thus the partition size can even be formidable for a practical computation, a truncation is applied to get a source Z. Although Elias method can be applied on samples of Z now, as is explained below, on which the Elias method is applied. Bernardini and Rinaldo [1] takes advantage of the geometric distribution so that a larger equiprobable partition can be obtained and thus higher output rate. We call this method Elias-geometric. On the other hand, we can consider an alternative method that apply Elias algorithm, as explained above in Section 2, directly on the Bernoulli source X, which we call Elias-Bernoulli. The main goal of ours is to compare the performance of the two methods. We will use n for the number of Bernoulli samples and m for the number of geometric samples, and they are assumed fixed.

4.1 Elias-geometric

Geometric Distribution If Y is a random variable with a geometric distribution of parameter p, the probability distribution is $Pr (Y = k) = p (1 - p)^{k} = {pq}^{k}, k = 0, 1, 2, \dots .$ For a practical sampling, we use a truncated version of geometric distribution $Z = Y mod M,$ where M is a suitably chosen integer. Then its probability distribution is $Pr (Z = k) = \frac{{pq}^{k}}{1 - q^{M}}, k = 0, 1, 2, \dots, M - 1 .$ (2)

Classical Elias Partition Now Z is just M-valued source of probability (2). Apply Elias method to get unbiased bitstrings: Take m samples z₁, z₂, …, z_m, each from Z. Then, z = (z₁, z₂, …, z_m) ∈ [M] ^m = {0, 1, …, M - 1} ^m. Partition the input space [M] ^m into equiprobable sets S_{(m₀,…,m_M-1)}, where m_i is the number of i in z = (z₁, z₂, …, z_m) and m = m₀ + … + m_M-1, and the output size of Elias function $E_{m}^{M}$ is determined by the size of the equiprobable set S_{(m₀,…,m_M-1)}, as explained in Section 2.

New Equiprobable Partition However, the source Z is not simply an M-valued source with an arbitrary probability distribution but it has a special distribution (2). So, we can take advantage of the property and get a better partition. Let, for 0 ≤ k ≤ m (M - 1), Q_k be the set ${(z_{1}, \dots, z_{m}) \in [M]^{m} ∣ z_{1} + \dots + z_{m} = k} .$ (3) For every z ∈ Q_k, we have $Pr (z) = \frac{p^{m} q^{k}}{(1 - q^{M})^{m}},$ hence Q_k is equiprobable. This new partition results in much bigger equiprobable sets than the classical Elias partition. For example, when M = 4 and m = 6, $\begin{matrix} Q_{5} & = S_{(1, 5, 0, 0)} \cup S_{(2, 3, 10)} \\ \cup S_{(3, 1, 2, 0)} \cup S_{(3, 2, 0, 1)} \cup S_{(4, 0, 1, 1)} . \end{matrix}$ (4)

More generally, for given M and m, we have $Q_{k} = ⋃ S_{(m_{0}, \dots, m_{M - 1})},$ (5) where (m₀, …, m_M-1)’s are the solutions of the integer equation ${\begin{matrix} m_{0} + \dots + m_{M - 1} = m, \\ 0 \cdot m_{0} + \dots + (M - 1) \cdot m_{M - 1} = k . \end{matrix}$ (6) Note that this equation is equivalent to ${\begin{matrix} z_{1} + \dots + z_{m} = k, \\ 0 \leq z_{i} < M, i = 1, \dots, m, \end{matrix}$ (7) which is implicit in the definition (3). Table 1 shows a complete list of the solutions.

Table 1

Table of Q_k = ⋃ S_{(m₀,…,m_M-1)} that satisfy the equations (6) and (7) for M = 4 and m = 6. The second column is the size of Q_k.

k=0	1	(6, 0, 0, 0)
k=1	6	(5, 1, 0, 0)
k=2	21	(5, 0, 1, 0), (4, 2, 0, 0)
k=3	56	(5, 0, 0, 1), (4, 1, 1, 0), (3, 3, 0, 0)
k=4	120	(4, 0, 2, 0), (2, 4, 0, 0), (4, 1, 0, 1), (3, 2, 1, 0)
k=5	216	(1, 5, 0, 0), (4, 0, 1, 1), (3, 2, 0, 1), (3, 1, 2, 0), (2, 3, 1, 0)
k=6	336	(0, 6, 0, 0), (4, 0, 0, 2), (1, 4, 1, 0), (3, 0, 3, 0), (2, 3, 0, 1), (3, 1, 1, 1), (2, 2, 2, 0)
k=7	456	(0, 5, 1, 0), (1, 4, 0, 1), (3, 1, 0, 2), (3, 0, 2, 1), (2, 1, 3, 0), (1, 3, 2, 0), (2, 2, 1, 1)
k=8	546	(0, 5, 0, 1), (2, 0, 4, 0), (0, 4, 2, 0), (3, 0, 1, 2), (1, 2, 3, 0), (1, 3, 1, 1), (2, 2, 0, 2), (2, 1, 2, 1)
k=9	580	(1, 1, 4, 0), (0, 4, 1, 1), (3, 0, 0, 3), (0, 3, 3, 0), (2, 0, 3, 1), (1, 3, 0, 2), (2, 1, 1, 2), (1, 2, 2, 1)
k=10	546	(1, 0, 5, 0), (0, 4, 0, 2), (0, 2, 4, 0), (2, 1, 0, 3), (0, 3, 2, 1), (1, 1, 3, 1), (2, 0, 2, 2), (1, 2, 1, 2)
k=11	456	(0, 1, 5, 0), (1, 0, 4, 1), (2, 0, 1, 3), (1, 2, 0, 3), (0, 3, 1, 2), (0, 2, 3, 1), (1, 1, 2, 2)
k=12	336	(0, 0, 6, 0), (2, 0, 0, 4), (0, 1, 4, 1), (0, 3, 0, 3), (1, 0, 3, 2), (1, 1, 1, 3), (0, 2, 2, 2)
k=13	216	(0, 0, 5, 1), (1, 1, 0, 4), (1, 0, 2, 3), (0, 2, 1, 3), (0, 1, 3, 2)
k=14	120	(0, 2, 0, 4), (0, 0, 4, 2), (1, 0, 1, 4), (0, 1, 2, 3)
k=15	56	(1, 0, 0, 5), (0, 1, 1, 4), (0, 0, 3, 3)
k=16	21	(0, 1, 0, 5), (0, 0, 2, 4)
k=17	6	(0, 0, 1, 5)
k=18	1	(0, 0, 0, 6)

Elias-geometric method is a generalized Elias method that uses these new partitions, $[M]^{m} = ⋃_{k = 0}^{m (M - 1)} Q_{k},$ and its output rate is $r_{G} (p, m) = \sum_{k = 0}^{m (M - 1)} \frac{p^{m} q^{k}}{(1 - q^{M})^{m}} α (| Q_{k} |) .$ (8) The output rate of the method using the classical Elias partition, that is the Elias method on the M-valued source Z of truncated geometric distribution, is $\sum_{k = 0}^{m (M - 1)} \frac{p^{m} q^{k}}{(1 - q^{M})^{m}} (\sum α (| S_{(m_{0}, \dots, m_{M - 1})} |)),$ (9) where the inner summation is over (m₀, …, m_M-1)’s subject to the equation (6). By Proposition 3, we have $\sum α (| S_{(m_{0}, \dots, m_{M - 1})} |) \leq α (| Q_{k} |) .$ So, the rate r_G (p, m) is no smaller than rate (9).

4.2 An Extremal Case of Elias-Geometric

extremal Although it is computationally impractical to implement the corresponding version of Elias algorithm, for the sake of analysis, consider an extremal case of Elias-geometric where the truncation step is removed, or rather M =∞. Now the random variable Z = Y is pure geometric, and a sample can be arbitrarily large and the input space ^bNm is partitioned into equiprobable subsets $⋃_{k = 0}^{\infty} {\hat{Q}}_{k}$ , where ${\hat{Q}}_{k} = {(y_{1}, y_{2}, \dots, y_{m}) ∣ y_{1} + \dots + y_{m} = k, y_{i} \geq 0},$

and, for $y \in {\hat{Q}}_{k}$ , $Pr (y) = p^{m} q^{k} .$ And in this case, $\begin{matrix} {\hat{Q}}_{5} = & S_{(1, 5, 0, 0, 0, 0, 0 \dots)} \cup S_{(2, 3, 1, 0, 0, 0, 0, \dots)} \\ \cup S_{(3, 1, 2, 0, 0, 0, 0, \dots)} \cup S_{(3, 2, 0, 1, 0, 0, 0, \dots)} \\ \cup S_{(4, 0, 1, 1, 0, 0, 0, \dots)} \cup S_{(4, 1, 0, 0, 1, 0, 0, \dots)} \\ \cup S_{(5, 0, 0, 0, 0, 1, 0, \dots)} . \end{matrix}$ Compare this with the partition of truncated case (4). The first five subsets correspond to the subsets in the truncated case, and there are two extra subsets, hence the size of ${\hat{Q}}_{k}$ is bigger for M =∞. In fact, when k < M, the partitions of Q_k and ${\hat{Q}}_{k}$ for the two cases are identical. And if M′ > M, then the equiprobable set $Q_{k}^{'}$ for M′-truncation is bigger than Q_k for M-truncation. Also, the probabilities of s samples z′ and z in the equiprobable sets of the two cases satisfy $Pr (z^{'}) = \frac{p^{m} q^{k}}{(1 - q^{M^{'}})^{m}} > \frac{p^{m} q^{k}}{(1 - q^{M})^{m}} = Pr (z) .$ Therefore, in view of (8), the output rate r_G (p, m), in which the truncation parameter M is implicit, increases as M increases.

The extremal case of Elias-geometric, where M =∞, has the output rate ${\hat{r}}_{G} (p, m) = \frac{1}{m} \sum_{k = 0}^{\infty} α (| {\hat{Q}}_{k} |) p^{m} q^{k},$ (10) and it is an upper bound of the output rate r_G (p, m) for every case of finite M. Unlike the finite-M cases, in which z_i’s are constrained by the condition 0 ≤ z_i < M in (7), in M =∞ case, the size of ${\hat{Q}}_{k}$ is conveniently expressed by a binomial coefficient: $| {\hat{Q}}_{k} | = (\begin{matrix} m + k - 1 \\ k \end{matrix}),$ so that we can compute the approximate value of the infinite series (10). See Section 4.3 for an interpretation of this quantity in the context of comparing Elias-geometric and Elias-Bernoulli.

4.3 Bernoulli vs. Geometric distribution from a Poisson Process

correspondence We have an obvious one-to-one correspondence between {0, 1} ^∞ and ^{bN ∞}. Say the following bitstring is from a Bernoulli process with p = 0.17: $\begin{matrix} x = 0 & 01100000110100000000101000100011 \\ 0001010000100000000101010010000 \dots \end{matrix}$ The corresponding samples of geometric distribution is: $y = Ψ (x) = 20501813303148112 \dots$ (11) This correspondence is similar to the “run-length encoding.” The correspondence Ψ induces a bijective mapping between a finite number of samples; for the input size m, recall that ${\hat{Q}}_{k}$ is the subset of sequences (y₁, …, y_m) ∈ ^bNm such that y₁ + … + y_m = k. For $y \in {\hat{Q}}_{k}$ , associate a binary sequence x1, where x has k 0’s and m - 1 1’s. For example, a length-6 prefix of (11), $y = 205018$ corresponds to $x 1 = 0011000001101000000001 .$ Note, here, that m = 6, and $k = 2 + 0 + 5 + 0 + 1 + 8 = 16 .$ Using the same name for the mapping between the infinite sequences {0, 1} ^∞ and ^{bN ∞}, we have a bijection between finite sequences $Ψ S_{m + k - 1, k}^{'} = {x 1 ∣ x \in S_{m + k - 1, k}} \to {\hat{Q}}_{k} .$ (12) Under this correspondence, the proposed method is reduced to the original binary Elias method: given an input y, use original Elias method on the corresponding x1 = Ψ^-1 (y) to compute the output. The same thing holds in the other direction as well. An interesting observation is that, by this one-to-one correspondence, we easily see that $| {\hat{Q}}_{k} | = | S_{m + k - 1, k} | = (\begin{matrix} m + k - 1 \\ k \end{matrix}) .$ Note that a binary sequence x with m - 1 1’s and k 0’s exactly corresponds to a monotone path from the bottom left corner to the upper right corner of a grid of size k × (m - 1), and there are exactly k + m - 1choosem - 1 = m + k - 1choosek such paths. See Section 7.2.1.3 of [6]. Figure. 2 shows the monotone path corresponding the binary sequence x of the above example. Since the way the correspond attaches 1 at the end of x, the path in the figure have a vertical segment attached at the end.

Fig.2

A monotone path 0011000001101000000001 in a grid of size k × m. The last vertical segment of length one is attached to show the way we make the correspondence Ψ. There are exactly k + m - 1choosem - 1 = m + k - 1choosek such paths.

4.4 Finite-Length Samplings

sample-size-comp A Bernoulli process of parameter p induces the geometric distribution with the average arrival time 1/p. In other words, we can expect one arrival in 1/p-th discretization interval on average. So every 1/p samplings of Bernoulli process amounts to a single sample of the corresponding geometric source. In fact, the entropy of the geometric distribution is $- \sum_{k = 0}^{\infty} p (1 - p)^{k} log (p (1 - p)^{k}) = \frac{1}{p} H (p),$ where H (p) is the entropy of the Bernoulli distribution. So the two samplings have the same information contents.

Now consider sampling from the Bernoulli process. The appropriate size must be, by the above discussion, n = m/p, where m is the sample size for Elias-geometric. (Or m = np. We have one geometric sample for every 1 in the source Bernoulli samples.)

Expected length of the inverse. Another way, or a more convincing way to see this is to consider the average length of Ψ^-1 (y) over all $y \in {\hat{Q}}_{k}$ of length m:

$\begin{matrix} | Ψ^{- 1} (y) | & = \sum_{k \geq 0} (m + k) (\begin{matrix} m + k - 1 \\ k \end{matrix}) p^{m} q^{k} \\ = m + p^{m} \sum_{k \geq 0} k (\begin{matrix} m + k - 1 \\ k \end{matrix}) q^{k} . \end{matrix}$ (13) Note that $\sum_{k \geq 0} | {\hat{Q}}_{k} | p^{m} q^{k} = 1,$ and consider the function $f (z) = \frac{1}{(1 - z)^{m}} = \sum_{k \geq 0} (\begin{matrix} m + k - 1 \\ k \end{matrix}) z^{k} .$ The series is obtained by multiplying m copies of 1/(1 - z) =1+ z + z² + ⋯, and the coefficient arises exactly the same way as we count the strings in ${\hat{Q}}_{k}$ . Then, we have $\begin{matrix} {zf}^{'} (z) & = \frac{mz}{(1 - z)^{m + 1}} \\ = \sum_{k \geq 0} k (\begin{matrix} m + k - 1 \\ k \end{matrix}) z^{k} . \end{matrix}$ With z = q, the above formula (13) $m + {mp}^{m} q / p^{m + 1} = m (1 + q / p) = m / p,$ completing the proof that the sample sizes n and m has the relationship $n = m / p .$ Expected length of the image Conversely, starting from the Bernoulli samples of size n, the expected length of the corresponding geometric samples is $| Ψ (x) | = \sum_{k = 0}^{n} k (\begin{matrix} n \\ k \end{matrix}) p^{k} q^{n - k} .$ (14) From the binomial theorem $(x + y)^{n} = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} y^{n - k}$ , we obtain $nx (x + y)^{n - 1} = \sum_{k = 0}^{n} k n k x^{k} y^{n - k} .$ Put x = p and y = q, and the formula (14) becomes np.

4.5 Comparison of Output Rates

The output rate for Elias-Bernoulli is, as in (1), $r_{B} (p, n) = \frac{1}{n} \sum_{l = 0}^{n} α (| S_{l} |) p^{l} q^{n - l} .$ Now the output rate for the corresponding Elias-geometric with the truncation parameter M, as shown in (8), is again $r_{G} (p, m) = \frac{1}{m} \sum_{k = 0}^{m (M - 1)} \frac{p^{m} q^{k}}{(1 - q^{M})^{m}} α (| Q_{k} |) .$ This quantity increases as M increases, and, it is bounded above, as discussed in Section 4.2, by ${\hat{r}}_{G} (p, m) = \frac{1}{m} \sum_{k = 0}^{\infty} α (| {\hat{Q}}_{k} |) p^{m} q^{k} .$ Note that this rate is the average output for a single geometric sample, which has 1/p times the information of a Bernoulli source bit, as discussed in Section 4.4. We need to compare r_B (p, n) with $p \cdot {\hat{r}}_{G} (p, m)$ , the average output length per binary source bit. Figure 3 shows plots of the rates, together with the information-theoretic bound H (p), and it shows that $r_{B} (p, n) > p \cdot {\hat{r}}_{G} (p, m)$ . Note that the calculation we performed is not a result from samples obtained with a simulation as in [1] but a numerical calculation of exact output rates that we derived above.

Fig.3

Output rates r_B (n, p) (solid) and ${\hat{r}}_{G} (m, p)$ (dash-dotted), and together with the entropy H (p) (dotted), for p = 0.05, 0.1, …, 0.95; n = 100 and m = np.

5 Remarks

Implementation of Elias-geometric

Although the larger partitions Q_k result in higher output rate, in order to compute Elias function, as far as we know, we need to compute a rank of a given input sequence in the equiprobable partition, and part seems to be the computational bottleneck. (See [12, 14] for details.) And to do that we need to know the size of Q_k. In the idealized case of ${\hat{Q}}_{k}$ , its size is expressed as relatively simple binomial number. However, with the truncated case, it appears that we need to solve the integer equation (6) that can be very hard in general. Moreover, computing a rank in Q_k might need to deal with the many components S_{(m₀,…,m_M-1)}, as demonstrated in Table 1, which makes the problem more complicated.

Exact Comparison of the Output Rates

Although we derived exact formula for the output rates r_B (p, n) and ${\hat{r}}_{G} (p, m)$ , we could not prove the inequality exactly. If we understand the property of the function α better, we might be able to do so, probably using the techniques used in Section 4.4.

Footnotes

Acknowledgement

This work was supported in part by a Hongik University grant and the National Research Foundation of Korea (NRF) grant funded by the Korean government (No. 2016R1D1A1B01016531).

References

Bernardini

and Rinaldo

, Unbiased random sequences from measurements of poisson processes, in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)2014, pp. 8188–8192.

Cover

T.M.

and Thomas

J.A.

, Elements of information theory, (2. ed.), Wiley, 2006.

Dijkstra

E.W.

, Making a fair roulette from a possibly biased coin, Information Processing Letters36 (1990), 193.

Elias

, The efficient construction of an unbiased random sequence, The Annals of Mathematical Statistics43(3) (1972), 865–870.

Juels

, Jakobsson

, Shriver

and Hillyer

B.K.

, How to turn loaded dice into fair coins, IEEE Transactions on Information Theory46(3) (2000), 911–921.

Knuth

D.E.

, The Art of Computer Programming, Combinatorial Algorithms, Part 1, volume 4A. Addison-Wesley, 2011.

Knuth

D.E.

and Yao

A.C.-C.

, The complexity of nonuniform random number generation. In Joseph

F. Traub

, editor, Algorithms and Complexity: New Directions and Recent Results. Proceedings of a Symposium, NewYork, NY, 1976, pp. 357–428. Carnegie-Mellon University, Computer Science Department, Academic Press. Reprinted in Knuth’s Selected Papers on Analysis of Algorithms (CSLI, 2000).

Pae

, Exact output rate of Peres’s algorithm for random number generation, Inf Process Lett113(5-6) (2013), 160–164.

Pae

, A generalization of Peres’s algorithm for generating random bits from loaded dice, IEEE Transactions on Information Theory61(2) (2015).

10.

Pae

, Binarizations in random number generation, In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 2016, pp. 2923–2927.

11.

Pae

and Loui

M.C.

, Optimal random number generation from a biased coin, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005) pp. 1079–1088.

12.

Pae

and Loui

M.C.

, Randomizing functions: Simulation of discrete probability distribution using a source of unknown distribution, IEEE Transactions on Information Theory52(11) (2006), 4965–4976.

13.

Peres

, Iterating von Neumann’s procedure for extracting random bits, Annals of Statistics20(1) (1992), 590–597.

14.

Ryabko

B.Y.

and Matchikina

, Fast and efficient construction of an unbiased random sequence, IEEE Transactions on Information Theory46(3) (2000), 1090–1093.

15.

Samuelson

P.A.

, Constructing an unbiased random sequence, Journal of American Statistical Sociaety63(324) (1968).

16.

Shannon

C.E.

, Warren

, The Mathematical Theory of Communication, The University of Illinois Press, Urbana. 1964.

17.

Stein

, Cormen

T.H.

, Rivest

R.L.

, Leiserson

C.E.

, Introduction to Algorithms, MIT Press, 2nd edition, 2001.

18.

Stout

Q.F.

and Warren

, Tree algorithms for unbiased coin tossing with a biased coin, Annals of Probability12(1) (1984), 212–222.

19.

von Neumann

, Various techniques for use in connection with random digits. Notes by Forsythe

G.E.

. In Monte Carlo Method, Applied Mathematics Series, volume 12, pp. 36–38. U.S. National Bureau of Standards, Washington D.C., 1951. Reprinted in von Neumann’s, Collected Works5 (Pergammon Press, 1963), pp. 768–770.