{'fraction_non_alphanumeric': 0.048476662164190304, 'fraction_numerical': 0.01263194757116414, 'mean_word_length': 3.80574588291862, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 35, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Von Neumann Normalisation of a Quantum Random Number Generator

In this paper we study von Neumann un-biasing normalisation for ideal and real quantum random number generators, operating on finite strings or infinite bit sequences. In the ideal cases one can obtain the desired un-biasing. This relies critically on the independence of the source, a notion we rigorously define for our model. In real cases, affected by imperfections in measurement and hardware, one cannot achieve a true un-biasing, but, if the bias"drifts sufficiently slowly", the result can be arbitrarily close to un-biasing. For infinite sequences, normalisation can both increase or decrease the (algorithmic) randomness of the generated sequences. A successful application of von Neumann normalisation---in fact, any un-biasing transformation---does exactly what it promises, un-biasing, one (among infinitely many) symptoms of randomness; it will not produce"true"randomness.


Introduction
The outcome of some individual quantum-mechanical events cannot in principle be predicted, so they are thought of as ideal sources of random numbers. An incomplete list of quantum phenomena used for random number generation include nuclear decay radiation sources [29], the quantum mechanical noise in electronic circuits known as shot noise [30], photons travelling through a semi-transparent mirror [23,27,31,34,36] or photon arrival times [39,32,4]. Our methods are primarily developed to address these latter photonbased quantum random number generators (QRNGs), one of the most direct and popular ways to generate QRNs, but many of our mathematical results will be applicable to other QRNGs.
Due to imperfections in measurement and hardware, QRNGs are biased and operate non-independently in their generation of bits, two symptoms of non-randomness [10]. 1 The first and simplest technique for reducing bias was invented by von Neumann [38]. It considers pairs of bits, and takes one of three actions: a) pairs of equal bits are discarded; b) the pair 01 becomes 0; c) the pair 10 becomes 1. Contrary to wide spread claims, the technique works for some sources of bits, but not for all. The source of constantly biased bits is effectively transformed into one in which the probabilities of 0 and 1 are equal: 50% for each. As we shall show, a stronger property is true: the un-biasing works not only for bits but for all reasonably long bit-strings. However, if the bias is not constant the procedure does not work. Furthermore, the von Neumann procedure cannot assure "true randomness" in its output. We briefly emphasise that bias is a property of the source of bits which only gives the expected frequency of 0's and 1's in the strings produced.
To understand the behaviour of QRNGs we need to study the un-biasing transformations on both (finite) strings and (infinite) sequences of bits produced by the source. In this paper we will focus on von Neumann normalisation 2 because it is very simple, easy to implement, and (along with the more efficient iterated version due to Peres [26] for which the results will also apply) is widely used by current proposals for QRNGs [23,24,18,31]. Similar or stronger normalisation procedures have been studied under additional assumptions in, for example, Blum [7] (the source is a finite Markov chain) or Santha and Vazirani [28] (the source is semi-random) or Vadhan [37]; such additional hypotheses are satisfied by some physical sources, like a zener diode, but not necessarily by quantum sources. The widespread use of von Neumann normalisation, however, warrants a proper understanding of its operational quality when used on non-ideal sources regardless of the existence of other methods.
The main results of this paper are the following. In the "ideal case", the von Neumann normalised output of an independent constantly biased QRNG is the probability space of the uniform distribution (un-biasing). This result is true for both for finite strings and for the infinite sequences produced by QRNGs (the QRNG runs indefinitely in the latter case).
It is important to note that independence in the mathematical sense of multiplicity of probabilities is a model intended to correspond to the physical notion of independence of outcomes [20]. In order to study the theoretical behaviour of QRNGs, which are based on the assumption of physical independence of measurements, we must translate this appropriately into our formal model. We carefully define independence of QRNGs to achieve this aim.
As explained above, QRNGs do not operate in ideal conditions. We develop a model for a real-world QRNG in which the bias, rather than holding steady, drifts slowly (within some bounds). In this framework we evaluate the speed of drift required to be maintained by the source distribution to guarantee that the output distribution is as close as one wishes to the uniform distribution.
We have also examined the effect von Neumann normalisation has on various properties of infinite sequences. In particular, Borel normality and (algorithmic) randomness are invariant under normalisation, but for ε-random sequences with 0 < ε < 1, normalisation can both decrease or increase the randomness of the source.
Finally, we present our results in a mathematical framework which avoids hasty claims which later are disproved.

