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)$).

Curves on a Sphere – Epilogue

I just wanted to add a few more words about the benefits of the probabilistic solution. The nice thing is that it can be applied in all kinds of circumstances. For example, suppose that you have 2 curves with total length less then $2 \pi$. Then, they are either in one hemisphere together, or they are in two complementing hemispheres (or both).
Another thing is that we can let our curve be longer then $2\pi$, if we replace the great circle with something shorter, as long as the product of their length is less then $4 \pi^2$. To see this you only have to realize that the expectation we calculated is actually linear in the length of both curves. In other words, the formula should be $\mathbb{E}(X)= \ell_1 \ell_2 / 2 \pi^2$. As long as this is less then 2, we’re fine.

I guess that you can also use this trick on other surfaces, but I don’t have a good example (beyond Buffon’s needle again).

Curves on a Sphere – the Solution

Here’s the riddle and a solution. And here’s a solution fitting a probablog:

pick a random hemisphere!

All we need to prove now is that this solution works with positive probability, ergo it works.

Consider the circumference of a (uniformly) random hemisphere – it is a random great circle. Now, if this great circle does not intersect the curve, then it is contained in the hemisphere (or in its complement) and we’re done. So we want to analyze the random variable $X$ that is the number of points of intersection of the curve and a random great circle. Specifically, we want to show that $X=0$ with positive probability.

Consider the expectation, $\mathbb{E}(X)$. As always, the expectation is additive, therefore it depends only on the length of the curve and in a linear way. So, $\mathbb{E}(X)=c \ell$, where $\ell$ is the length of the curve and $c$ is some constant. To find out what the contant is, just take a curve for which calculating the expectation is easy – a great circle. The length of a great circle is $\ell = 2 \pi$ and a uniformly random great circle intersects a great circle at exactely 2 points, almost surely. Therefore $c=1/\pi$.

Since our curve is shorter then a great circle, $\mathbb{E}(X) < 2$. However, $X\neq 1$, almost surely, so whenever $X>0$, it is at least 2. This means that the probability of $X>0$ cannot be 1, for then its expectation would be at least 2. Q.E.D.

This solution is not constructive at all (perhaps it could be derandomized?), but that’s also part of its strength, since it can be applied to all kinds of variations of the original riddle. Perhaps I’ll write another post about that. Note, however, that a simple constructive solution exists, and is given in Winkler’s book.

If you’re into (and have some experience with) probability, you probably recognized the connection to Buffon’s needle (not to mention his noodle).

More riddles

Following my own riddle post (OK, not really), Gil Kalai posted two math riddles. I would like to offer a variation on the ant riddle, which also appears in Peter Winkler’s book (it has a whole chapter on ants riddles):

24 ants are randomly placed on a a circular track, each in a random direction. Whenever 2 ants collide they each reverse direction. The track is 1 meter long and ants walk at 1 meter per minute. After one minute, what is the probability that Alice, a randomly chosen ant, finds herself in the place she began?

Would the answer change significantly, if there were 25 ants, instead of 24?

Curves on a Sphere – a Solution and a Hint

First, the solution. This is not one of the two solutions appearing in the book, which are actually nicer.

The curve separates the surface of the sphere into 2 regions. Paint the smaller one black and the other white. Pick (one of) the hemisphere which maximizes the black area in it (there’s a global maximum because of continuity and compactness, but a local maximum also suffices). We claim that the entire black area (hence the curve) is contained in this hemisphere.

Why is that so? Consider the circle circumventing that hemisphere. If it does not intersect the curve, we’re done. Suppose it does intersect the curve. Then all the points of intersection can’t be contained in just one half of the circle, for then a slight rotation of the hemisphere would increase the black area in it. Therefore, there are several points of intersection, such that the shortest distance between any two consecutive points in along the circle. But this sums up to $2 \pi$, contradicting our assumption.

So, what’s with the hint? Isn’t it supposed to come before the solution? Not if the hint is for another solution!

And the hint is this:

Why would this riddle appear in a probablog?

Curves on a Sphere

•October 16, 2008 • 2 Comments

Here’s a riddle from Peter Winkler‘s book “Mathematical Mind-Benders” (which is wholeheartedly recommended):

On the surface of a sphere of radius 1 lies a closed curve of length less then $2 \pi$. Prove that it is contained in some hemisphere.

Since there are currently no readers to this probablog, there’s no reason to wait a couple of days before posting hints or solutions, beside procrastination. Well, I guess that’s a good enough reason for me.