11
$\begingroup$

Let $\{X_n:n\ge1\}$ be a sequence of independent Bernoulli random variables with $$P\{X_k=1\}=1-P\{X_k=0\}=\frac{1}{k}.$$ Set $$S_n=\sum^{n}_{k=1}\left(X_k-\frac{1}{k}\right), \ B_n^2=\sum^{n}_{k=1}\frac{k-1}{k^2}$$ Show that $\frac{S_n}{B_n}$ converges in distribution to the standard normal variable $Z$ as $n$ tends to infinity.

My attempt is to use the Lyapunov CLT, therefore we need to show there exists a $\delta>0$ such that, $$\lim_{n\rightarrow \infty}\frac{1}{B_n^{2+\delta}}\sum_{k=1}^{n}E[|X_k-\frac{1}{k}|^{2+\delta}]=0. $$

So set $\delta=1$$$ \sum_{k=1}^{n}E\left|X_k-k^{-1}\right|^{3}=\sum_{k=1}^{n} \left(\frac{1}{k}-\frac{3}{k^2}+\frac{4}{k^3}-\frac{2}{k^4}\right) $$ and $$ B_n^3=\left( \sum_{k=1}^n \frac{1}{k}-\frac{1}{k^2} \right) \sqrt{\left( \sum_{k=1}^n \frac{1}{k}-\frac{1}{k^2} \right)} $$

By evaluating for large n's on the computer it shows how both $\sum_{k=1}^{n}E|X_k-k^{-1}|^{3} \to \infty$ and $B_n^3 \to \infty$ as $n \to \infty$. But $B_n^3$ increases faster than $B_n^2$ so $\frac{\sum_{k=1}^{n}E|X_k-k^{-1}|^{3}}{B_n^3} \to 0$. Can someone help me prove this convergence holds?

$\endgroup$
  • 7
    $\begingroup$ This is Example 27.3 of Probability and Measure by Patrick Billingsley. $\endgroup$ – Zhanxiong Mar 27 '16 at 15:02
10
$\begingroup$

It may be instructive to demonstrate this result from first principles and basic results, exploiting properties of cumulant generating functions (exactly as in standard proofs of the Central Limit Theorem). It requires us to understand the rate of growth of generalized harmonic numbers $$H(n,s)=\sum_{k=1}^n k^{-s}$$ for $s=1, 2, \ldots.$ These growth rates are well-known and easily obtained by comparison to the integrals $\int_1^n x^{-s}dx$: they converge for $s \gt 1$ and otherwise diverge logarithmically for $s=1$.


Let $n \ge 2$ and $1 \le k \le n$. By definition, the cumulant generating function (cgf) of $(X_k - 1/k)/B_n$ is

$$\psi_{k,n}(t) = \log\mathbb{E}\left(\exp\left(\frac{X_k - 1/k}{B_n}t\right)\right) = -\frac{t}{k B_n} + \log\left(1 + \frac{-1 + \exp(t/B_n)}{k}\right).$$

The series expansion of the right hand side, obtained from the expansion of $\log(1+z)$ around $z=0$, takes the form

$$\psi_{k,n}(t) = \frac{(k-1)}{2 k^2 B_n^2}t^2 + \frac{k^2 - 3k + 2}{6 k^3 B_n^3} t^3 + \cdots + \frac{k^{j-1} - \cdots \pm (j-1)!}{j! k^j B_n^j}t^j + \cdots.$$

The numerators of the fractions are polynomials in $k$ with leading term $k^{j-1}$. Because the log expansion converges absolutely for $\left|\frac{-1 + \exp(t/B_n)}{k}\right| \lt 1$, this expansion converges absolutely when

$$\left|\exp(t/B_n) - 1\right| \lt k.$$

(In case $k=1$ it converges everywhere.) For fixed $k$ and increasing values of $n$, the (obvious) divergence of $B_n$ implies the domain of absolute convergence grows arbitrarily large. Thus, for any fixed $t$ and sufficiently large $n$, this expansion converges absolutely.

For sufficiently large $n$, then, we may therefore sum the individual $\psi_{k,n}$ over $k$ term by term in powers of $t$ to obtain the cgf of $S_n/B_n$,

$$\psi_n(t) = \sum_{k=1}^n \psi_{k,n}(t) = \frac{1}{2}t^2 + \cdots + \frac{1}{B_n^j}\left(\sum_{k=1}^n \left(k^{-1} - \cdots \pm (j-1)!k^{-j}\right)\right)\frac{t^j}{j} + \cdots.$$

