Convergence of a sequence of random variables that are independent but not identically distributed

Question

Consider a sequence of independent random variables $\{X_k\}_{k=1}^\infty$. Consider $M$ probability density functions $f_1(x),\dots,f_M(x)$ defined on $\mathbb{R}$ which are distinct but have the same expected value, i.e., \begin{equation} \mathbb{E}_{f_m} [X] = \mu \text{ for all } m \in \{1,\dots,M\}. \end{equation} Consider a sequence of indices $S=\{S_k\}_{k=1}^\infty$ such that $S_k \in \{1,\dots,M\}$. We have that the distribution of the process is given as follows:

\begin{equation} X_k \sim f_{S_k}(\cdot). \end{equation}

I am trying to establish whether

\begin{equation} \lim_{k \rightarrow \infty} \sup_{S} \mathbb{P}_S \left( \frac{\sum_{i=1}^k X_{i}}{k} > \mu + \epsilon \right) \rightarrow 0 \end{equation} holds, where $\mathbb{P}_S$ denotes the probability measure when the distribution of $\{X_k\}_{k=1}^\infty$ is specified by $\{S_k\}_{k=1}^\infty$ and the supremum is taken over all possible sequences $\{S_k\}_{k=1}^\infty$. Is the statement true or do we need more assumptions that that the means are equal? I really appreciate your assistance.

Answer 1

Ben’s answer gives a nice result when variances are finite. Here is a proof for a more general case that allows for infinite variances and non-i.i.d. variables. It also allows the choice of $S$ to depend on the $\{X_i\}$ variables.

---

Fix $\mu \in \mathbb{R}$. Fix $M$ as a positive integer. Let $\{X_i[m]\}_{i=1}^{\infty}$ be a collection of real-valued random processes for $m \in \{1, …, M\}$ such that $$ P\left[\lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n X_i[m] = \mu\right] = 1 \quad \forall m \in \{1, …, M\}$$ The processes are not required to have identical distributions or to have independence properties.

Fix $\epsilon>0, \delta>0$. For positive integers $k$ and $c$, define the following events: \begin{align} A_k &= \cap_{m=1}^M \cap_{n=k}^{\infty} \left\{\frac{1}{n}\sum_{i=1}^n (X_i[m]-\mu) \leq \frac{\epsilon}{2}\right\}\\ B_k(c) &= \cap_{m=1}^M \cap_{n=1}^k \{X_i[m]\leq c\} \end{align}

The following two claims hold (I omit the proof):

• Claim 1: There is a positive integer $z$ such that $P[A_{z}]\geq 1-\delta/2$.

• Claim 2: There is an integer $d \geq \mu$ such that $P[B_{z}(d)] \geq 1-\delta/2$.

From Claims 1 and 2 and the union bound we find: $$P[A_z^c \cup B_z(d)^c] \leq \delta$$ Now fix $n$ as a positive integer and let $S_n=(S_n[1], S_n[2], … ,S_n[M])$ be a random vector of nonnegative integers that sum to $n$. This represents the number of times we choose type $m$ variables in the first $n$ steps. The vector $S_n$ is allowed to depend on the processes $\{X_i[m]\}_{i=1}^{\infty}$. Define $R_n(S_n)$ as the average of interest: $$ \boxed{R_n(S_n)=\frac{1}{n}\sum_{m=1}^M\sum_{i=1}^{S_n[m]}(X_i[m]-\mu)}$$

If the event $A_z\cap B_z(d)$ holds (which happens with probability at least $1-\delta$) then for each $m \in \{1, …, M\}$ we observe:

• If $S_n[m]<z$ then, because event $B_z(d)$ holds, we have $$\sum_{i=1}^{S_n[m]} (X_i[m]-\mu) \leq (d-\mu)z$$

• if $S_n[m]\geq z$ then, because $A_z$ holds, we have $$\sum_{i=1}^{S_n[m]} (X_i[m]-\mu) \leq \frac{\epsilon S_n[m]}{2}$$

