Discrete uniform and binomial distributions with infinite support

In this paper, we are interested in properties of two probability distributions defined on the infinite set \(\{0,1,2, \ldots \}\) and generalizing the ordinary discrete uniform and binomial distributions. Both of these extensions have been recently discussed in Calude and Dumitrescu (2020) and mentioned in Zhigljavsky (2012); both extensions use the notion of grossone. The grossone, introduced in Sergeyev (2013) and denoted by \(\textcircled {1}\), is a model of infinity which, as shown in Sergeyev (2009), Sergeyev (2017) and many other publications can be very useful in solving diverse problems of computational mathematics and optimization; in such applications, \(\textcircled {1}\) is used as numerical infinity. Grossone can also be useful as a theoretical model of infinity, see, e.g., (Zhigljavsky 2012; Sergeyev 2017). Some historical, philosophical and logical aspects of grossone have been considered in Lolli (2012), Lolli (2015), Hansson (2020). In Sect. 1, we consider and briefly discuss postulates of \(\textcircled {1}\).

For a positive integer n, the discrete uniform distribution on the set \(\{0,1, \ldots , n-1\}\) assigns equal mass 1/n to all integers \(j\in \{0, \ldots , n-1\}\). We use the notation DU(n) from Balakrishnan and Nevzorov (2004) for this distribution. An extension of this distribution to the infinite set \(\{0,1,2 \ldots \}\) is denoted by DU\((\infty )\) and is used in Bayesian statistics as vague prior (often called ‘Jeffrey’s prior’) for large integer-valued parameters, in particular for the parameter N in the binomial distribution Bin (N, p), see, e.g., (Raftery 1988). An extension of DU(n) to DU\((\textcircled {1})\) is straightforward: for a random variable (r.v.) \(\xi \sim \)DU\((\textcircled {1})\), we have \(\mathrm{Pr} \{ \xi = k \}=1/(\textcircled {1})\) for all \(k \in \{0,1, \ldots ,\textcircled {1}-1\}\). This distribution has been considered, in particular, in Calude and Dumitrescu (2020). The distribution DU\((\textcircled {1})\) is easier than DU\((\infty )\): indeed, DU\((\infty )\) is a vague (improper) distribution but, if one agrees to perform calculations with \(\textcircled {1}\), DU\((\textcircled {1})\) is a well-defined distribution, very similar to DU(n).

In Sect. 2.2, we consider the problem of decomposing a random variable \(\xi \sim \) DU\((\textcircled {1})\) into sums \(\xi {\mathop {=}\limits ^\mathrm{d}} \xi _1 + \ldots + \xi _m\), where \(\xi _1 , \ldots , \xi _m\) are independent non-degenerate random variables and the equality \({\mathop {=}\limits ^\mathrm{d}}\) means that the distributions of the random variables in the lhs and rhs of the equation are equal. In particular, we shall establish that DU\((\textcircled {1})\) is not an infinitely divisible distribution which might have been expected in view of results of Warde and Katti (1971).

The probability mass function (pmf) for Bin(N, p), the binomial distribution with parameters N and p, iswhere N is usually interpreted as the number of Bernoulli trials and p as the probability of success in these trials. We are interested in approximating the binomial probabilities (3) in the case when N is (very) large but p is rather small like \(p=c/N^{\alpha }\) with finite \(c>0\) and \(1/2<\alpha \le 1\). This case is important for understanding the distribution Bin\((\textcircled {1},p)\), the grossone extension of Bin(N, p).

