<s>[INST] Running average of an $O_p(1)$ sequence Suppose that $\{X_n\}$ is an $O_p(1)$ sequence of random variables (see https://en.wikipedia.org/wiki/Big_O_in_probability_notation). Is it true that
$$
\bar{X}_n=\frac{1}{n}\sum_{i=1}^n X_i=O_p(1)?
$$
I was thinking about using the following bound
$$
P(|\bar{X}_n|>M)\le \sum_{i=1}^n P(|X_i|>M).
$$
However, it is not tight enough. Is there a better bound or a simple counterexample?
 [/INST] The conjecture is not true.  The counterexample is as follows (modified from the classical example of $X_n \to_P 0$ but $X_n \not\to 0$ with probability $1$):
Take the probability space to be $((0, 1], \mathscr{B}((0, 1]), \lambda)$, where $\lambda$ is the Lebesgue measure on $(0, 1]$.  Let
\begin{align}
& X_1(\omega) = 1, \\
& X_2(\omega) = 2^2 I_{(0, 1/2]}(\omega), X_3(\omega) = 3^2I_{(1/2, 1]}(\omega), \\
& X_4(\omega) = 4^2I_{(0, 1/4]}(\omega), X_5(\omega) = 5^2I_{(1/4, 1/2]}(\omega),
X_6(\omega) = 6^2I_{(1/2, 3/4]}(\omega), X_7(\omega) = 7^2I_{(3/4, 1]}(\omega), \\ 
& \cdots\cdots
\end{align}
In general, for $n \geq 2$, write $n$ as $n = 2^k + m$ with $k \geq 1$ and $0 \leq m < 2^k$, then define
\begin{align}
X_n(\omega) = n^2I_{(m2^{-k}, (m + 1)2^{-k}]}(\omega).
\end{align}
Or in terms of $n$ solely, this is
\begin{align}
X_n(\omega) = n^2I_{\left((n - 2^{\lfloor \log_2n \rfloor}) 2^{-\lfloor \log_2n \rfloor}, (n - 2^{\lfloor \log_2n \rfloor} + 1) 2^{-\lfloor \log_2n \rfloor}\right]}(\omega).
\end{align}
It is a standard exercise to show $X_n \to_P 0$ as $n \to \infty$, whence $X_n = O_P(1)$.
For every positive integer $N$ and $\omega \in (m2^{-N}, (m + 1)2^{-N}]$, where $0 \leq m < 2^{N}$, let $m_k$ be such that $\omega \in (m_k2^{-k}, (m_k + 1)2^{-k}]$ for $1 \leq k \leq N - 1$.  By construction, we have
\begin{align}
     & X_1(\omega) + X_2(\omega) + \cdots + X_{2^{N + 1}}(\omega) \\
\geq & X_1(\omega) + X_2(\omega) + \cdots + X_{2^N + m - 1}(\omega) + X_{2^N + m}(\omega) \\
\geq & X_1(\omega) + X_{2 + m_1}(\omega) + \cdots + X_{2^{N - 1} + m_{N - 1}}(\omega) + X_{2^N + m}(\omega) \\
= & 1 + (2 + m_1)^2 + \cdots + (2^{N - 1} + m_{N - 1})^2 + (2^N + m)^2 \\
\geq & \sum_{k = 0}^N (2^k)^2 = \frac{1}{3}(4^{N + 1} - 1).
\end{align}
Therefore, for every $\omega \in (0, 1]$, it follows that
\begin{align}
 & \bar{X}_{2^{N + 1}}(\omega) = \frac{1}{2^{N + 1}}(X_1(\omega) + \cdots + 
X_{2^{N + 1}}(\omega)) \geq \frac{4^{N + 1} - 1}{3 \times 2^{N + 1}} = \frac{2^{N + 1}}{3} - \frac{1}{3 \times 2^{N + 1}} > N
\end{align}
for $N \geq 2$. This shows that for all $N \geq 2$, there exists $n > N$, such that for every $\omega \in (0, 1]$, it holds that $\bar{X}_n(\omega) > N$. In other words, $P[|\bar{X}_n| > N] = 1$.  Therefore, $\bar{X}_n \neq O_P(1)$.
</s>