Suppose I have $n$ bernoulli (values zero or one), possibly dependent and nonidentically distributed, random variables (like the generalized binomial model), where a law of large numbers holds. Let $S_n = \sum_{i=1}^n X_i$ and

$$\lim_{n\rightarrow\infty}\frac{S_n-ES_n}{n}=0\text{ a.s.}$$

My question is, does this imply a function like $$F(n)=\frac{1}{n}\sum_{i=0}^{\lfloor ES_n \rfloor}(ES_n-i)\Pr(S_n=i)+\frac{1}{n}\sum_{i=\lfloor ES_n \rfloor+1}^n(i-ES_n)\Pr(S_n=i) $$ also converges to zero almost surely?

My work: $$nF(n) = \Pr(S_n\leq ES_n)(ES_n - E(S_n \mid S_n\leq ES_n)) + (1-\Pr(S_n \leq ES_n))(E(S_n\mid S_n >ES_n )-ES_n) $$

Replacing $\Pr(S_n\leq ES_n)$ with $p_n$,

$$nF(n) = 2p_n ES_n - ES_n - p_nE(S_n \mid S_n\leq ES_n) + (1-p_n)E(S_n \mid S_n> ES_n) $$

$$nF(n) = 2p_n ES_n - 2p_nE(S_n \mid S_n\leq ES_n).$$

Here, I'm getting stuck. I think I can use the tower property to show $EF(n)=0$, but I'd like to show $F(n)\rightarrow 0$ as $n\rightarrow \infty$ a.s.

  • $\begingroup$ Note that your function $F(n)$ is not random, so "convergence almost surely" for $F(n)$ should be replaced by "convergence." And yes, $F(n)$ converges to $0$. $\endgroup$
    – Michael
    Nov 13 '14 at 22:55

Yes. In fact, you just need to assume $(S_n-E[S_n])/n$ converges to $0$ in probability (almost sure convergence is not needed). It is helpful that, in your case, $0 \leq S_n \leq n$ for all $n$.

You are trying to show that $\lim_{n\rightarrow\infty} E\left[\left|\frac{S_n-E[S_n]}{n}\right|\right]=0$. Define $A_n = |S_n-E[S_n]|/n$. A hint is to fix $\epsilon>0$ and consider $E[A_n] = E[A_n|A_n\leq \epsilon]Pr[A_n\leq \epsilon] + E[A_n|A_n>\epsilon]Pr[A_n>\epsilon]$.

More generally, if $\{Z_n\}_{n=1}^{\infty}$ is a sequence of random variables that satisfies $Z_n\rightarrow 0$ in probability, and if the $Z_n$ values are deterministically bounded by some constant $C$ (so that $|Z_n|\leq C$ for all $n$), then $\lim_{n\rightarrow\infty}E[Z_n]=0$. This is a special case of the "Bounded Convergence Theorem" for random variables (see section 13.6 of Probability with Martingales by David Williams).

An even more general statement is the "bounded moment convergence theorem," which removes the requirement of deterministic bounds and only requires $E[|Z_n|^{1+\delta}] \leq C$ for all $n$ (for some real numbers $C\geq 0$, $\delta>0$). I needed such a statement once but couldn't find any ref, so I gave a quick proof in Appendix A here: http://ee.usc.edu/stochastic-nets/docs/low-power-computing-chapter.pdf

  • $\begingroup$ Thanks! Let me make sure I understand though. In setting up $E[A_n]$, I can show $E[A_n \mid A_n\leq \epsilon]\Pr(A_n\leq \epsilon)+ E[A_n \mid A_n >\epsilon]\Pr(A_n > \epsilon) \leq \epsilon + 1\Pr(A_n > \epsilon) \rightarrow \epsilon$ for a fixed epsilon, which being arbitrary, tells me the expectation is zero? I might also want to weight one kind of "error", adding a constant in front of one of the sums in $F(n)$, but I'm guessing that should be easy enough to deal with. $\endgroup$
    – Pburg
    Nov 14 '14 at 16:34
  • $\begingroup$ Yes, that is a great way to finish the details to show the limiting expectation is $0$. I think this is essentially the same proof as given in the David Williams book. $\endgroup$
    – Michael
    Nov 14 '14 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.