Notation
We present the main notation used throughout the paper.
By 2 X we denote the power set of X. By |X| we denote the cardinality of the set of X.
Let B = {0, 1} and denote by B * the set of all bit-strings (λ is the empty string). If x ∈ B * and i ∈ B then |x| is the length of x and # i (x) represents the number of i's in x. By B n we denote the finite set {x ∈ B * | n = |x|}. The concatenation product of two subsets X, Y of B * is defined by XY = {xy | x ∈ X, y ∈ Y }. If X = {x} then we write xY instead of {x}Y . By B ω we denote the set of all infinite binary sequences. For x ∈ B ω and natural n we denote by x(n) the prefix of x of length n. We write w < v or w < x in case w is a prefix of the string v or the sequence x.
A prefix-free (Turing) machine is a Turing machine whose domain is a prefix-free set of strings [10]. The prefix complexity of a string, H W (σ), induced by a prefix-free machine W is H W (σ) = min{|p| : W (p) = σ}. Fix a computable ε with 0 < ε ≤ 1. An ε-universal prefix-free machine U is a machine such that for every machine W there is a constant c (depending on U and W ) such that ε · H U (σ) ≤ H W (σ) + c, for all σ ∈ B * . If ε = 1 then U is simply called a universal prefix-free machine. A sequence x ∈ B ω is called ε-random if there exists a constant c such that H U (x(n)) ≥ ε · n − c, for all n ≥ 1. Sequences that are 1-random are simply called random.
A sequence x is called Borel m-normal (m ≥ 1) if for every 1 ≤ i ≤ 2 m one has: lim n→∞ N m i (x(n))/ n m = 2 −m ; here N m i (y) counts the number of non-overlapping occurrences of the ith (in lexicographical order) binary string of length m in the string y. The sequence x is called Borel normal if it is Borel m-normal, for every natural m ≥ 1.
A probability space is a measure space such that the measure of the whole space is equal to one [6]. More precisely, a (Kolmogorov) probability space is a triple consisting of a sample space Ω, a σ-algebra F on Ω, and a probability measure P , i.e. a countably additive function defined on F with values in [0, 1] such that P (Ω) = 1.

Source probability space and independence
In this section we define the QRNG source probability space and the independence property.
Consider a string of n independent bits produced by a (biased) QRNG. Let p 0 , p 1 be the probability that a bit is 0 or 1, respectively, with p 0 + p 1 = 1, p 0 , p 1 ≤ 1.
The probability space of bit-strings produced by the QRNG is (B n , 2 B n , P n ) where P n : 2 B n → [0, 1] is defined by for all X ⊆ B n . It is easy to verify that the Kolmogorov axioms are satisfied for the space (B n , 2 B n , P n ), so we have: Fact 1. The space (B n , 2 B n , P n ) with P n defined in (1) is a probability space.
The space (B n , 2 B n , P n ) is just the n-fold product of the single bit probability space (B, 2 B , P 1 ). For this reason this space is often called an "independent identicallydistributed bit source". The resulting space is "independent" because each bit is independent of previous ones. But what is "an independent probability space"?
Physically the independence of a QRNG is usually expressed as the impossibility of extracting any information from the flow of bits x 1 , . . . , x k−1 to improve chances of predicting the value of x k , other than what one would have from knowing the probability space. The fact that photon-based QRNGs obey this physical independence between photons (and thus generated bits) rather well [2,31] is the primary motivation for our modelling of these devices. These sources (where the condition of independence still holds) are often termed "independent-bit sources" [37]. In a real device we cannot, of course, expect each bit to be identically distributed, so we study this more general case more thoroughly in Section 3.5.
Formally, two events A, B ⊆ B n are independent (in a probability space) if the probability of their intersection coincides with the product of their probabilities [9] (a complexity-theoretic approach was developed in [14]). This motivates the definition of independence of a general source probability space given in Definition 3. But first we need the following simple property: Fact 2. For every bit-string x and non-negative integers n, k such that 0 ≤ k + |x| ≤ n we have: Fact 4. The probability space (B n , 2 B n , P n ) with P n defined in (1) is independent.
Proof. Using (2) we have: As we will see later, there are other relevant independent probability spaces.

Von Neumann normalisation function
Here we present formally the von Neumann normalisation procedure.
We define the mapping F : Note that for all x ∈ B we have F (f (x)) = x and, for all For m ≤ n/2 we define the normalisation function V N n,m : Fact 5. For all 1 < m ≤ n/2 and y ∈ B m there exists an x ∈ B n such that y = V N n,m (x).
In fact we can define the right inverse normalisation V N −1 n,m : 2 B m → 2 B n as for which V N n,n V N −1 n,m (y) = {y} holds for every y ∈ B m .

