A Truncating Trick

While discussing a problem, Asaf Nachmias, a fellow post doc here, showed me the following trick. Suppose you have a not so well behaved random variable X, in the sense that it’s expectation is infinite. Suppose you’ve got a bunch (2:19) of X_i, i.i.d. like X, what can you say about the distribution of S_n = \sum_{i=1}^n X_i?

Assume that these random variable are non-negative, then binding the probability of S_n \ge M from below is easy: if one of the X_i‘s is greater then M, then so is the sum. This probability is 1-(1-P(X > M))^n \approx n P(X \ge M), when this last term is small. But is this actually the right order of magnitude?

One simple approach is that for the sum to be more then M, one of the variables must be at least M/n, so P(S_n \ge M) \le n P(X \ge M/n). This is nice, but most of the time it’s not enough. To be specific, in our case we had P(X \ge t) \approx 1/\sqrt{t}, so we get P(S_n \ge M) \le n P(X \ge M/n) \approx n\sqrt{n}/\sqrt{M} while the lower bound is \approx n P(X \ge M) = n/\sqrt{M}. It seems pretty obvious that the upper bound could be improved, but how?

Here’s the trick: if we’re interested in the probability of some variable being more then M, we might as well truncate it at M. That is, given a random variable X, we produce a new, truncated variable X\wedge M, which is just the minimum of X and M. This new variable now has a finite expectation, which we can use. First we note that E(S_n \wedge M) = E((\sum_{i=1}^n X_i) \wedge M) \le E(\sum_{i=1}^n X_i \wedge M) = n E(X\wedge M). Then, using Markov’s inequality we get P(S_n \ge M)=P(S_n \wedge M = M ) \le E( S_n \wedge M) /M \le n E(X\wedge M) /M.

Is this better? in our specific case, E(X\wedge M) \approx \sqrt{M}, so the bound we got was n/\sqrt{M}, which matches the lower bound, yey! If we look closely we see that Markov’s inequality implies that E(X\wedge M)/M \ge P(X \ge M), but in our case we get E(X\wedge M)/M \approx P(X \ge M), so the upper and lower bound match, up to a constant. It’s easy to see that this last condition is slightly stronger then having an infinite expectation, so we can’t expect it to work every time, but even when it’s not true (consider a random variable with P(Y \ge M) = 1/M), you usually lose a relatively small factor (in this case \log(M)). Still, sometimes the first, simpler, bound is better (here it is n^2/M, which is better when n < \log(M)).

Advertisements

~ by Ori on November 20, 2008.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: