# Maximum convergence rate of empirical probability

Given a sequence of events $$(a_1, a_2, \dots, a_n),$$ then the sequence of empirical probabilities of some event $\alpha$ is $$\left(p_1 = \frac{\sum_{i = 1}^1 [a_i = \alpha]}{1}, p_2 = \frac{\sum_{i = 1}^2 [a_i = \alpha]}{2}, \dots, p_n = \frac{\sum_{i = 1}^n [a_i = \alpha]}{n}\right).$$ Assume that this sequence converges to some value, $p^*$. If you can choose the sequence of events (i.e. which events are equal to $\alpha$ and which are not), then what is the maximum convergence rate of this sequence to $p^*$?

The answer will depend on the value of $p^*$. If $p^* = 0$, then the sequence can converge immediately by never choosing event $\alpha$. Similarly, if $p^* = 1$, then the sequence can converge immediately by always choosing event $\alpha$. However, if $0 < p^* < 1$, then the sequence cannot converge immediately.

So my question is, if you can choose the sequence of events $(a_i)_{i = 1}^n$ and, you want the sequence of empirical probabilities $(p_i)_{i = 1}^n$ to converge to some value $0 < p^* < 1$ as quickly as possible, then what is the maximum convergence rate?

I think a simple process to achieve the maximum convergence rate is if $p_{i - 1} < p^*$ then choose event $\alpha$, otherwise choose some other event $\beta \neq \alpha$. I also think the maximum convergence rate is $1 / i$ but I'm not sure how to prove this.

• Hint: When you plot the points $(n, p_n n)$, which lie on the integer lattice in the plane, you obtain a discrete approximation to the line $(n, pn)$. The maximum convergence rate is obtained by choosing lattice points that come as close as possible to the line. Just how close can they come (as a function of $n$)? – whuber Sep 11 '14 at 15:34

So I have an argument about why the maximum convergence rate is $1 / i$, where $i$ is the iteration number, but I'm not sure if my reasoning is correct and, even if it is, if there isn't a better argument or, a proof.

Given a sequence of events, $$\left(a_1, a_2, \dots, a_n\right),$$ where $a_i \in A$ for $1 \leq i \leq n$ and $A$ is the set of all possible events. The sequence of empirical probabilities for some event $\alpha \in A$ is $$S_1 = \left(\frac{\sum_{i = 1}^1 [a_i = \alpha]}{1}, \frac{\sum_{i = 1}^2 [a_i = \alpha]}{2}, \dots, \frac{\sum_{i = 1}^n [a_i = \alpha]}{n}\right),$$ where $[\phi]$ is the Iverson bracket such that $[\phi] = 1$ if the predicate $\phi$ is true, otherwise $[\phi] = 0$.

We want $S_1$ to converge to some probability, $0 \leq p^* \leq 1$, as quickly as possible. To do this, we make each term in $S_1$ as close to $p^*$ as possible giving $$S_2 = \left(\frac{\textrm{nint}(1p^*)}{1}, \frac{\textrm{nint}(2p^*)}{2}, \dots, \frac{\textrm{nint}(np^*)}{n}\right),$$ where $\textrm{nint}$ is the nearest integer (or $\textrm{round}$) function such that $\textrm{nint}(x) = \min(x - \textrm{floor}(x), \textrm{ceil}(x) - x)$.

The difference between each term in $S_2$ and $p^*$ is \begin{align} S_3 &= \left(\frac{\textrm{nint}(1p^*)}{1} - p^*, \frac{\textrm{nint}(2p^*)}{2} - p^*, \dots, \frac{\textrm{nint}(np^*)}{n} - p^*\right)\\ &= \left(\frac{\textrm{nint}(1p^*) - 1p^*}{1}, \frac{\textrm{nint}(2p^*) - 2p^*}{2}, \dots, \frac{\textrm{nint}(np^*) - np^*}{n}\right) \textrm{ and}, \end{align} the absolute value of each term in $S_3$ gives $$S_4 = \left(\frac{|\textrm{nint}(1p^*) - 1p^*|}{1}, \frac{|\textrm{nint}(2p^*) - 2p^*|}{2}, \dots, \frac{|\textrm{nint}(np^*) - np^*|}{n}\right),$$ If $S_3$ converges to $0$, then $S_4$ must converge to $0$ and, $S_2$ must converge to $p^*$. Additionally, the convergence rate of $S_3$ to $0$ will equal both the convergence rate of $S_4$ to $0$ and, the convergence rate of $S_2$ to $p^*$.

If $p^* = 0$, then \begin{align*} S_2 = \left(0, 0, \dots, 0\right),\\ S_3 = \left(0, 0, \dots, 0\right),\\ S_4 = \left(0, 0, \dots, 0\right), \end{align*} where $S_2$, $S_3$, and $S_4$ converge immediately (or their convergence rates are infinity).

