Bound the expectation of an average

Question

Let $(a_n)_{n \geq 1}$ be random variables taking values on a finite subset $B$. Assume that $\nu_l(b) \le P[a_n = b\mid a_1,\ldots,a_{n-1}] \le \nu_u(b)$ almost surely for every $n \ge 1$ and $b \in B$. Then, it can be shown that $$ \frac{1}{n}\sum_{k=1}^n 1_{[a_k = b]}-\frac{1}{n}\sum_{k=1}^n P[a_k = b\mid a_1,\ldots,a_{k-1}]\overset{\text{a.s.}}{\to} 0 \text{ as $n\to +\infty$,} $$ i.e., the averages $\frac{1}{n}\sum_{k=1}^n 1_{[a_k = b]}$ and $\frac{1}{n}\sum_{k=1}^n P[a_k = b\mid a_1,\ldots,a_{k-1}]$ have the same limit points as $n \to +\infty$, which belong to $[\nu_l(b),\nu_u(b)]$. For a proof, see the answer to my previous question here.

I would like to show that $$ E\Big(\frac{1}{n}\sum_{k=1}^n 1_{[a_k = b]} \Big)\leq \frac{T_b}{\sqrt{n}}. $$ for some $T_b$. Could you help me do that?

Answer 1

Of course, this is not true. E.g., suppose that the $a_n$'s are independent random variables each uniformly distributed on the finite set $B$, of cardinality $|B|\ge1$. (With $\nu_l(b)$ and $\nu_u(b)$ completely unspecified, the condition $\nu_l(b) \le P[(a_n = b|a_1,\ldots,a_{n-1}) \le \nu_u(b)$ is not a restriction at all. In our present case, we can take $\nu_l(b)=\nu_u(b)=P(a_n=n)=1/|B|$ for all $b\in B$.)

Then for any real $T_b$ and all $n>T_b^2|B|^2$ $$E\Big(\frac1n\,\sum_{k=1}^n 1(a_k = b) \Big) =\frac1n\,\sum_{k=1}^n E1(a_k = b)=\frac1{|B|} \not\le \frac{T_b}{\sqrt{n}}.$$

---

Added in response to a comment by the OP: In general, $$E\Big(\frac1n\,\sum_{k=1}^n 1(a_k = b) \Big) =\frac1n\,\sum_{k=1}^n E1(a_k = b) \\ =\frac1n\,\sum_{k=1}^n P(a_k = b) =\frac1n\,\sum_{k=1}^n EP(a_k = b|a_1,\ldots,a_{n-1}) \\ \le\frac1n\,\sum_{k=1}^n E\nu_u(b) =\nu_u(b).$$ Similarly, $$E\Big(\frac1n\,\sum_{k=1}^n 1(a_k = b) \Big) \ge\nu_l(b).$$