Target probability space and normalisation
We now construct the target probability space of the normalised bit-strings over B m for m ≤ n/2 , i.e. the probability space of the output bit-strings produced by the application of the von Neumann function on the output bit-strings generated by the QRNG. The von Neumann normalisation function V N n,m transforms the source probability space (B n , 2 B n , P n ) into the target probability space (B m , 2 B m , P n→m ). The target space of normalised bit-strings of length 1 < m ≤ n/2 associated to the source probability space (B n , 2 B n , P n ) is the space (B m , 2 B m , P n→m ), where P n→m : 2 B m → [0, 1] is defined for all Y ⊆ B m by the formula: . Proposition 6. The target space (B m , 2 B m , P n→m ) of normalised bit-strings of length 1 < m ≤ n/2 associated to the source probability space (B n , 2 B n , P n ) is a probability space.
Proof. We need to check only additivity:

Normalisation of the output of a source with constant bias
We now show that von Neumann procedure transforms the source probability space with constant bias into the probability space with the uniform distribution over B m , i.e. the target probability space (B m , 2 B m , P n→m ) has P n→m = U m , the uniform distribution. Independence and the constant bias of P n play a crucial role.
Theorem 7 (von Neumann). Assume that 1 < m ≤ n/2 . In the target probability space (B m , 2 B m , P n→m ) associated to the source probability space (B n , 2 B n , P n ) we have Proof. Since P n→m is additive it suffices to show that for any y ∈ B m , P n→m ({y}) = 2 −m . Let Z = P n V N −1 n,m (B m ) . We have (the sums are over all , which is independent of y. Since P n→m (B m ) = 1 and for all It is natural to check whether the independence and constant bias of the source probability space are essential for the validity of the von Neumann normalisation procedure.
Comment. One could present the above examples in the more general framework of Theorem 7.
The outcome of successive context preparations and measurements, such as is the case for the type of QRNG usually envisioned, are postulated to be independent of previous and future outcomes [19]. This means there must be no causal link between one measurement and the next within the system (preparation and measurement devices included) so that the system has no memory of previous or future events. For QRNGs this translates into the condition that the probability that each successive bit is either 0 or 1 is independent of the previous bit measured. We will only consider such independent probability spaces, as this is a necessary property of a good RNG, so most QRNGs are designed to conform to this requirement.
The above assumption needs to be made clear as in high bit-rate experimental configurations to generate QRNs with, e.g., photons, its validity may not always be clear. If the wave-functions of successive photons "overlap" the assumption no longer holds and (anti)bunching phenomena may play a role. This is an issue that needs to be more seriously considered in QRNG design and will only become more relevant as the bit-rate of QRNGs is pushed higher and higher. While we leave study of the nature of these temporal correlations (and any non-independence they may cause) to future research [2], we pose the following open question which may help to quantify any possible effect they may have.
Open Question. Fix an integer k ≥ 0 and small positive real κ. Consider the probability space (B n , 2 B n , P † n ) where P † n is a modification of the probability P n satisfying the conditions that for all i ≤ n and and for all l > k In other words, the probability of each bit depends on no more than the previous k bits, and the difference in probabilities for a bit between that given by P † n conditioned on the previous k bits and P n is no more than κ. If the output of such a source is normalised with the von Neumann procedure, how close is the resulting probability space of strings of length m to the uniform distribution (see Definition 18 for a definition of the closeness of probability spaces)?

Normalisation of the output of a source with non-constant bias
Now we consider the probability distribution obtained if von Neumann normalisation is applied to a string generated from an independent source with a non-constant bias-an "independent-bit source". We consider only a bias which varies smoothly; this excludes the effects of sudden noise which could make the bias jump significantly from one bit to the next. Such a source corresponds to a QRNG in which the bias varies slowly (drifts) from bit to bit over time, but never too far from its average point. We choose this to model photon-based QRNGs since the primary cause of variation in the bias will be of this nature. For example, the detector efficiencies may vary as a result of slow changes in temperature or power supply. While abrupt changes-which this model does not account for-are plausible, their relatively rare occurrence (in comparison with the bit generation rate in the order of MHz) will mean they have little effect on the resultant distribution.
Let p 0 , p 1 < 1 and p 0 + p 1 = 1 be constant. Let x = x 1 x 2 . . . x n ∈ B n be the generated string. Then define the probability of an individual bit x i being either zero or one as The variation in the bias is bounded, so we require that for all i, Furthermore, we assume that the "speed" of variation be bounded, i.e. there exists a positive δ such that for all i. Evidently we have δ ≤ β (presumably in any real situation δ β); however, we introduce two separate constants since they correspond to two physically different (but related) concepts. Note that we will discuss in more detail the importance of these two parameters for the approximation of the uniform distribution and their relevance to calibration of the QRNG later once the analysis is completed. Indeed, the rate of change, γ i , is more important; the need for β stems from the need to realise that, even though the probabilities can fluctuate, they can only fluctuate in one direction for so long (since For a string y = y 1 y k . . . y k ∈ B k and positive integer i we introduce, for convenience, the following notation: q i (y) = q y 1 i q y 2 i+1 · · · q y k i+k−1 . The following fact will allow us to evaluate the effect of normalisation on such a string.
Let us first formally define the probability space generated by this QRNG.
Proposition 13. The probability space of bit-strings produced by the QRNG is (B n , 2 B n , R n ) where R n : 2 B n → [0, 1] is defined for all X ⊆ B n as follows: Proof. We verify only that R n (B n ) = 1, which is easily shown since q 0 i + q 1 i = 1, and R n (B n ) = (q 0 1 + q 1 1 ) · · · (q 0 n + q 1 n ).
Proof. Using Fact 14 we get: Proof. Using (6) we have: As with the constantly biased source, we consider the probability space R n→m . We first investigate the simplest case n = 2m. In this situation, for any y ∈ B m we have

Approximating the uniform distribution
Unlike the case for a constantly biased source, we no longer have q i (01) = q i (10); from Fact 12 we have q i (01) = q i (10) + γ i . As a result the normalised equation is no longer the uniform distribution, but only an approximation thereof. We now explore how closely R n→m approximates U m . We first need to define what we mean by approximating U m .
Definition 18. The total variation distance between two probability measures P and Q over the space Ω is ∆(P, It is well known (see for example [37]) that The variation ∆(R n→m , U m ) depends on each γ i and q i (thus on p 0 , p 1 and each ε i ), but we wish to calculate the worst case in terms of the bounds δ, β and p 0 , p 1 , i.e. using Lemma 19, Let us first note that we can write , and hence we have We have rewritten the denominator in its original form to emphasise that only the signs (−1) y i depend on y. Thus, we want to find the values of q 2i−1 and γ 2i−1 which maximise subject to the constraints that |γ | ≤ δ and |ε | ≤ β for 1 ≤ ≤ n. Proof. We take 0 ≤ c i < 1 for 1 ≤ i ≤ n. For y = y 1 . . . y n ∈ B n define p(y, j) = n i=1,i =j (1 + (−1) y i c i ). Without loss of generality pick a j ≤ n and let ε > 0 be an (arbitrarily small) positive real with c j + ε ≤ 1. Note that We partition B n as follows: Note that for y ∈ B n , p(y, j) ≥ 0, and for y i ∈ Y i , i = 1, . . . , 5, we have p(y 5 , j) < p(y 4 , j) < p(y 3 , j) < p(y 2 , j) < p(y 1 , j), We have: where the final line follows from the definition of Y 2 and Y 4 . Since this holds for all j ≤ n, g is strictly increasing over [0, 1) n .

Lemma 21.
For every j ≥ 1 we have Proof. We omit the index j as it is not needed in this context. Let .
Since q(01) + q(10) > 0, in order to maximise u we look for maxima and minima of v; clearly maxima have γ > 0 and minima have γ < 0. We use Lagrange multipliers with inequality constraints to find the critical points. We have the following six constraints: We must solve the following equations: λ i ≥ 0 for minima, i = 1, . . . , 6, λ i ≤ 0 for maxima, i = 1, . . . , 6.
We say a constraint is inactive if λ i = 0 and active otherwise; the condition of complimentarity (13) captures the notion that a critical point satisfying the constraints either occurs at h i (ε, γ) = 0 or is also a critical point in the unconstrained problem. Noting that 0 < p 0 − β ≤ p 0 + β < 1 and solving, we find the candidate points are: Note that u(ε, γ) = u(ε + γ, −γ). Testing values shows the second case maximises u(ε, γ) when p 1 > p 0 and the third cases maximises u(ε, γ) for p 0 > p 1 . For p 0 = p 1 both cases give the same value. Substituting in ε, γ and consolidating the cases we arrive at (11).
Then we have Note that in this worst case, the normalised source acts as an independent and identicallydistributed source with p 0 = 1/2 ± α/2 and the total variation is bounded by that of two binomial sources: one with p 0 = 1/2, the other with p 0 = 1/2 ± α/2 (the number k of successful outcomes is identified with the number of ones in y).
There are two interesting questions: a) what is the quality of the distribution produced by a QRNG, i.e. how close are R n→m and U m in terms of α? and b) given a real ρ ∈ (0, 1), how accurate does the QRNG need to be in terms of α to guarantee that R n→m and U m are ρ close?
We can take a rough approach to solve the above problems as follows. First note that So given α, R n→m and U m are at most 1 2 We will express further results in the latter form, focusing on question b), although both are important questions depending on the operational circumstances and results can easily be transformed from one form to the other. So, by making α very small, R n→m can be made as close as we wish to the uniform distribution. This is intuitive since α → 0 only as δ → 0 and we approach the constantly biased source situation.
There are, unfortunately, some issues with this bound. First, as m → ∞ the bound on the variation becomes infinite too. This is unreasonable as by definition we should have ∆(R n→m , U m ) ≤ 1. It only makes sense to talk about ρ ≤ 1, although in any useful situation we will require ρ to be small (close to 0) so it is only of real importance that the bound is good in this situation. However, (16) requires α to be significantly smaller than we really require for the two probabilities to be ρ close. Even for small ρ the bound is noway near tight enough (see Figure 2). Further, it would be instructive to examine more correctly the behaviour for large m and investigate fully the nature of the relationship between α, m and ρ.
To rectify this and find a more reasonable bound, we carry out a finer analysis making use of the previous observation that this is the same problem as finding the variation between two binomial distributions. Let us denote a binomial probability distribution function for n trials and probability of success p as S n,p :
The total variation between two binomial distributions can be given in terms of regularised incomplete beta functions [3].
Definition 23. The incomplete beta function is defined as a, b) = B(a, b) for the complete beta function, or just beta function. The regularised incomplete beta function is defined as . Theorem 24. Let 0 ≤ p ≤ 1, q = 1 − p and 0 ≤ x ≤ q. The total variation between two binomial distributions with probability of success p and p + x is Proof. The first line is from Adell and Jodrá [3]. The rest follows from the well known properties of the beta functions: B (a, b) = B (b, a) and n k = 1 (n + 1)B(n − k + 1, k + 1) . This bound is exact (under the extrema given by Lemma 21), and we easily verify that ∆(R n→m , U m ) ≤ 1 since I p (a, b) ≤ 1 for all a, b and p ≤ 1, and for p ≥ p we have I p (a, b) ≥ I p (a, b) (with equality only for p = p ). Unfortunately this bound on the variation has no simple closed form, so we can not easily relate α, m and ρ like we did in (16). The shape and nature of this relationship can be seen for various values of m in Figure 1. In practice, with m fixed and given ρ it is easy to compute (with numerical methods) α such that ∆(R n→m , U m ) ≤ ρ. For relatively small ρ however, we can find a simple and fairly good bound which is easy to work with for rough approximations.

