A convergence problem

Question

I have a math/stat problem where I need to show the convergence of the average of a sequence of experiments to an interval. The sequence of experiments is not i.i.d., hence the standard law of large number does not apply. However, the framework satisfies some assumptions which might facilitate the convergence proof. I think the question can fit this advanced forum because it seems to go beyond standard applications of probability results.

Suppose we have a sequence of random experiments $(a_n)_{n\in \mathbb{N}}$. In particular, each $a_n$ is a random draw from a probability distribution $P_n: B\rightarrow [0,1]$, where $B$ is a finite set.

The probability distributions $P_n$ are potentially different across $n$. However, for each $b\in B$ and $n\in \mathbb{N}$, we know that $P_n(b)\in [\nu_\ell(b), \nu_u(b)]$, where the latter interval does not vary across $n$.

Let $x_N(b):=\frac{1}{N}\sum_{n=1}^N \mathbb{1}(a_n=b)$ for a finite $N\in \mathbb{N}$, where $\mathbb{1}(a_n=b)$ takes value 1 if $a_n=b$ and 0 otherwise.

I would like to show that, as $N\rightarrow \infty$, $x_N(b)$ falls in $[\nu_\ell(b), \nu_u(b)]$.

Could you help me to do that? If you think the statement is wrong, can you explain why?

Note: the draws may not be independent.

Answer 1

I assume that $(a_n)_{n \ge 1}$ are random variables taking values on a finite subset $B$, and that $\nu_l(b) \le P[a_n = b|a_1,\ldots,a_{n-1}] \le \nu_u(B)$ almost surely for every $n \ge 1$ and $b \in B$.

If yes, then for each $b \in B$, the formula $$M_n(b) := \sum_{k=1}^n\frac{1}{k}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ defines a square-integrable martingale. This martingale has orthogonal increments and is bounded in $L^2(P)$, since $$E\Big[\frac{1}{k^2}\big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)^2\Big] \le \frac{1}{4k^2}.$$ Hence it converges almost surely and in $L^2$.

We deduce that the averages
$$\frac{S_n(b)}{n} := \frac{1}{n}\sum_{k=1}^n \big(1_{[a_k=b]}-P[a_k = b|a_1,\ldots,a_{k-1}]\big)$$ converge almost surely to $0$, by Cesàro lemma since $$S_n(b) = \sum_{k=1}^n k(M_k(b)-M_{k-1}(b)),$$ $$S_n(b) = \sum_{k=1}^n kM_k(b) - \sum_{k=1}^n kM_{k-1}(b)),$$ $$S_n(b) = \sum_{k=0}^n kM_k(b) - 0 - \sum_{k=0}^{n-1} (k+1)M_k(b)),$$ $$S_n(b) = nM_n(b) - \sum_{k=0}^{n-1} M_k(b),$$ $$\frac{S_n(b)}{n} = M_n(b) - \frac{1}{n}\sum_{k=0}^{n-1}M_k(b).$$

As a result, 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|a_1,\ldots,a_{k-1}]$ have the same limit points as $n \to +\infty$, which belong to $[\nu_l(b),\nu_u(b)]$.

---

ADDENDUM (answers to the questions added by the OP)

Step 1. $|M_n(b)| \le \sum_{k=1}^n 1/k$. Therefore $M_n(b)$ is in $L^2(P)$.

Step 2. On $L^2(\Omega,\mathcal{A},P)$, the conditional expectation $E[\cdot|\mathcal{F_n}]$ coincides with the orthogonal projection on $L^2(\Omega,\mathcal{F_n},P)$. Hence $M_{n+1}(b)-M_n(b)$ is orthogonal to $L^2(\Omega,\mathcal{F_n},P)$, therefore to $M_0(b),\ldots,M_n(b)$.

Step 3. Do not confuse $E[M_n^2]$ finite for every $n$ and $E[M_n^2]$ bounded independently on $n$. The last statement follows from Pythagore equality (write $N_n$ as the sum of the pairwise orthogonal random variables $M_1-M_0,\ldots,M_n-M_{n-1}$) and from the convergence of the series $\sum_k 1/k^2$.

Step 4. The theorem applied here is the martingale convergence theorem, for martingales which are bounded in $L^2(P)$. Convergence in $L^2(P)$ can also be proved simply bu using Cauchy lemma and Pythagore theorem, thanks to the pairwise orthogonalality of the random variables $M_n-M_{n-1}$ and the convergence of the series $\sum_k 1/k^2$.

Step 5. No question on this step.

Step 6. Two sequences $(u_n)$ and $(v_n)$ of real numbers whose difference converges to $0$ have the same limit points: remind that the limit points are the limit of convergent subsequences. Because of the assumption $u_n-v_n \to 0$, for every increasing map $\phi$ from $\mathbb{N}$ to $\mathbb{N}$, and every real number $\ell$, $u_{\phi(n)} \to \ell$ if and only if $v_{\phi(n)} \to \ell$.