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](https://mathoverflow.net/questions/435609/a-convergence-problem).


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?



Bound the expectation of an average
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).$$