Theorem 25. The total variation is bounded by
Proof. We will take a first order (linear) approximation of ∆(S m,1/2 , S m,1/2(1+α) ) around α = 0. From Theorem 24 and the Fundamental Theorem of Calculus we have Since ≥ m/2 we have Φ(α) ≤ Φ(0), so our first order upper bound is given by Since the central binomial coefficient (i.e. n n/2 ) is the largest, for k ≤ m − 1 we have which can easily be shown by taking the two cases of m odd and m even. Since ≥ m/2 we have that Using the bounds given in Corollary 2.3, [33], and writing m = a m/2 where a ≤ 2, we have .
Hence, we have . This bound is much better than the bound given in (16), and for small α is extremely good. It has the desired properties that as α → 0, the bound on the variation tends to 0 also. Obviously this bound is not less than one for all α, but for small ρ the bound is very good, as can be seen in Figure 2.
Another interesting question refers to the possibility of manipulating the parameter α for fine calibration of the QRNG. For R n→m to become closer to U m we need to make α smaller, but this can be done by adjusting both δ and β. As previously discussed, both are reasonable physical parameters, and which one is the most suitable (or easiest) to decrease experimentally will to a large extent depend on the QRNG set-up itself. However, adjusting δ has a larger effect on α than adjusting β does, and R n→m will only approach U m arbitrarily close as δ → 0, as even with β = δ (recall δ ≤ β) we do not have α = 0 unless δ = 0.
These results can be extended to all m ≤ n/2, although the analysis is rather ellaborated. The key difference is that in the definition of R n→m in (7) the set V N −1 n,m (Y ) no longer has the same size as Y , so an additional summation is needed in the right hand side of (7). However, the total variation will still be maximised under the same conditions as in Lemmata 20 and 21, and the same relation as in Theorem 25 holds.
It is worth noting that the conditions which maximised the variation in (10) correspond to every ε i being the same up to a small variation δ. Physically this would indicate that p 0 , p 1 have been incorrectly stated, but that the device is actually rather accurate except for a small drift in probabilities of no more than δ. Since the parameters ε i are supposed to physically account for the amount the probability is allowed to drift, which will normally be much more than the drift between individual bits (the γ i ), if the device is calibrated so that p 0 and p 1 are centred so that the ε i are distributed around them, then the variation will not be nearly as bad as in this worst case. However, the bound on the variation remains valid as it is not necessarily meaningful (or useful) to look into the physical situation under which the worst case bound is achieved.
We briefly wish to point out that other methods for dealing with independent-bit sources have been proposed. For example, grouping bits into blocks of size and taking the parity of these bits for the "normalised" bit, produces a string of length n/ [37]. With this method each bit becomes unbiased exponentially fast in . However, the bound in Theorem 26 is asymptotically tighter than the corresponding bound that can be obtained by the parity method if the block size is fixed; if scales polynomially with n then this method produces a better bound, but at a substantial cost to the number of bits produced [37,Proposition 6.5]. The reason the von Neumann normalisation outperforms the parity method is due to the fact that the bias is required to vary slowly.

