1 Introduction

Roughly speaking, randomness is the fact that, even using all the information that we have about a physical system, in some situations it is impossible, or unfeasible, for us to predict exactly what will be the future state of that system. Randomness is a facet of nature that is ubiquitous and very influential in our society and in others [1–3]. As a consequence, it is also an essential aspect of our science and technology. The related research theme, that was motivated initially mainly by gambling and led eventually to probability theory [4, 5], is nowadays a crucial part of many different fields of study such as computational simulations, information theory, cryptography, statistical estimation, system identification, and many others [6–12].

One rapid-growing area of research for which randomness is a key concept is the maturing field of quantum information science (QIS). Our main aim in this interdisciplinary field is understanding how quantum systems can be harnessed in order to use all Nature’s potentialities for information storage, processing, transmission, and protection [13–15].

Quantum mechanics [16, 17] is at present one of the fundamental theories of Nature. The essential mathematical object in this theory is the density operator (or density matrix) ρ. It embodies all our knowledge about the preparation of the system, i.e., about its state. From the mathematical point of view, a density matrix is simply a positive semi-definite matrix (notation: ρ≥0) with trace equal to one (Tr(ρ)=1). Such kind of matrix can be written as \(\rho ={{\sum }_{\mathrm {j}}}r_{\mathrm {j}}{\Pi }_{\mathrm {j}}\), which is known as the spectral decomposition of ρ. In the last equation, πj is the projector (πjπk=δ jkπj and \({\sum }_{\mathrm {j}}{\Pi }_{\mathrm {j}}=\mathbb {I}_{\mathrm {d}}\), where \(\mathbb {I}_{\mathrm {d}}\) is the d−dimensional identity matrix). From the positivity of ρ follows that, besides it being Hermitian and hence having real eigenvalues, its eigenvalues are also non-negative, r j ≥0. Since the trace function is base independent, the eigenvalues of ρ must sum up to one, \(\text {Tr}(\rho )=\textstyle {{\sum }_{j}}r_{\mathrm {j}}=1\). Thus, we see that the set {r j} possesses all the features that define a probability distribution (see, e.g., Ref. [4]).

The generation of pseudo-random quantum states is an essential tool for inquires in QIS (see, e.g., Refs. [18–30]) and involves two parts. The first one is the generation of pseudo-random sets of projectors {πj}, that can be cast in terms of the creation of pseudo-random unitary matrices. There are several methods for accomplishing this last task [31–34], whose details shall not be discussed here. Here, we will address the second part, which is the generation of pseudo-random discrete probability distributions [35–37], dubbed here as pseudo-random probability vectors (pRPV).

In this article, we go into the details of three methods for generating numerically pRPV. We present the problem details in Section 2. The Section 3 is devoted to present a simple method, the iid method, and to show that it is not useful for the task regarded in this article. In Section 4, the standard normalization method is discussed. The bias of the pRPV appearing in its naive-direct implementation is highlighted. A simple solution to this problem via random shuffling of the pRPV components is then presented. In Section 5, we consider the trigonometric method. After discussing some issues regarding its biasing and numerical implementation, we study and compare the probability distribution generated and the computer time required by the last two methods when the dimension of the pRPV is varied. The conclusions and prospects are presented in Section 6.

2 The Problem

By definition, a discrete probability distribution [4] is a set of non-negative real numbers,

$$ p_{j}\ge0, $$
(1)

that sum up to one,

$$ {\sum}_{j=1}^{d} p_{\mathrm{j}} = 1. $$
(2)

In this article, we will utilize the numbers p j as the components of a probability vector

$$ \mathbf{p} = (p_{1}, \cdots, p_{\mathrm{d}}). $$
(3)

Despite the lack of consensus regarding the meaning of probabilities [4], here we can consider p j simply as the relative frequency with which a particular value x j of a physical observable modeled by a random variable X is obtained in measurements of that observable under appropriate conditions.

