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.
 A: 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$:


*

*The numerators of the terms in $S_3$ never converge but, are bounded.

*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.

*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.