The infinite case
The extension of the above results to infinite sequences of bits produced by QRNGs is fairly straightforward, but forces us to address a few unexpected problems. First, we must extend the definition of the normalisation function V N n,m to sequences. We define V N : For convenience we also define V N n : Secondly, we introduce the probability space of infinite sequences as in [10]. Let A Q = {a 1 , . . . , a Q }, Q ≥ 2 be an alphabet with Q elements. We let P = {xA ω Q | x ∈ A * Q } ∪ {∅} and C be the class of all finite mutually disjoint unions of sets in P; the class P can be readily shown to generate a σ-algebra M. Using Theorem 1.7 from [10], the probabilities on M are characterised by the functions h : A * Q → [0, 1] satisfying: If Q = 2 so A 2 = B, and for x ∈ B n we take h(x) = P n ({x}) with P n as defined in Fact 1, then the above conditions are satisfied. This induces our probability measure µ P on M, which satisfies µ P (XB ω ) = P n (X) for X ⊆ B n . Hence the suitable extension of the finite case probability space to infinite generated sequences is the space (B ω , M, µ P ). In the special case when p 0 = p 1 we get the Lebesgue probability µ P L (XB ω ) = x∈X 2 −|x| .
In general, if Q ≥ 2, p i ≥ 0 for i = 1, . . . , Q are reals in [0,1] such that Q i=1 p i = 1, we can take h Q (x) = p is the number of occurrences of a i in x) to obtain the probability space (A ω Q , M, µ P Q ) in which µ P Q (xA ω Q ) = h Q (x), for all x ∈ A * Q . The first result notes that there exist sequences x ∈ B ω such that V N (x) ∈ B * . In fact every string can be produced via von Neumann normalisation from a suitable sequence.
Theorem 27. For every string y ∈ B * there exists an uncountable set R ⊂ B ω of µ P measure zero such that for all x ∈ R, V N (x) = y.
Proof. Let y = y 1 . . . y n ∈ B * and D = {00, 11}, the two-bit blocks which are deleted by von Neumann normalisation and y = f (y 1 ) . . . f (y n ). Then every sequence x ∈ y D ω satisfies V N (x) = V N 2n (x)V N (x 2n+1 x 2n+2 . . . ) = y since V N 2n (x) = V N 2n,2n (y ) = y and for all z ∈ D ω we have V N (z) = λ. Obviously, the set R = y D ω is uncountable and has µ P measure zero as the set of Borel normal sequences has measure one [10].
Proof. We simply note that the union of countably many measure zero sets also has measure zero.
It is interesting to note that the "collapse" in the generated sequence produced by von Neumann normalisation in Theorem 27 is not due to computability properties of the sequence. In particular, there are random sequences that collapse to any string, so to strings which are not Borel normal.
In the following we need a measure-theoretic characterisation of random sequences, so we present a few facts from constructive topology and probability.
Consider the compact topological space (A ω Q , τ ) in which the basic open sets are the sets wA ω Q , with w ∈ A * Q . Accordingly, an open set x is not contained in any constructively null set in (A ω Q , M, µ P Q ). For the case of the Lebesgue probability µ P L the measure-theoretic characterisation of random sequences holds true: x is random if and only if x is not contained in any constructively null set of (A ω Q , M, µ P L ) [25,10]. We continue with another instance in which von Neumann normalisation decreases randomness.
We follow this with instances for which the converse is true: von Neumann normalisation conserves or increases randomness. Proposition 30. There exist (continuously many) infinite 1/2-random sequences x ∈ B ω such that V N (x) is random.
Comment. Both Proposition 29 and 30 are true for the more general case of ε-random sequences, where 0 < ε < 1 is computable.
We briefly note that in the definition of Borel normality it does not matter if we count the number of non-overlapping occurrences of each string of length m, N m i (y) as defined in Section 2, or the number of overlapping occurrences, N m i (y) [22]. One of the main results of this section, presented in Theorem 31, is the following: Borel normality is invariant under von Neumann normalisation.
Hence, both limits exist and we have Since this holds for all m, i we have that V N (x) is Borel normal. ) be the probability space defined by the probabilities As T is prefixincreasing we naturally extend T to sequences to obtain the function T : Proof. Take w = w 1 . . . w m ∈ A ω Q−1 . We have: Proof. We generalise a result in [12] stating that, for the Lebesgue probability, measure-preserving transformations preserve randomness. Assume that x is random in there is a constructive null set R = (G m ) m≥1 containing T (x). Assume that G m = X m A ω Q−1 , where X m ⊂ A ω Q−1 is c.e. and has the measure µ P T } and, using Lemma 32, has the measure smaller than 2 −m : We have proved that x is not random in (A ω Q , M, µ P Q ), a contradiction.
and for X ⊆ B * as For all x ∈ B * and y ∈ V N −1 (x)B ω we then have x < V N (y). For the cases that V N (x) ∈ B ω , the probability space (B ω , M, µ P V N ) induced by von Neumann normalisation is endowed with the measure µ P V N . The measure µ P V N is defined on the sets xB ω with x ∈ B * by .