We would like to generate numerically a pseudo-random probability vector p whose components \(\{p_{\mathrm {j}}\}_{\mathrm {j=1}}^{d}\) form a probability distribution, i.e., respect (1) and (2). In addition, we would like the pRPV to be unbiased, i.e., the components of p must have similar probability distributions. A necessary condition for fulfilling this last requisite is that the average value of p j (notation: 〈p j〉) becomes closer to 1/d as the number of pRPV generated becomes large.

At the outset, we will need a pseudo-random number generator (pRNG). In this article, we use the Mersenne Twister pRNG [38], that yields pseudo-random numbers (pRN) with uniform distribution in the interval [0,1]. We observe however that the results reported in this article can also be applied when dealing with true random numbers [39, 40].

3 The iid Method

A simple way to generate an unbiased pseudo-random probability vector p=(p 1,⋯ ,p d) is as follows. If we create d independent pseudo-random numbers x j with identical probability distributions in the interval [0,1] (so the name of the method) and set

$$ p_{j} := \frac{x_{j}}{{\sum}_{k=1}^{d}x_{k}}, $$
(4)

we will obtain a well-defined discrete probability distribution, i.e., p j≥0 and \({\sum }_{\mathrm {j}=1}^{d}p_{\mathrm {j}}=1\). Besides, as p is unbiased, the mean value of p j approaches 1/d as the number of samples grows.

Nevertheless, we should note that the sum \({\sum }_{\mathrm {k}=1}^{d}x_{\mathrm {k}}\) shall be typically greater than one. This in turn will lead to the impossibility for the occurrence of pRPVs with one of its components equal (or even close) to one. As can be seen in Fig. 1, this problem becomes more and more important as d increases. Therefore, this kind of drawback totally precludes the applicability of the iid method for the task regarded in this article.

Fig. 1
figure 1

(color online) Probability distribution for the first component of the unbiased probability vector p=(p 1,⋯ ,p d) for one million random samples generated using the iid method. The inset shows the probability distribution for the components of the probability vector p=(p 1,p 2,p 3,p 4)

Full size image

4 The Normalization Method

Lets us begin our discussion of this method by considering a probability vector with dimension d=2, i.e., p=(p 1,p 2). If the pRNG is used to obtain p 1∈[0,1] and we impose the normalization to get p 2=1−p 1, we are guaranteed to generate an uniform distribution for p j∈[0,1] for both j=1 and j=2.

If d=3 then p=(p 1,p 2,p 3) and the pRNG is used again (two times) to obtain p 1∈[0,1] and p 2∈[0,1−p 1]. Note that the interval for p 2 was changed because of the normalization of the probability distribution, which is also used to write p 3=1−(p 1+p 2). As p 1 is equiprobable in [0,1], for a large number of samples of the pRPV, its mean value will be 1/2. This shall restrict the values of the other components of p, shifting the “center” of their probability distributions to 1/4, thus biasing the pRPV. Of course, if one increases the dimension of the pRPV, the same effect continues to be observed, as is illustrated in the table below for 106 pRPV generated for each value of d.

Table 1
Full size table

The probability distributions for the four components of the probability vector p=(p 1,p 2,p 3,p 4) are shown in Fig. 2. For the sake of illustration, the spaces for the pRPV are sketched geometrically in Fig. 3 for the cases d=2 and d=3. We observe that the procedure for generating p as explained above is the motivation for the name of the method, the normalization method.

Fig. 2
figure 2

(color online) Probability distribution for the components of the biased probability vector p=(p 1,p 2,p 3,p 4) for one million random samples of it. The inset shows the probability distribution for the components of the unbiased probability vector q=(q 1,q 2,q 3,q 4)

Full size image
Fig. 3
figure 3

(color online) Set of possible values for the components of the probability vector in the cases of d=2 (figure on the top) and for d=3 (figure on the bottom). For higher dimensions, the probability space is a hyperplane

Full size image

A simple solution for the biasing problem just discussed is shuffling the components of the pRPV in each run of the numerical experiment. This can be done, for example, by generating a random permutation of {1,2,⋯ ,d−1,d}, let us call it {k 1,k 2,⋯ ,k d−1,k d}, and defining a new pRPV as

