Convergence of a sequence of random variables that are independent but not identically distributed 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.
 A: 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.$$
A: 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$$