By noting that
it is clear to see that µ P V N satisfies the Kolmogorov axioms for a probability measure. While the set V N −1 (B |x| ) contains sequences for which normalisation produces a finite string, from Corollary 28 we know that the set of such sequences have measure zero, so the definition of µ P V N is a good model of the target probability space. We thus arrive at the key result that (measure-theoretical) randomness is invariant under von Neumann normalisation.
Theorem 34. Let x ∈ B ω be random in (B ω , M, µ P ). Then V N (x) ∈ B ω is also random in (B ω , M, µ P V N ).
Proof. We write the random sequence x as x = x 1 x 2 . . . x n · · · = (x 1 x 2 ) . . . (x 2n−1 x 2n ) · · · ∈ {00, 01, 10, 11} ω . Renaming a = 00, A = 01, B = 10, b = 11 and consistently deleting first all occurrences of a we get a random sequence x A,B ,b on the alphabet {A, B, b}, then deleting all occurrences of b we get a random sequence x A,B on the alphabet {A, B}. The result follows from the fact that V N (x) = x 0,1 and Proposition 33 stating that x A,B is random.
Proof. From Theorem 34 it follows that V N (x) is Borel normal provided x is random [10].
Theorem 36. The probability space (B ω , M, µ P V N ) induced by von Neumann normalisation is the uniform distribution (B ω , M, µ P L ), where µ P L is the Lebesgue measure.
Proof. By Lemma 32 von Neumann normalisation is measure preserving, so for x ∈ B * we have The key point, as in the finite case, is that this only depends on |x| not x itself. By using the fact that for any n, x∈B n µ P V N (xB ω ) = 1, we have for all x ∈ B * , and hence µ P V N = µ P L , the Lebesgue measure.
This can easily be extended from the case when V N (x) is infinite, to the case in which it is finite. To do so, note that if y ∈ B ω and V N (x) = y ∈ B n , then the probability space induced by von Neumann normalisation is (B n , 2 B n , P * n ). We then have , and since the denominator is constant for all x ∈ B n , we can proceed as for above, and P * n = U n as desired.
is computable } has measure zero with respect to the probability space (B ω , M, µ P ).
Proof. By Theorem 34 we deduce that which has measure zero [25]. To complete the proof, note that we know from Corollary 28 that the set {x ∈ B ω | V N (x) ∈ B * } also has measure zero.