According to the central limit theorem, for any p and large N, the distribution [Bin(\(N,p)-Np]/\sqrt{Np(1-p)}\) is approximately the standard normal distribution \({{\mathcal {N}}}(0,1)\) and, therefore, the binomial distribution Bin(N, p) can be approximated by the normal distribution \( {{\mathcal {N}}}(Np,{Np(1-p)}). \) However, if p is small then, even for very large N, this normal approximation is very poor, especially in the tails, see for example (Berry 1941). Also, the support of the random variable with distribution \({{\mathcal {N}}}(Np,Np(1-p))\) barely resembles the support of Bin(N, p) and this could be a serious problem in practice. There are many improvements to the normal approximation, see, e.g., (Brown et al. 2001). However, even corrected normal approximations are rather poor in approximating tails; in particular, the approximations based on the Edgeworth expansion do not guarantee that the approximations to individual binomial probabilities are non-negative, see for example (Petrov 1995) for an excellent account of different approximations in the CLT. Even the shape of the normal approximation \( {{\mathcal {N}}}(Np,Np(1-p))\) may be misleading. Consider, for instance, the skewness which is the widely accepted characteristic of a non-symmetry of distributions. The skewness of \({{\mathcal {N}}}(0,1)\) is zero, whereas the skewness of [Bin(\(\textcircled {1}\),p)\(-p\) \(\textcircled {1}\) \(]/\sqrt{p(1-p)\textcircled {1}}\) is \( \gamma _1={{(2p-1)/\sqrt{p(1-p)\textcircled {1}}}.} \) As an example, for \(p=\lambda /\textcircled {1}\) we have \(\gamma _1=1/\sqrt{\lambda } + O(\textcircled {1}^{-1})\) which shows that even if N is very large, the binomial distribution Bin(N, p) can still be very asymmetric for small p, even after the renormalization.

Bearing in mind that the normal approximation to Bin(N, p) cannot be suitably corrected if p is small, in Sect. 3 we will concentrate on correcting the Poisson approximation to Bin(N, p) assuming that N is very large but p is of order \(p=c/N^{\alpha }\) with finite \(c>0\) and \(1/2<\alpha \le 1\).

One of the central concepts used below is the concept of grossone which has been introduced in Sergeyev (2013), developed in a series of papers by Ya. Sergeyev and coauthors and recently comprehensively reviewed in Sergeyev (2017). Grossone can be defined axiomatically, see (Sergeyev 2017). The two main axioms are given below.

The grossone models infinity. Similarly, the quantities like \(1/\textcircled {1}\) and \(1/\textcircled {1}^2\) model infinitesimals. These models, as comprehensively discussed in Sergeyev (2017), are very useful as theoretical models and as models of numerical infinity and infinitesimals. A very attractive feature of these numerical infinity and infinitesimals is a possibility to operate with them in numerical fashion, exactly as with numbers (rather than with symbols like in MAPLE); this feature is the key concept of the ‘infinity computer’ discussed in many publications of Ya. Sergeyev and coauthors, see (Sergeyev 2009, 2017).

In mathematics, a more common approach to model infinitesimal quantities is to use the framework of the non-standard analysis. The non-standard analysis approach for modeling infinitesimal probabilities has been recently discussed in Benci et al. (2018). Modeling infinitesimal probabilities with \(1/\textcircled {1}\) and similar quantities involving \(\textcircled {1}\) has also attracted serious attention, see (Calude and Dumitrescu 2020; Sergeyev 2017; Rizza 2018). One of an attractive features of the grossone-based approach is that one may simultaneously work with infinitesimal probabilities of different order like \(1/\textcircled {1}\) and \(1/\textcircled {1}^2\). It should be stressed that the grossone-based methodology is different from the approach based on the non-standard analysis, see (Sergeyev 2019).