$$\begin{array}{@{}rcl@{}} \mathbf{q} & = & (q_{1},q_{2},{\cdots} , q_{\mathrm{d}-1},q_{\mathrm{d}})\\ & := & (p_{\mathrm{k}_{1}},p_{\mathrm{k}_{2}},{\cdots} , p_{\mathrm{k}_{\mathrm{d}-1}},p_{\mathrm{k}_{\mathrm{d}}}). \end{array} $$
(5)

In the table below, the mean value of the components of q is presented, for 106 pRPV generated.

Table 2
Full size table

In the inset of Fig. 2, an example with the resulting probability distributions for the four components of q=(q 1,q 2,q 3,q 4) is presented.

From the discussion above we see that in addition to the d−1 pRN needed for the biased pRPV, we have to generate another d−1 pRN for the shuffling used in order to obtain an unbiased pRPV (because \({\sum }_{\mathrm {j}=1}^{d}j=d(d+1)/2\)), resulting in a total of 2(d−1) pRN per pRPV.

5 The Trigonometric Method

As the name indicates, this method uses a trigonometric parametrization [35, 37] for the components of the probability vector \(\vec {p}=(p_{1},\cdots ,p_{\mathrm {d}})\):

$$ p_{\mathrm{j}}:=\sin^{2}\theta_{\mathrm{j}-1} {\prod}_{\mathrm{k}=\mathrm{j}}^{d-1}\cos^{2}\theta_{\mathrm{k}}, $$
(6)

with 𝜃 0=π/2 (so the name trigonometric method). More explicitly,

$$\begin{array}{@{}rcl@{}} p_{1}&=&\sin^{2}\theta_{0}\cos^{2}\theta_{1}\cos^{2}\theta_{2}\cos^{2}\theta_{3}\cdots\cos^{2}\theta_{d-1} \\ p_{2}&=&\sin^{2}\theta_{1}\cos^{2}\theta_{2}\cos^{2}\theta_{3}\cdots\cos^{2}\theta_{d-1} \\ p_{3}&=&\sin^{2}\theta_{2}\cos^{2}\theta_{3}\cos^{2}\theta_{4}\cdots\cos^{2}\theta_{d-1} \\ &&\vdots \\ p_{\mathrm{d}-1}&=&\sin^{2}\theta_{\mathrm{d}-2}\cos^{2}\theta_{\mathrm{d}-1} \\ p_{\mathrm{d}}&=&\sin^{2}\theta_{\mathrm{d}-1}. \end{array} $$
(7)

A simple application of the equality \(\cos ^{2}\theta _{\mathrm {j}}+\sin ^{2}\theta _{\mathrm {j}}=1\) to this last equation shows that p j ≥0 and \({\sum }_{\mathrm {j}=1}^{d}p_{\mathrm {j}}=1\). Therefore, this parametrization, which utilizes d−1 angles 𝜃 j, leads to a well-defined probability distribution \(\{p_{\mathrm {j}}\}_{\mathrm {j}=1}^{d}\).

Let us regard the numerical generation of an unbiased pseudo-random probability vector by starting with the parametrization in (6). Of course, this task is accomplished if the components of the pRPV are created with uniform probability distributions. Thus, we can proceed as follows. We begin with p d and go all the way to p 1 imposing that each p j must be uniformly distributed in [0,1]. Thus, we must have

$$ \theta_{\mathrm{d}-1}=\arcsin\sqrt{t_{\mathrm{d}-1}} $$
(8)

and the other angles 𝜃 j, with j=1,⋯ ,d−2, should be generated as shown in the next equation:

$$ \theta_{\mathrm{j}}=\arcsin\sqrt{\frac{t_{\mathrm{j}}}{{\prod}_{\mathrm{k}=\mathrm{j}+1}^{d-1}\cos^{2}\theta_{\mathrm{k}}}}, $$
(9)

where t j, with j=1,⋯ ,d−1, are pseudo-random numbers with uniform distribution in the interval [0,1]. For obvious reasons, this manner of generating a pRPV is very unstable, and therefore inappropriate, for numerical implementations.