Role of probability spaces for QRNGs
The treatment of QRNGs as entirely probabilistic devices is grounded purely on the probabilistic treatment of measurement in quantum mechanics which originated with Born's decision to "give up determinism in the world of atoms" [8], a viewpoint which has become a core part of our understanding of quantum mechanics. This is formalised by the Born rule, but the probabilistic nature of individual measurement is nonetheless postulated and tells us nothing about how the probability arises. Along with the assumption of independence this allows us to predict the probability of successive events, as we have done.
No-go theorems such as the Kochen-Specker Theorem [21] tell us something stronger: if we assume non-contextuality (i.e. that the result of an observation is independent of the compatible observables are co-measured alongside it [5,17]) then there can, in general, be no pre-existing definite values prescribable to certain sets of measurement outcomes in dimension three or greater Hilbert space. In other words, the randomness is not due to ignorance of the system being measured; indeed, since there are in general no definite values associated with the measured observable it is surprising there is an outcome at all [35]. While this does not answer the question as to where the randomness arises from, it does tell us something stronger than the Born Rule does. In [13] it is shown that every infinite sequence produced by a QRNG is (strongly) incomputable. In particular, this implies that it is impossible for a QRNG to output a computable sequence. The set of computable numbers has measure zero with respect the probability space of the QRNG, but the impossibility of producing such sequence is much stronger than, although not in contradiction with, the probabilistic results.
In the finite case every string is, of course, obtainable, and we would expect the distribution to be that predicted by the probability space derived from the Born Rule. However, the infinite case has something to say here too. We can view any finite string produced by a QRNG as the initial segment of an infinite sequence the QRNG would produce if left to run indefinitely. For any infinite sequence produced by the QRNG, it is impossible to compute the value of any bit before it is measured [1]; in the finite case this means there is no way to provably compute the value of the next bit before it is measured. In light of value indefiniteness this is not unexpected, but nonetheless gives mathematical grounding to the postulated unpredictability of each individual measurement, as well as the independence of successive measurements-indeed we can rule out any computable causal link within the system which may give rise to the measurement outcome.
The results we have presented in this paper, however, describe thoroughly the distribution of strings/sequences produced by QRNGs. With the distributions known we can create more intelligent tests of the quality of output of a QRNG [11]. Current statistical tests for analysing RNGs are designed with pseudo-RNGs in mind, and are not necessarily the best way to test the quality of QRNGs. The effects of normalisation on strings generated by QRNGs can help us design QRNGs which are more robust to experimental imperfection and exhibit the desired behaviour. It will further aid in developing new normalisation techniques designed to produce the expected (ideal) theoretical distribution even in the absence of experimental imperfections.