The pmf for Poi\((\lambda )\), the Poisson distribution with parameter \(\lambda \), is defined byThere is a lot of literature on the accuracy of Poisson approximation to Bin(N, p), see for example (Hodges and Le Cam 1960; Duembgen et al. 2019). If we are not interested in approximating tails of the Binomial distribution, then Poisson approximation Poi\((\lambda )\) to Bin(N, p) is rather accurate when \(\lambda =pN\) is not too large. However, unless \(\lambda \) is small enough, Poi\((\lambda )\) does not approximate tails of Bin(N, p) well even if N is very large. There are several approaches for correcting the Poisson approximation including the Stein–Chen method, see (Barbour et al. 1992). Among these asymptotic corrections, the most known is based on the use the expansion with respect to the Charlier polynomials. This expansion has been developed in Uspensky (1931) and can be written as follows:where \(\lambda =p/N\), \(b_x\) and \(p_x\) are defined by (3) and (5), respectively, \({\tilde{c}}_j(x;\lambda )= \lambda ^j {c}_j(x;\lambda )\) and \({c}_j(x;\lambda )\) are the Charlier polynomialsWe will derive an alternative improvement to the Poisson approximation which, as we will demonstrate, is very accurate at the lower tail of the binomial distribution Bin(N, p) with very large N and very small p; the value of \(\lambda =Np\) could be rather large but smaller than \(\sqrt{N}\).

To start with, we rearrange the binomial probability \(b_x\) as followsAssume N is large enough and \(p=\lambda /N\). For all \(\lambda x<\!<N\), we havewithwhere \(x_{(j)}=x(x-1)\ldots (x-j+1)\) is the falling factorial. The series (8) converges if \(\lambda x /N \rightarrow 0\) as \(N \rightarrow \infty \).

Now, consider Q of (7):whereUsing the expansion \(e^{-y}= 1+\sum _{m=1}^\infty (-1)^m y^m /m! \) and writing \(y^m\) in the form of the multiple sumwe obtainCollecting the terms by powers of 1/N, we obtainwhere the first four polynomials \(Q_j(\lambda )\) areThe series (9) converges if \(\sqrt{\lambda }/N \rightarrow 0 \) as \(N \rightarrow \infty \).

For the term R of (7), we have:where the first four polynomials \(R_j(x)\) areCombining (7)–(10), we obtain the following expansion for the probability \(b_x\):All the series converge if \(\lambda x /N \rightarrow 0\) as \(N \rightarrow \infty \). If \(\lambda x /N \) does not tend to 0 as \(N \rightarrow \infty \), but x/N and \(\sqrt{\lambda } /N \) do, then we recommend to use the approximationwhere the term T of (7) is not expanded. Numerical results show that for x in the left tail of the binomial distribution, the approximations (11) and (12) practically coincide if we get enough terms in the expansion for T.

Let us rewrite the result (11) in terms of the binomial probabilities of Bin\((\textcircled {1},\lambda /\textcircled {1})\) keeping only two main terms in the expansion:This formula makes sense in the grossone universe. Indeed, both \(\lambda \) and x could be infinitely large but \((\lambda +x)^2/\textcircled {1} \) should be kept infinitesimal as otherwise the second and third terms in the rhs of (13) become large. In particular, the expansion (13) is valid if \(\lambda =c_1 \textcircled {1}^\alpha \) and \(x=c_2 \textcircled {1}^\beta \) where \(c_1\) and \(c_2\) are finite constants and both \(\alpha \) and \(\beta \) are smaller than 1/2.

In Figs. 1, 2 and 3, we demonstrate accuracy of several approximations for \(b_x\) in (3) by plotting the ratio \({\tilde{b}}_x/b_x\) where \({\tilde{b}}_x\) is an approximation for \(b_x\). We have chosen the following coding for the x axis: “0” is the mean \(\lambda =Np\) of the distribution Bin(N, p) and \(j= \pm 1, \pm 2, \ldots \) denote the points \(\lambda +js\), where \(s=\sqrt{Np(1-p)}\) is the standard deviation of Bin(N, p) .

In Figs. 1, 2 and 3, we have chosen \(p=0.03\) and \(N=10^3,10^4,10^5\) so that \(\lambda =30,300\) and 3000. The normal approximation (depicted by black solid line) is always very poor. Due to incorrect skewness, the normal approximation considerably underestimates the probabilities \(b_x\) for \(x<\lambda \) overestimates them for \(x>\lambda \). We have tried to use several improved normal approximations, in particular, the ones based on the Edgeworth expansion, but these expansions were not much better and in many cases some of the estimators \({\tilde{b}}_x\) became negative. Uncorrected Poisson approximation (blue dashed line) is slightly more accurate than normal, but it is still quite poor. The corrected Poisson approximations (6), based on the expansion with respect to the Charlier polynomials, significantly improve the Poisson approximation. The first-order Charlier approximation (red dotted line), where we keep only the term \({\tilde{c}}_2(x;\lambda )/{2N} \) in (6), works well for x within the \(3\sigma \)-interval; the second-order Charlier approximation is very accurate x within the \(4\sigma \)-interval.

