2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$)? $\endgroup$ – whuber Sep 11 '14 at 15:34
1
$\begingroup$

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, \begin{equation} \left(a_1, a_2, \dots, a_n\right), \end{equation} 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 \begin{equation} 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), \end{equation} 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 \begin{equation} S_2 = \left(\frac{\textrm{nint}(1p^*)}{1}, \frac{\textrm{nint}(2p^*)}{2}, \dots, \frac{\textrm{nint}(np^*)}{n}\right), \end{equation} 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 \begin{equation} S_4 = \left(\frac{|\textrm{nint}(1p^*) - 1p^*|}{1}, \frac{|\textrm{nint}(2p^*) - 2p^*|}{2}, \dots, \frac{|\textrm{nint}(np^*) - np^*|}{n}\right), \end{equation} 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. \begin{equation} |\textrm{nint}(ip^*) - ip^*| \leq \frac{0.5}{i}, \forall i. \end{equation}

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Sep 19 '14 at 14:45
  • $\begingroup$ 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$? $\endgroup$ – Richy Sep 23 '14 at 8:32
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Sep 23 '14 at 16:32

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.