Conclusions
The analysis developed in this paper involves the probability spaces of the source and output of a QRNG and the effect von Neumann normalisation has on these spaces.
In the "ideal case", the von Neumann normalised output of an independent constantly biased QRNG is the probability space of the uniform distribution (un-biasing). This result is true for both for finite strings and for the infinite sequences produced by QRNGs (the QRNG runs indefinitely in the second case).
For a real-world QRNG in which the bias, rather than holding steady, drifts slowly, we evaluated the speed of drift required to be maintained by the source distribution to guarantee that the output distribution is arbitrarily close to the uniform distribution. It is an open question to study the quality of von Neumann normalisation in the more realistic case when, instead of the bits being independent, the probability for each bit depends on a finite number of preceding bits (for example, because of the high bit-rate of the experiment). Note that Blum's algorithm [7] assumes a Markov-type correlation, which cannot be assumed for a QRNG certified by value indefiniteness [2].
We have also examined the effect von Neumann normalisation has on various properties of infinite sequences. In particular, Borel normality and (algorithmic) randomness are invariant under normalisation, but for ε-random sequences with 0 < ε < 1, normalisation can both decrease or increase the randomness of the source. It is an open question whether von Neumann normalisation preserves randomness and Borel normality for finite strings.
Finally, we reiterate that a successful application of von Neumann normalisationin, fact, any un-biasing transformation-does exactly what it promises, un-biasing, one (among infinitely many) symptoms of randomness; it will not produce "true" randomness.