Thus, regardless of the value of $S_n[m]$ we have: $$ \sum_{i=1}^{S_n[m]} (X_i[m]-\mu) \leq (d-\mu)z + \frac{\epsilon S_n[m]}{2}$$ Therefore, if the event $A_z\cap B_z(d)$ holds, then
\begin{align} R_n(S_n)&= \frac{1}{n}\sum_{m=1}^M \sum_{i=1}^{S_n[m]}(X_i[m]-\mu)\\ &\leq \frac{1}{n}\sum_{m=1}^M\left[(d-\mu)z + \frac{\epsilon S_n[m]}{2}\right]\\ &= \frac{M(d-\mu)z}{n} + \frac{\epsilon}{2n}\sum_{m=1}^MS_n[m]\\ &= \frac{M(d-\mu)z}{n} + \frac{\epsilon}{2} \end{align} where we have used the fact that $\sum_{m=1}^MS_n[m] =n$. Then for every positive integer $n$ that is large enough to ensure $M(d-\mu)z/n \leq \epsilon/2$ we have: $$ R_n(S_n)\leq \epsilon $$ In particular, if $n \geq 2M(d-\mu)z/\epsilon$ then $$ A_z \cap B_z(d) \subseteq \{R_n(S_n)\leq \epsilon\} $$ Thus $$1-\delta \leq P[A_z \cap B_z(d)]\leq P[R_n(S_n)\leq \epsilon]$$ This holds for all allocation vectors $S_n$, in particular: $$ \sup_{S_n} P[R_n(S_n)\leq \epsilon] \geq 1-\delta \quad \forall n \geq 2M(d-\mu)z/\epsilon$$ Taking a limit gives $$ \liminf_{n\rightarrow\infty} \sup_{S_n}P[R_n(S_n)\leq \epsilon] \geq 1-\delta$$ This holds for all $\delta>0$ and so $$\boxed{\lim_{n\rightarrow\infty} \sup_{S_n}P[R_n(S_n)\leq \epsilon] =1} \quad \Box$$

Answer 2

A simple sufficient condition for this result is for the variances of each of your $M$ distributions to be finite. If this holds then you can apply Chebychev's inequality to obtain the required limit. To see this, let $\sigma_1^2,...,\sigma_M^2$ denote the variances of the distributions (some or all of which may be infinite), and define the corresponding maximum $\bar{\sigma}^2 \equiv \max (\sigma_1^2,...,\sigma_M^2)$ (which may also be infinite). Then using standard moment calculations for the sample mean we can easily establish that:

$$\mathbb{E}(\bar{X}_k) = \mu \quad \quad \quad \quad \quad \mathbb{V}(\bar{X}_k) \leqslant \frac{\bar{\sigma}^2}{k}.$$

For any sequence $S$, we can apply Chebychev's inequality (on the third line of working) to obtain:

$$\begin{equation} \begin{aligned} \mathbb{P}_S (\bar{X}_k > \mu + \epsilon ) &= \mathbb{P}_S (\bar{X}_k - \mu > \epsilon ) \\[12pt] &\leqslant \mathbb{P}_S (|\bar{X}_k - \mu| > \epsilon ) \\[10pt] &\leqslant \frac{\mathbb{V}(\bar{X}_k)}{\epsilon^2} \\[6pt] &\leqslant \frac{1}{\epsilon^2} \cdot \frac{\bar{\sigma}^2}{k}. \\[6pt] \end{aligned} \end{equation}$$

Since this holds for all sequences $S$, we therefore have:

$$\sup_S \mathbb{P}_S (\bar{X}_k > \mu + \epsilon ) \leqslant \frac{1}{\epsilon^2} \cdot \frac{\bar{\sigma}^2}{k}.$$

If $\bar{\sigma}^2 < \infty$ (i.e., if the variances of each of the distributions is finite) then we have:

$$\lim_{k \rightarrow \infty} \sup_S \mathbb{P}_S (\bar{X}_k > \mu + \epsilon ) \leqslant \lim_{k \rightarrow \infty} \frac{1}{\epsilon^2} \cdot \frac{\bar{\sigma}^2}{k} = 0.$$