If $p^* = 1$, then \begin{align*} S_2 = \left(1, 1, \dots, 1\right),\\ S_3 = \left(0, 0, \dots, 0\right),\\ S_4 = \left(0, 0, \dots, 0\right), \end{align*} where $S_2$, $S_3$, and $S_4$ converge immediately (or their convergence rates are infinity).

If $0 < p^* < 1$, $i \in \mathbb{N}$, and $i \geq 1$, then for $S_3$ \begin{align} &\min_{i,p^*}(\textrm{nint}(ip^*) - ip^*) = -0.5,\\ &\max_{i,p^*}(\textrm{nint}(ip^*) - ip^*) = 0.5,\\ &(\textrm{nint}(ip^*) - ip^*) \in [-0.5, 0.5]. \end{align} It follows that \begin{align} &\min_{i,p^*}\left(\frac{\textrm{nint}(ip^*) - ip^*}{i}\right) = \frac{-0.5}{i},\\ &\max_{i,p^*}\left(\frac{\textrm{nint}(ip^*) - ip^*}{i}\right) = \frac{0.5}{i},\\ &\left(\frac{\textrm{nint}(ip^*) - ip^*}{i}\right) \in \left[\frac{-0.5}{i}, \frac{0.5}{i}\right]. \end{align} For $S_4$, \begin{align} &\min_{i,p^*}(|\textrm{nint}(ip^*) - ip^*|) = 0.0,\\ &\max_{i,p^*}(|\textrm{nint}(ip^*) - ip^*|) = 0.5,\\ &(|\textrm{nint}(ip^*) - ip^*|) \in [0.0, 0.5]. \end{align} It follows that \begin{align} &\min_{i,p^*}\left(\frac{|\textrm{nint}(ip^*) - ip^*|}{i}\right) = \frac{0.0}{i},\\ &\max_{i,p^*}\left(\frac{|\textrm{nint}(ip^*) - ip^*|}{i}\right) = \frac{0.5}{i},\\ &\left(\frac{|\textrm{nint}(ip^*) - ip^*|}{i}\right) \in \left[\frac{0.0}{i}, \frac{0.5}{i}\right]. \end{align}

It is important to note that the lower and upper bounds of the terms in $S_3$ and $S_4$ are for any value of $p^*$ and, any value of $i$ within their constraints. If $p^*$ is set to a particular value, then these bounds will change. For example, if $p^* = 1 / 3$, then $(\textrm{nint}(ip^*) - ip^*) \in [-1/3, 1/3]$ and $(|\textrm{nint}(ip^*) - ip^*|) \in [0, 1/3]$.

Consider the following facts about the terms in $S_3$:

1. The numerators of the terms in $S_3$ never converge but, are bounded.
2. The numerators of the terms in $S_3$ oscillate between their lower and upper bounds as the number of iterations increases. This means that given any iteration $i_1$, there exist iterations $i_2,i_3 > i_1$, where at $i_2$ the numerator of the term is equal to its lower bound and, at $i_3$ the numerator of the term is equal to its upper bound.
3. The minimum of the convergence rates of the lower and upper bounds of the terms in $S_3$ to $0$ is like $1 / i$.

Given points 1 and 2, then the convergence rate of the terms in $S_3$ to $0$ must be equal to the minimum of the convergence rates of its lower and upper bounds, which given point 3 is like $1 / i$. This means that $S_4$ must also be converging to $0$ like $1 / i$ and, that $S_2$ must also be converging to $p^*$ like $1 / i$. In fact, $S_4$ converges with order $1$ when $c = 0.5$ i.e. $$|\textrm{nint}(ip^*) - ip^*| \leq \frac{0.5}{i}, \forall i.$$

I would appreciate any feedback, especially if someone could show me a better argument or, even a proof.

• Because lattice points in the plane have unit spacing, the hint I gave to the question immediately shows you can achieve $1/(2i)$ accuracy everywhere. That's a rigorous proof. Drawing a picture might help you understand it and connect it to the calculations presented in your answer here. – whuber Sep 19 '14 at 14:45
• Thanks Whuber, I didn't really understand your original comment and was hoping for more of an explanation. I assume that my argument is effectively saying the same thing but in a more roundabout way. Am I right in thinking this is like the maximum convergence rate though? Because you cannot have the sequence I labelled $S_3$ convergence to zero unless its bounds converge to zero, so you have to wait for them to converge to zero, which they do so like $1/2i$? – Richy Sep 23 '14 at 8:32
• It is not quite the maximal convergence rate for all $p^{*}$--but you can use the same geometrical technique to figure that out. For instance, when $p^{*}=1/3$, then all lattice points can be made to lie within $1/3$ of the line $y=p^{*}x$, but infinitely many of them will be $1/3$ from the line, so the rate is $1/(3i)$. It can be achieved through the sequence $0,1,0,0,1,0,0,1,0,0,1,\ldots$ for which $i(p^{*}-p_i)$ proceeds as $-1/3,1/3,0,-1/3,1/3,0,-1/3,\ldots$. Regardless of the value of $p^{*}$, a convergence rate of at least $1/(2i)$ is guaranteed. – whuber Sep 23 '14 at 16:32