12
$\begingroup$

Let $X$ be an integer-valued random variable and let $X_n$ be the sum of $n$ independent realizations of $X$. I would like to understand the behavior of $X_n/n$ for large $n$ in some cases where $X$ has no expected value and therefore the central limit theorem (along with Chebyshev's Theorem, etc.) does not apply.

For a concrete example, let $X$ have the following distribution: $$Prob(X=0)=1/3\qquad Prob(X=4^k)=1/4^{k+1}\qquad Prob(X=-4^{k})=1/4^{k+1}$$ with all other probabilities zero.

Note that $X$ has no expected value so we can't use the central limit theorem. Still, I'd like to have a good way to estimate $Prob(X_n/n > M)$ for a given large $n$ and $M$.

Note also that in this example $Prob(X_n/n=M)$ can depend on number theoretic properties of $M$ (and in particular will not be monotonic in $M$), but I'm hoping that when $n$ is big and we consider $Prob(X_n/n > M)$, this sort of thing will wash out.

I've done some relevant calculations, but I wonder whether I'm missing either some knowledge or some insight that would make this easier to understand.

$\endgroup$
8
  • 2
    $\begingroup$ Try applying the standard techniques to truncations of $X$? $\endgroup$ Mar 3, 2014 at 8:48
  • $\begingroup$ One might also ask about sums like this when the payoffs $c^k$ increase at a different rate than the probabilities $p^k$ decrease. I think for equal rates $(cp=1)$, each of the positive and negative parts scale as $\log n$ projecteuclid.org/euclid.aoms/1177731094 and for different rates with no expectation, the scaling is as a power of $n$, with some dependence on the fractional part of $\log_p n$. $\endgroup$ Mar 3, 2014 at 9:36
  • 1
    $\begingroup$ What about the continuous analog of X Cauchy? That has similar asymptotics, and the mean of n iid Cauchy variables is again Cauchy. $\endgroup$
    – user44143
    Mar 3, 2014 at 11:00
  • 2
    $\begingroup$ I think what you're looking for are stable laws. If you take averages of random variables that have a variance, you obtain a normal distribution after rescaling. If you average random variables that have lower moments, you can expect convergence after rescaling to a stable law (apparently this is a theorem of Gnedenko and Kolmogorov). The stable law with 1st moment but no more is exactly the Cauchy random variable as @MattF hints at. $\endgroup$ Mar 3, 2014 at 15:43
  • 2
    $\begingroup$ Steve: a good intuition-building exercise is to simulate independent Cauchy random variates, then plot a running histogram of the averages. Instead of concentrating on 0 (as in the case of finite mean), you'll see the histogram itself trace out the Cauchy PDF. The point here isn't that the CLT is missing, it's that the LLN is. You'll probably have to dig into the literature on Large Deviations Theory to say something precise about these tail probabilities. As a mathematical economist, you'll like Large Deviations: lots of hemicontinuous functions & clever uses of convexity. $\endgroup$ Mar 3, 2014 at 18:57

1 Answer 1

13
$\begingroup$

We can attack this problem by using Fourier transforms (i.e. characteristic functions). I'll consider the example in the problem where $X$ is a random variable taking the value $0$ with probability $1/3$, and $4^{k}$ and $-4^{k}$ with probability $1/4^{k+1}$ (for $k=0$, $1$, $\ldots$). I'll show that the probability that $|X_n|/n >M$ is about a constant times $1/M$ (more precise result below).

Fix a smooth function $\Phi$ compactly supported in $[-1,1]$ and approximating the characteristic function of that interval. Concretely, suppose $\epsilon$ is small and $\Phi(x)=1$ on $[-1+\epsilon, 1-\epsilon]$ and is between $0$ and $1$ on the rest of $[-1,1]$. Since $\Phi$ is smooth, its Fourier transform ${\hat \Phi}(\xi) = \int_{-\infty}^{\infty}\Phi(x) e^{-2\pi i x\xi} dx$ has rapid decay for $|\xi|$ large.

Now let $n$ and $M$ be large and consider $$ {\Bbb E}\Big(\Phi\Big(\frac{X_n}{nM}\Big)\Big). $$
Note that $$ \text{Prob} (|X_n| >nM) \le 1 -{\Bbb E}(\Phi(X_n/(nM))) \le \text{Prob}(|X_n| > (1-\epsilon)nM), $$ and so our problem is to understand the expectation above. By Fourier inversion, $$ {\Bbb E}(\Phi(X_n/(nM))) = \int_{-\infty}^{\infty} {\hat \Phi}(\xi) {\Bbb E}\Big( e^{2\pi i \xi X_n/(nM)}\Big) d\xi = \int_{-\infty}^{\infty} {\hat \Phi}(\xi) \Big( {\Bbb E}\Big( e^{2\pi i \xi X/(nM)}\Big)\Big)^{n} d\xi. $$

Now we compute that $$ {\Bbb E}\Big( e^{2\pi i \xi X/(nM)}\Big) = \frac{1}{3} + 2 \sum_{k=0}^{\infty} \frac{1}{4^{k+1}} \cos \Big( \frac{2\pi \xi 4^k}{nM}\Big) = 1 - 2\sum_{k=0}^{\infty} \frac{1}{4^{k+1}}\Big (1-\cos \Big( \frac{2\pi \xi 4^k}{nM}\Big) \Big). $$ Now using that $(1-\cos(x)) = O(\min(x^2, 1))$ we see that $$ \sum_{k=0}^{\infty} \frac{1}{4^{k+1}}\Big (1-\cos \Big( \frac{2\pi \xi 4^k}{nM}\Big) \Big) = O\Big( \frac{|\xi|}{nM}\Big). $$ Therefore, using $(1-x)^n = 1-nx +O(n^2 x^2)$ for $0\le x\le 1$,
$$ {\Bbb E}(\Phi(X_n/(nM))) = \int_{-\infty}^{\infty} {\hat \Phi}(\xi) \Big( 1- 2n \sum_{k=0}^{\infty} \frac{1}{4^{k+1}}\Big (1-\cos \Big( \frac{2\pi \xi 4^k}{nM}\Big) \Big) + O\Big(\frac{\xi^2}{M^2}\Big) \Big) d\xi. $$ Since ${\hat \Phi}$ has rapid decay, the error term above is $O(1/M^2)$ (with the implied constant depending only on the fixed function $\Phi$). Using Fourier inversion, we conclude that $$ {\Bbb E}({\Phi }(X_n/(nM))) = \Phi(0) - n \sum_{k=0}^{\infty} \frac{1}{4^{k+1}} \Big(2 \Phi(0) - \Phi\Big(\frac{4^k }{nM} \Big) -\Phi\Big(-\frac{4^k}{nM}\Big)\Big) + O\Big(\frac{1}{M^2}\Big). $$ Since $\Phi(0)=1$, we get $$ 1- {\Bbb E}({\Phi }(X_n/(nM))) = n \sum_{k=0}^{\infty} \frac{1}{4^{k+1}} \Big(2 - \Phi\Big(\frac{4^k }{nM} \Big) -\Phi\Big(-\frac{4^k}{nM}\Big)\Big) + O\Big(\frac{1}{M^2}\Big). $$ By our choice for $\Phi$, the main term above is $$ \ge 2n \sum_{k, 4^{k} \ge nM} \frac{1}{4^{k+1}}, $$ and is $$ \le 2n \sum_{k, 4^{k} \ge (1-\epsilon) nM} \frac{1}{4^{k+1}}. $$

Thus we have obtained a good understanding of the probability that $|X_n|/n$ is large. Note also that the precise answer will have discontinuities when $nM$ gets near a power of $4$, but in any case the probability is about a constant times $1/M$.

$\endgroup$
4
  • $\begingroup$ This is terrific, and is stronger than, but consistent with, what I had come to expect from working through a paper of Feller that Douglas Zare referenced in a now-deleted answer. Thanks very much indeed for this. (PS---A minor typo---I believe your second displayed equation should end in $(1-\epsilon)nM$, not $(1-\epsilon)M$.) $\endgroup$ Mar 5, 2014 at 6:19
  • $\begingroup$ I haven't done any hard work on this yet, so maybe I'm missing something easy but ---- I wonder if we can adapt your method to study the case where $N$ is large but $M$ is very small, i.e. to estimate the probability that $|X_n|/n$ falls into a given small interval around zero. $\endgroup$ Mar 5, 2014 at 15:05
  • $\begingroup$ @StevenLandsburg: Probably something can be done, but it needs work. Work above says that if $nM$ is not near a power of $4$, then the chance that $|X_n| >nM$ is essentially the same as the largest of $n$ independent picks from $X$ being larger than $nM$ in size. That is the sum is dominated by its maximum, and once one sees this one can give an alternative proof than the one I gave. From this one should also be able to say that if $|X_n|/n$ is small then the maximum of the $n$ choices of $X$ is also small, and then conditioning on that event you'd be able to compute the desired probability. $\endgroup$
    – Lucia
    Mar 5, 2014 at 15:15
  • $\begingroup$ I would like to cite this result in a paper that I'm submitting for publication (albeit to a non-research-level journal). [In fact, it will be the only nontrivial mathematical result in the paper.] I'd like to thank you in the paper but am unsure whether you want to blow your anonymity. I'll be glad if you write me at the address on my profile page to let me know what you prefer. $\endgroup$ Apr 25, 2014 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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