4
$\begingroup$

Is there some analogous of the Central limit theorem for discrete uniforms and discrete normal distributions?

To be more specific, let's say we have identical and independent random random variables $U_i$ uniform on a given integer interval $[0, k]\cap \mathbb{Z}$, for some $k \in \mathbb{N}$, $k \ge 2$.

Then, we can define the distribution $S_n := \sum_{i=1}^n U_i$.

Let $f_{c, s}(x) = \exp(-(x-c)/(2s^2))$, then the discrete Gaussian distribution centered on $c$ with variance $s^2$, which I will denote by $G_{c, s^2}$, assigns to each $x \in \mathbb{Z}$ the probability $$Pr[G_{c,s} = x] = \frac{f_{c, s}(x)}{\sum_{\forall y \in \mathbb{Z}}f_{c, s}(y)}.$$ That is, the "mass" of $x$ normalized by the "mass" of the whole integers.

I would like to know if there is some result that relates $S_n$ with the discrete normal distribution. For example, will $S_n$ converge to $G_{c, s^2}$ as $n$ increases?

I know that the mean of each $U$ is $\mu := k/2$ and the variance is $\sigma^2 := (k+1)^2 / 12$, so I made some tests using $G_{c, s^2}$ with $c = n\mu$ and $s = \sqrt{n}\sigma$, but it seems that $S_n$ does not converge. But it is hard to tell by the graphs...

$\endgroup$
3
  • $\begingroup$ The CLT asserts that the standardized version of $S_n$ converges to a standard Normal distribution. Since that's not the same as a discrete Gaussian, the answer to your question must be in the negative. Perhaps some further study of the CLT would help you, or maybe a detailed analysis of $S_n.$ $\endgroup$ – whuber Jul 17 '19 at 15:06
  • $\begingroup$ Yes, but if I divide by $n$, then I get rational values, and in this case there is no chance for $S_n$ to converge to the discrete Gaussian over the integers, since the supports will be diferent. Isn't there a version of CLT for non-standardized sums? Thank you! $\endgroup$ – Hilder Vitor Lima Pereira Jul 17 '19 at 16:03
  • $\begingroup$ I think you missed one of the main points about the CLT: it concerns the (cumulative) distribution function, not the probability mass function or probability density function. Because the CLT governs sums, the only possible different conclusion--whether the sums are standardized or not--occurs when the underlying distribution has infinite variance. That's not the case here. $\endgroup$ – whuber Jul 17 '19 at 16:50
2
$\begingroup$

This is a useful question with which to illustrate general principles for applying distributional approximations coming from the central limit theorems to random variables with a known restricted support. I will try to illustrate how you can deal with this specific case effectively, but also give some general principles for constructing good approximating distributions in these cases.


As a preliminary matter, we note that the sum statistic in this case has mean and variance:

$$\mu_n \equiv \mathbb{E}(S_n) = \frac{nk}{2} \quad \quad \quad \quad \quad \sigma_n^2 \equiv \mathbb{V}(S_n) = \frac{nk(k + 2)}{12}.$$

The classical central limit theorem for IID random variables (the Lindeberg–Lévy theorem) applies here, which applies to the standardised sum. That is, we have:

$$\lim_{n \rightarrow \infty} \mathbb{P} \bigg( \frac{S_n - \mu_n}{\sigma_n} \leqslant z \bigg) = \Phi(z),$$

