5
$\begingroup$

I have a power law distribution $X$ with exponent $c$: $$p(X=t) = \left\\{\begin{array}{cl}(c-1)/t^{c} & t \geq 1 \\\\ 0 & t < 1\end{array}\right.$$

From $X$ I take $n$ independent samples $X_1, \ldots, X_n$ and would like to give a tail bound for the mean; i.e. a good bound on $\Pr[\frac{1}{n}\sum X_i > t]$.

Unfortunately, my $X$ is unbounded and much of the work on concentration of measure assumes bounded variables. However, I do know that $X$ has bounded moments, so I can bound the variance and get a weak concentration. But if $c$ is larger, say $10$, I ought to be able to use the higher moments to get a stronger result. In particular it seems like the moment method outlined in http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/ should be applicable, but the treatment there assumes bounded variables.

I can work through the modifications to that treatment myself and get a reasonable result, but it's kind of messy. So my question is: is there any existing published theorem that does what I want, so I don't have to add an ugly proof to my paper's appendix?

Improve this question
$\endgroup$
4
  • $\begingroup$ It looks like you want t to be any real number, not just an integer, so I think your notation is wrong and you want the probability density function f(t), not p(X=t). Anyway, you have a very explicit formula; if you only need this result, why don't you just work out the probability directly using characteristic functions/Fourier transforms and seeing what it gives? It looks a little messy, but if you check Special Functions books it shouldn't be too hard (and most of the details can be left out for a paper). Besides, you might find it gives better results than the general theory. $\endgroup$
    – Zen Harper
    Commented Jun 21, 2010 at 3:13
  • 1
    $\begingroup$ Eric, in Section 2 of that article, Terry explains how to use the truncation method to adapt the results to unbounded random variables. Have you tried following that method? $\endgroup$
    – Tom LaGatta
    Commented Jun 21, 2010 at 3:35
  • $\begingroup$ Eric: I doubt you'll find a prepackaged result for your setting. Also, you're unlikely to do much better than the moment method; since your distribution doesn't have finite exponential moments you can't use Chernoff-type bounds, which are the usual tool when, for example, the random variables are bounded. Zen's suggestion of using Fourier transforms and classical special functions theory is also good, but I doubt it will improve over the moment method unless you care about precise constants (although it might well be less messy). $\endgroup$
    – Mark Meckes
    Commented Jun 21, 2010 at 14:47
  • $\begingroup$ Go to google books and google scholar and enter this term: "Pareto distribution". That's what this is. Also: you're taking a sample of size $n$, not "$n$ samples. $\endgroup$
    – Michael Hardy
    Commented Aug 16, 2010 at 0:42

1 Answer 1

Reset to default
3
$\begingroup$

This topic is examined by Olivier Catoni in his recent paper: High confidence estimates of the mean of heavy-tailed real random variables. Denote the mean, variance and kurtosis of your distribution by $m$, $v$ and $\kappa$, respectively. Then, by Catoni's proposition 7.1, the following holds with probability at least $1-2\epsilon$: $$\frac{|(\frac{1}{n}\sum_{i=1}^n X_i) - m|}{\sqrt{v}} \leq \frac{2\log (\frac{3}{2}\epsilon^-1)\sqrt{\kappa}}{5n} + \sqrt{\frac{2\log (\frac{3}{2}\epsilon^-1)}{n}} + \left(\frac{3\kappa}{2\epsilon n^3}\right)^{1/4}\left(1 + \frac{3^5(n-1)\log (\frac{3}{2}\epsilon^-1)^2\kappa}{2500n^2} + \frac{12\sqrt{2}\log(\frac{3}{2}\epsilon^-1)^{3/2}\sqrt{\kappa}}{25n^{3/2}}\right)^{1/4}$$ There is no mention of boundedness but of course you will want to check his proof.

Are you using the empirical average as an estimate of the mean? If so, you may prefer Catoni's estimator, which is conceptually similar to the truncation trick described in Tao's notes. The raw empirical average performs poorly because a single $X_i$ can throw it wildly off course. Instead, blunt the incoming $X_i$'s and use them to update a guess of $m$. Of course, an initial guess is needed, so the scheme is naturally iterative.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .