Let $A_1,A_2,\cdots$ and $B_1,B_2,\cdots$ be two independent sequences of i.i.d random variables according to probability density function $p(x)$, with $\mathbb{E}[A_1]=\mathbb{E}[B_1]<\infty$ and $Var[A_1]=Var[B_1]<\infty$. For a fixed constant $c>0$, find the constant $k>0$ such that

$$\lim\limits_{n \to \infty}\mathbb{P}\left(\frac{1}{n}\sum\limits_{i=1}^{i=n}A_i\geq \left(1-\frac{c}{\sqrt{n}}\right)\left(1-\frac{k}{\sqrt{n}}\right)\frac{1}{n+k\sqrt{n}}\sum\limits_{i=1}^{i=n+k\sqrt{n}}B_i \right)=1 $$

My approach: $\frac{1}{n}\sum\limits_{i=1}^{i=n}A_i$ is a random variable and weak law of large numbers yields $$\frac{1}{n}\sum\limits_{i=1}^{i=n}A_i\xrightarrow{p}\mathbb{E}(A_i)\,\,\,\,\,\,\,\,\,\,\,(1)$$

Similarly, $$ \frac{1}{n+k\sqrt{n}}\sum\limits_{i=1}^{i=n+k\sqrt{n}}B_i \xrightarrow{p}\mathbb{E}(B_i)=\mathbb{E}(A_i)\,\,\,\,\,\,\,\,\,\,\,(2)$$

[I am not sure about this step:] Therefore, for all $k$

$$\left(1-\frac{c}{\sqrt{n}}\right)\left(1-\frac{k}{\sqrt{n}}\right)\frac{1}{n+k\sqrt{n}}\sum\limits_{i=1}^{i=n+k\sqrt{n}}B_i \xrightarrow{p}\mathbb{E}(B_i)=\mathbb{E}(A_i)\,\,\,\,\,\,\,\,\,\,\,(3)$$

Now, by (1) and (3)

$$\left[\frac{1}{n}\sum\limits_{i=1}^{i=n}A_i-\left(1-\frac{c}{\sqrt{n}}\right)\left(1-\frac{k}{\sqrt{n}}\right)\frac{1}{n+k\sqrt{n}}\sum\limits_{i=1}^{i=n+k\sqrt{n}}B_i \right]\xrightarrow{p}0$$

Thus, for all $k$

$$\lim\limits_{n \to \infty}\mathbb{P}\left(\frac{1}{n}\sum\limits_{i=1}^{i=n}A_i\geq \left(1-\frac{c}{\sqrt{n}}\right)\left(1-\frac{k}{\sqrt{n}}\right)\frac{1}{n+k\sqrt{n}}\sum\limits_{i=1}^{i=n+k\sqrt{n}}B_i \right)=1 $$

Is my approach correct? Is there a simpler precise method to prove? In the problem statement, if we had a function $f(n,c,k)$ instead of $\left(1-\frac{c}{\sqrt{n}}\right)\left(1-\frac{k}{\sqrt{n}}\right)$, such that $\lim\limits_{n\to\infty}f(n,c,k)=1$, could we use the same approach?

  • $\begingroup$ I observe that your question has random variables $\{B_i\}$ that are never used. Is there a typo in the question? $\endgroup$ – Michael Dec 21 '16 at 18:29
  • $\begingroup$ @Michael Thanks for informing me that. I fixed the typo $\endgroup$ – Susan_Math123 Dec 21 '16 at 18:31
  • 1
    $\begingroup$ Your argument seems similar to the following false claim: “If $X_i \rightarrow 1$ and $Y_i \rightarrow 1$ then $P[X_i \geq Y_i] \rightarrow 1$.” This is not true, for example, if $Y_i=1$ and $X_i=1-e^{-i}$ for all $i$. $\endgroup$ – Michael Dec 21 '16 at 18:37
  • $\begingroup$ There are cases when no such $k$ exists. For example if $Var(A)=0$ and $E[A]=-1$. Also, no such $k$ exists if $Var(A)>0$ and $E[A]=0$. You are likely supposed to assume $E[A]>0$ and then use the central limit theorem. $\endgroup$ – Michael Dec 21 '16 at 18:44
  • $\begingroup$ Actually, even if $Var(A)>0$ and $E[A]>0$, there is still no such $k$. Where did this problem come from? if the factors were $(1-c/n^{.5-\epsilon})$ then it would work. $\endgroup$ – Michael Dec 21 '16 at 19:02