where $\Phi$ denotes the CDF of the standard normal distribution. For large $n$ we often use this rule to say that $S_n$ approximately follows a normal distribution with mean $\mu_n$ and variance $\sigma_n^2$. However, the drawback of this is that the normal distribution has support over the entire real line, and this may not match the known support of the random variable under consideration (and in this case it doesn't).

A lesser-known alternative to using the normal approximation is that we can instead say that $S_n$ follows an alternative sequence of approximating distributions that itself converges towards the normal distribution (in an appropriately standardised sense). Convergence occurs in the following sense. Suppose there is a sequence of distributions $\{ \tilde{F}_n | n \in \mathbb{N} \}$ such that:

$$\lim_{n \rightarrow \infty} \tilde{F}_n(\mu_n + z \sigma_n) = \Phi(z) \quad \quad \quad \text{for all } z \in \mathbb{R}.$$

Then for all $z \in \mathbb{R}$ you have:

$$\lim_{n \rightarrow \infty} \Bigg| \mathbb{P}(S_n \leqslant \mu_n + z \sigma_n) - \tilde{F}_n(\mu_n + z \sigma_n) \Bigg| = 0.$$

In other words, the absolute difference between the true distribution and the approximation $\tilde{F}_n$ converges pointwise to zero.

Now, in addition to having access to the limiting result from the CLT, we also know that the true support of this random variable is $\text{supp} \ S_n = \{ 0,...,nk \}$. Thus, to construct a good distributional approximation, we want to use a sequence of distributions that has this support and also converges towards the normal distribution in the limit. There are a number of ways we can construct such a sequence of approximating distributions, and I will give some examples below. (The first is the same approximation you refer to in your question.) As you can see from these examples, there are various ways to construct a reasonable approximating distribution that is concentrated on the true support of the random variable of interest, but which converges to the normal distribution in the manner specified above.


Method 1A - Discrete normal approximation: A simple method to obtain a distributional approximation over the desired support is to use the approximating mass function:

$$\mathbb{P}(S_n = s) = \frac{\text{N}(s|\mu_n, \sigma_n^2)}{\sum_{r=0}^{nk} \text{N}(r|\mu_n, \sigma_n^2)} \quad \quad \quad \text{for } s = 0,...,nk.$$

This distributional approximation has the correct support and converges to the normal distribution in the limit (in an appropriately standardised sense).


Method 1B - Discrete normal approximation: A slight variation on the above method uses approximation via integration under the normal density over intervals using the values in the support as midpoints. To obtain a distributional approximation over the desired support we use the approximating mass function:

$$\mathbb{P}(S_n = s) = \frac{\int_{s-1/2}^{s+1/2} \text{N}(r|\mu_n, \sigma_n^2) \ dr}{\int_{-1/2}^{nk+1/2} \text{N}(r|\mu_n, \sigma_n^2) \ dr} \quad \quad \quad \text{for } s = 0,...,nk.$$

This distributional approximation has the correct support and converges to the normal distribution in the limit (in an appropriately standardised sense).


Method 2 - Beta-binomial approximation: The beta-binomial distribution is a three parameter distribution over a bounded discrete support that can be made to give a desired support range, mean and variance. We use $nk$ trials in the distribution and then we match up the moments by equating:

$$\mu_n = \frac{nk}{2} = \frac{nk \alpha}{\alpha+\beta} \quad \quad \quad \quad \quad \sigma_n^2 = \frac{nk(k+2)}{12} = \frac{nk \alpha \beta (\alpha+\beta+nk)}{(\alpha+\beta)^2 (\alpha+\beta+1)}$$

Solving these equations gives $\alpha = \beta = (3nk-k-2)/2(k-1)$, so we obtain a distributional approximation over the desired support by using the approximating mass function:

$$\mathbb{P}(S_n = s) = \text{BetaBin} \bigg( s \bigg| nk, \frac{3nk-k-2}{2(k-1)}, \frac{3nk-k-2}{2(k-1)} \bigg).$$

This distributional approximation has the correct support and converges to the normal distribution in the limit (in an appropriately standardised sense).


$\endgroup$
1
$\begingroup$

Partially answered in comments:

The CLT asserts that the standardized version of $S_n$ converges to a standard Normal distribution. Since that's not the same as a discrete Gaussian, the answer to your question must be in the negative. Perhaps some further study of the CLT would help you, or maybe a detailed analysis of $S_n$.

– whuber

( Yes, but if I divide by $n$, then I get rational values, and in this case there is no chance for $S_n$ to converge to the discrete Gaussian over the integers, since the supports will be diferent. Isn't there a version of CLT for non-standardized sums? – Hilder Vítor Lima Pereira )

I think you missed one of the main points about the CLT: it concerns the (cumulative) distribution function, not the probability mass function or probability density function. Because the CLT governs sums, the only possible different conclusion--whether the sums are standardized or not--occurs when the underlying distribution has infinite variance. That's not the case here.

– whuber

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.