A possible way out of this nuisance is simply to ignore the squared cosines in the denominator of (9). That is to say, we may generate the angles using, e.g.,

$$ \theta_{\mathrm{j}}=\arccos\sqrt{t_{\mathrm{j}}} $$
(10)

for all j=1,⋯ ,d−1. This procedure will give us an uniform distribution for \(\cos ^{2}\theta _{\mathrm {j}}\) and \(\sin ^{2}\theta _{\mathrm {j}}\), but will also increase the chance for the components p j with more terms to have values closer to zero. Thus, there is the issue of a biased pRPV again. A possible solution for this problem is, once more, shuffling. The next two tables show the average value of the components of 106 pRPV generated via the trigonometric method before, 〈p j〉, and after, 〈q j〉, shuffling.

Table 3
Full size table

As was the case with the normalization method, for the trigonometric method, we need to generate 2(d−1) pRN per pRPV, d−1 for the angles and d−1 for the random permutation. Nevertheless, because of the additional multiplications in (6), the computation time for the last method is in general a little greater than that for the former, as is shown in Fig. 4.

Fig. 4
figure 4

(color online) Log-log plot of the computation time required by the trigonometric method (blue squares) and by the normalization method (red circles) to generate a pseudo-random probability vector with dimension equal to d. The calculations were realized using a Processor 1.3 GHz Intel Core i5.

Full size image

One may wonder if the normalization and trigonometric methods, that are at first sight distinct, lead to the same probability distributions for the pRPV’s components and also if they produce an uniform distribution for the generated points in the probability hyperplane. We provide some evidences for positive answers to both questions in Figs. 5 and 6, respectively.

Fig. 5
figure 5

(color online) Semi-log plot of the probability distributions for a component of the unbiased probability vectors generated using the trigonometric (lines) and normalization (points) methods for some values of d. We see that the two methods yield, for all practical purposes, the same probability distributions for the components of the pRPV

Full size image
Fig. 6
figure 6

(color online) Sample with five thousand pRPV generated using the indicated method. We see that in this case, for which d=3, with exception of the slight overpopulated corners, we get a fairly uniform distribution of points in the probability space

Full size image

6 Concluding Remarks

In this article, we discussed thoroughly the three methods for generating pseudo-random discrete probability distributions. We showed that the iid method is not a suitable choice for the problem studied here and identified some difficulties for the numerical implementation of the trigonometric method. The fact that in a direct application of both the normalization and trigonometric methods, one shall generate biased probability vectors was emphasized. Then the shuffling of the pseudo-random probability vector components was shown to solve this problem at the cost of the generation of additional d−1 pseudo-random numbers for each pRPV.

It is worthwhile recalling that pure quantum states in \(\mathbb {C}^{d}\) can be written in terms of the computational basis \(\{|c_{j}\rangle \}_{j=1}^{d}\) as follows:

$$ |\psi\rangle = {\sum}_{\mathrm{j}}c_{j}|c_{\mathrm{j}}\rangle = {\sum}_{\mathrm{j}} |c_{\mathrm{j}}|\mathrm{e}^{\phi_{j}}|c_{\mathrm{j}}\rangle = {\sum}_{\mathrm{j}} \sqrt{p_{\mathrm{j}}}\mathrm{e}^{\phi_{\mathrm{j}}}|c_{\mathrm{j}}\rangle, $$
(11)

where \(c_{\mathrm {j}}\in \mathbb {C}\) and \(\phi _{\mathrm {j}}\in \mathbb {R}\). The normalization of |ψ〉 implies that the set {p j} is a probability distribution. Thus, the results reported in this article are seen to have a rather direct application for the generation of unbiased pseudo-random state vectors.

We observe however that the content presented in this article can be useful not only for the generation of pseudo-random quantum states in quantum information science, but also for stochastic numerical simulations in other areas of science. An interesting problem for future investigations is with regard to the possibility of decreasing the number of pRN, and thus the computer time required for generating an unbiased pRPV.