Taking the terms in the sums over $k$ one at a time requires us to evaluate expressions proportional to

$$b(s,j) = \frac{1}{B_n^j}\sum_{k=1}^n k^{-s}$$

for $j \ge 3$ and $s=1, 2, \ldots, j$. Using the asymptotics of generalized harmonic numbers mentioned in the introduction, it follows easily from

$$B_n^2 = H(n,1) - H(n,2) \sim \log(n)$$

that

$$b(1,j) \sim (\log(n))^{1-j/2}\to 0$$

and (for $s \gt 1$)

$$b(s,j) \sim (\log(n))^{-j/2}\to 0$$

as $n$ grows large. Consequently all terms in the expansion of $\psi_n(t)$ beyond $t^2$ converge to zero, whence $\psi_n(t)$ converges to $t^2/2$ for any value of $t$. Since convergence of the cgf implies convergence of the characteristic function, we conclude from the Levy Continuity Theorem that $S_n/B_n$ approaches a random variable whose cgf is $t^2/2$: that is the standard Normal variable, QED.


This analysis uncovers just how delicate the convergence is: whereas in many versions of the Central Limit Theorem the coefficient of $t^j$ is $O(n^{1-j/2})$ (for $j \ge 3$), here the coefficient is only $O(((\log(n))^{1-j/2})$: the convergence is much slower. In this sense the sequence of standardized variables "just barely" becomes Normal.

We can see this slow convergence in a series of simulations. The histograms display $10^5$ independent iterations for four values of $n$. The red curves are graphs of standard normal density functions for visual reference. Although there is evidently a gradual tendency towards normality, even at $n=1000$ (where $(\log(n))^{-1/2} \approx 0.38$ is still sizable) there remains appreciable non-normality, as evidenced in the skewness (equal to $0.35$ in this sample). (It is no surprise the skewness of this histogram is close to $(\log(n))^{-1/2}$, because that's precisely what the $t^3$ term in the cgf is.)

Figure: histograms for n=30, 100, 300, 1000

Here is the R code for those who would like to experiment further.

set.seed(17)
par(mfrow=c(1,4))
n.iter <- 1e5
for(n in c(30, 100, 300, 1000)) {
  B.n <- sqrt(sum(rev((((1:n)-1) / (1:n)^2))))
  x <- matrix(rbinom(n*n.iter, 1, 1/(1:n)), nrow=n, byrow=FALSE)
  z <- colSums(x - 1/(1:n)) / B.n
  hist(z, main=paste("n =", n), freq=FALSE, ylim=c(0, 1/2))
  curve(dnorm(x), add=TRUE, col="Red", lwd=2)
}
$\endgroup$
6
+50
$\begingroup$

You have a great answer already. If you want to complete your own proof, too, you can argue as follows:

Since $\sum_{k=1}^n 1/k^i$ converges for all $i>1$ and diverges for $i = 1$ (here), we may write

\begin{align}S(n):=\sum_{k=1}^n\left(\frac{1}{k} - \frac{3}{k^2} + \frac{4}{k^3} - \frac{3}{k^4} \right) = \sum_{k=1}^n\frac{1}{k} + O(1). \end{align}

By the same argument,

$$ B^2_n = \sum_{k=1}^n\frac{1}{k} + O(1). $$

Consequently, $S(n) / B_n^2 = O(1)$ and, thus,

$$ S(n)/B_n^3 = O(1)(B_n^2)^{-1/2} \to 0, $$

which is what we wanted to show.

$\endgroup$
2
$\begingroup$

First your random variables are not identically distributed if the distributions depend on $k$ ;)

Also I wouldn't use your $B_n$ notation as:

  • capital letters are usually reserved for random variables.
  • it's just the sum of the variances so I would use a notation involving a $\sigma$ symbol to make this obvious.

Then regarding the question I don't know if this is an exercise or research and what tools you're allowed to use. If you're not trying to re-prove known theorems, I'd just say it's a central limit theorem for independent non-identically distributed but uniformly bounded RV and call it a day. I don't have a good source at hand but it shouldn't be too hard to find one, for example look at https://mathoverflow.net/questions/29508/is-there-a-central-limit-theorem-for-bounded-non-identically-distributed-random.

Edit : My bad, of course the uniformly bounded condition is not enough, you also need $$\sum_{k=1}^n \sigma_k^2 \to \infty$$

$\endgroup$

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.