The style of Figs. 4, 5 and 6 is similar to Figs. 1, 2 and 3. In these figures, we also demonstrate accuracy of several approximations \({\tilde{b}}_x\) for binomial probabilities \(b_x\) by plotting the ratio \({\tilde{b}}_x/b_x\) where \({\tilde{b}}_x\) is an approximation for \(b_x\). Similarly to Figs. 1, 2 and 3, for the x-axis, \(j= 0,\pm 1, \pm 2, \ldots \) denote the points \(\lambda +js\), where \(s=\sqrt{Np(1-p)}\). In Figs. 4, 5 and 6, the smallest value at the x-axis corresponds to \(x=0 \) in (3) so that we show the values of the ratios \({\tilde{b}}_x/b_x\) for \(x=0,1, \ldots , \lambda +6 \sqrt{Np(1-p)}\).

In Figs. 4, 5 and 6, we do not use uncorrected normal and Poisson approximations as these approximations are poor. We use three approximations based on the expansion (6): the first-order Charlier approximation (red dotted line), second-order Charlier (green dash-dotted) and third-order Charlier (magenta long dashed). We also use the expansion (12) (brown dashed line), where we keep the first four terms in the expansions for Q and R.

The corrected Poisson approximations (6), based on the expansion with respect to the Charlier polynomials, significantly improve the Poisson approximation. The first-order Charlier approximation works well for x within the \(3\sigma \)-interval, but the second-order and especially third-order Charlier approximations are much more accurate. The new approximation (11) is basically exact at the lower tail of the binomial distribution and outperforms the Charlier approximations.

We study properties of two probability distributions defined on the infinite set \(\{0,1,2, \ldots \}\) and generalizing the ordinary discrete uniform and binomial distributions. Both extensions use the notion of grossone denoted by \(\textcircled {1}\). The uniform distribution assigns masses \(1/\textcircled {1}\) to all points in the set \( \{0,1, \ldots ,\textcircled {1}-1\}\). For this distribution, we study the problem of decomposing a r.v. \(\xi \) with this distribution as a sum \(\xi {\mathop {=}\limits ^\mathrm{d}} \xi _1 + \ldots + \xi _m\), where \(\xi _1 , \ldots , \xi _m\) are independent non-degenerate r.v. We establish that, under the validity of the grossone divisibility axiom, such decompositions exist, but all r.v. \(\xi _j\) in the decomposition \(\xi {\mathop {=}\limits ^\mathrm{d}} \xi _1 + \ldots + \xi _m\) must have different distributions and, as a corollary, that the discrete uniform distribution on the set \( \{0,1, \ldots ,\textcircled {1}-1\}\) is not infinitely divisible, where the natural extension of the notion of infinite divisibility (introduced in Sect. 2.1) is used.

Then, we study the accuracy of different approximations for the probability mass function of the binomial distribution Bin\((\textcircled {1},p)\) with \(p=c/\textcircled {1}^{\alpha }\) with \(1/2<\alpha \le 1\). We demonstrate that the normal and uncorrected Poisson approximations are rather poor and develop a new approximation which is demonstrated to be extremely accurate on the lower tail of Bin\((\textcircled {1},p)\). We compare the accuracy of the developed approximation with the corrected Poisson approximations constructed from the expansion with respect to the Charlier polynomials. The accuracy of approximations is assessed on the base of a numerical study. To derive approximations, we use asymptotic expansions formulated in the standard language, but the final results we translate into the language of grossone.