# Convergence to a Uniform Distribution

$$\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}$$

Show that if $$P(X_n = i/n)=1/n$$ for every $$i = 1,...,n$$, then $$X_n$$ converges in distribution to a uniformly distributed random variable $$X$$.

Convergence in distribution is defined as

$$P(X_n \leq x) \rightarrow P(X \leq x)$$

and I have that a uniform distribution with parameters $$a$$ and $$b$$ implies that

$$P(X \leq x) = \frac{x-a}{b-a}$$

I cannot go any further however. I feel like I don't know anything about $$X_n$$ - I don't even know if it is continuous or discrete. What I can just say is that

$$P(X_n \leq x) = \sum_{i=1}^\floor{x} \frac{1}{n}$$

where $$\floor{x}$$ means rounding $$x$$ to the closest lower integer.

• (1) $X_n$ clearly is discrete: all its probability is concentrated on $n$ distinct values. (2) Please check your calculation of the probability: you seem not to have seen the occurrence of "$i$" in the original formula (or perhaps are ignoring its division by $n$). (3) I believe considerable insight can be obtained by graphing the CDFs of the first few $X_n$ as well as of the limiting distribution. – whuber Oct 22 '18 at 16:01
• Thanks. I think I have problems interpreting $X_n$. Can you help? For example, if I have $n=10$, and $x = 5.5$, then what will $P(X_n \leq x)$ be? – Daniel Oct 22 '18 at 16:12
• You might find it easier first to answer questions of the form "what is $\Pr(X_{10}=1/10),$ what is $\Pr(X_{10}=2/10),$ ..., and what is $\Pr(X_{10}=10/10)$?" With those answers in hand it should become apparent what $\Pr(X_{10}\lt 0)$ and $\Pr(X_{10}\gt 1)$ are; and you can then begin graphing the CDF. – whuber Oct 22 '18 at 16:29

I want to make two points. One is that although the concepts in this exercise are relatively sophisticated, a completely elementary simple solution is available. The other is that an appropriate visualization of the problem can lead us in natural steps through a rigorous proof. I will demonstrate that, by pointing out visually evident patterns in a set of graphs and then proving that those patterns are correct, using nothing more than the most basic properties of numbers and limits.

Because convergence in distribution is defined in terms of the (pointwise) convergence of the distribution functions, let's understand the latter.

Define $$F_n$$ to be the distribution of $$X_n.$$ That is,

$$F_n(x) = {\Pr}(X_n\le x).$$

Because $$X_n$$ can take on only a finite set of values--namely, $$1/n, 2/n, \ldots, (n-1)/n, n/n=1$$--it is necessarily discrete. This allows us to express its distribution $$F_n(x)$$ as the sum of probabilities of all numbers less than or equal to $$x.$$

Because all the possible values of all $$X_n$$ are greater than $$0$$ and less than or equal to $$1,$$ we immediately deduce that $$F_n(x)=0$$ when $$x\le 0$$ and $$F_n(x)=1$$ when $$x \ge 1.$$ What about intermediate values, $$x\in(0,1)$$? To find these, we may simply multiply $$x$$ by $$n.$$ This converts $$i/n$$ to $$i$$, whence

$$F_n(x) = \frac{1}{n}\text{ times the number of integers in }\{1,2,3,\ldots, n\}\text{ less than or equal to } nx.$$

The expression in words describes the floor function (aka greatest integer function), which associates with any real number $$x$$ the largest integer less than or equal to $$x.$$ This is more compactly written

$$F_n(x) = \lfloor xn \rfloor / n.\tag{1}$$

Let's plot a few of these functions, shown in the first three red graphs from left to right. The blue graph maps $$x$$ to $$x$$ for $$0\lt x\lt 1$$ and otherwise is $$0$$ for negative $$x$$ and equal to $$1$$ for $$x\ge 1.$$ It is shown for reference. Let $$F_\infty$$ denote the function of which it is the graph.

Another pattern emerges: the red curves never rise above the reference blue curve. That means $$F_n(x) \le x$$ for all $$x.$$ This is an immediate consequence of $$(1),$$ because the floor function is defined as the largest of a set of smaller values.

Visually, the red graphs grow closer to the blue graph as $$n$$ increases. It's tempting to leap to the conclusion that the blue graph must be their limit. Be careful, though, because they don't do this consistently at every point. For instance, for $$n=3$$ the red graph for $$F_n$$ touches the blue one at $$x=1/3$$ and $$x=2/3,$$ but when we increase $$n$$ to $$4,$$ its graph will no longer touch the blue one at those points.

The situation isn't all that complicated, though. You can see that the red graphs depart no further than $$1/n$$ from the blue graph at any point. Algebraically, in terms of the notation $$(1),$$ this claim is established by noting that the floor of any number $$x$$ is never more than $$1$$ away from $$x$$ itself, whence

$$|F_n(x) - F_\infty(x)| = |x - \lfloor nx \rfloor / n| = |nx - \lfloor nx \rfloor|/n \le \frac{1}{n}.$$

A basic fact of real numbers is that they are Archimedian: the sizes of the integers $$1,2,3,\ldots, n,\ldots$$ increase without bound. Therefore the sizes of the foregoing differences $$1/n$$ converge to $$0$$ as $$n$$ increases without bound. That is, by definition, what it means for

$$\lim_{n\to\infty} F_n(x) = F_\infty(x).$$

We have just proven that for $$0\lt x\lt 1,$$ $$F_n(x)$$ converges (uniformly!) to $$F_\infty(x).$$ For all other $$x$$, $$F_n(x) = F_\infty(x).$$ Consequently the convergence occurs everywhere.

Because $$F_\infty$$ is the uniform distribution function for the interval $$[0,1],$$ we are done.

By the way the information is given, namely that it tells us that the probability of $$X_n$$ taking a specific value is strictly positive, we learn that $$X_n$$ is certainly a discrete random variable, otherwise we would have $$P(X_n = i/n)=0$$ (and I guess we can assume that mixed distributions, part discrete part continuous, are not considered here).

Moreover, given $$P(X_n = i/n)=1/n$$, we learn that for every finite $$n$$, $$X_n$$ is a discrete uniform random variable with support $$\{1,2,...,n\}$$. What the exercise asks you to examine is whether, as $$n \to \infty$$, $$X_n$$ becomes at the limit a continuous uniform random variable. Does it?

The issue is trickier to examine than it may look at first, because the Uniform distribution, discrete or continuous, is defined in a bounded support (domain). If we let $$n\to \infty$$ the domain becomes infinite from the one side.

Certainly, for $$n$$ "very large" but finite, the distribution intuitively will be practically indistinguishable from the truly continuous uniform distribution. But to formalize "practically indistinguishable" without officially using $$n\to \infty$$, it appears you may need to use careful epsilon-delta limit arguments.