Assume $\{A_i\}$ and $\{B_i\}$ are independent i.i.d. processes with $Var(A_1)=\sigma^2$. If $0<\sigma^2 < \infty$, then there is no such $k$.

Proof: Define $m=E[A_1]$. Fix $c>0$ and $k>0$ as arbitrary constants. Define the following events:

\begin{align} \mathcal{C}_n &= \left\{\frac{1}{n}\sum_{i=1}^n A_i \geq (1-\frac{c}{\sqrt{n}})(1-\frac{k}{\sqrt{n}})\frac{1}{\lceil n + k\sqrt{n}\rceil}\sum_{i=1}^{\lceil n+k\sqrt{n}\rceil}B_i\right\} \\ \mathcal{D}_n &= \left\{\frac{1}{\lceil n+k\sqrt{n}\rceil}\sum_{i=1}^{\lceil n + k\sqrt{n}\rceil}B_i \geq m\right\} \end{align} Notice that $P[\mathcal{D}_n]\rightarrow 1/2$ by the central limit theorem (CLT). Also, $\mathcal{D}_n$ is independent of the $\{A_i\}$ process. Hence, for all $n$ large enough to ensure $1>(1-\frac{c}{\sqrt{n}})(1-\frac{k}{\sqrt{n}})> 0$, we have: \begin{align} P[\mathcal{C}_n|\mathcal{D}_n] &\leq P\left[\frac{1}{n}\sum_{i=1}^nA_i \geq (1-\frac{c}{\sqrt{n}})(1-\frac{k}{\sqrt{n}})m|\mathcal{D}_n\right]\\ &=P\left[\frac{1}{n}\sum_{i=1}^nA_i \geq (1-\frac{c}{\sqrt{n}})(1-\frac{k}{\sqrt{n}})m \right] \\ &=P\left[\frac{1}{\sqrt{n}}\sum_{i=1}^n(A_i-m) \geq - m(c+k) + \frac{ckm}{\sqrt{n}} \right] \rightarrow q \end{align} where we define $q=P[G \geq -m(c+k)]$ for $G$ a Gaussian with mean 0 and variance $\sigma^2$. Note that $0<q<1$. Then:

\begin{align} P[\mathcal{C}_n] &= P[\mathcal{C}_n|\mathcal{D}_n]P[\mathcal{D}_n] + P[\mathcal{C}_n|\mathcal{D}_n^c]P[\mathcal{D}_n^c] \\ &\leq P[\mathcal{C}_n|\mathcal{D}_n]P[\mathcal{D}_n] + P[\mathcal{D}_n^c] \end{align} and so $$ \limsup_{n\rightarrow\infty} P[\mathcal{C}_n] \leq q(1/2)+(1/2) < 1 \quad \Box$$

  • $\begingroup$ Thanks. I know $P\left[\frac{1}{\sqrt{n}}\sum_{i=1}^n(A_i-m) \geq - m(c+k) \right] \rightarrow q$, but can you (precisely) clarify why $P\left[\frac{1}{\sqrt{n}}\sum_{i=1}^n(A_i-m) \geq - m(c+k) + \frac{ckm}{\sqrt{n}} \right] \rightarrow q$? This is not obvious to me. $\endgroup$ – Susan_Math123 Dec 23 '16 at 3:21
  • $\begingroup$ And, in the last step, why did you use limsup? I think you could use lim. Right? Can you clarify please? (Your clarification helps me understand and learn these stuff which is one of the goals of stackexchange.) $\endgroup$ – Susan_Math123 Dec 23 '16 at 3:23
  • 1
    $\begingroup$ If you want, you can just say $P[\frac{1}{\sqrt{n}}\sum_{i=1}^n (A_i-m) \geq -m(c+k) + \frac{ckm}{\sqrt{n}}] \leq P[]$ and then take a limit after. I used $\limsup$ just because I did not want to bother proving the limit exists. $\endgroup$ – Michael Dec 23 '16 at 14:14
  • $\begingroup$ @That was great! $\endgroup$ – Susan_Math123 Dec 29 '16 at 3:50

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.