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 , in the sense that it’s expectation is infinite. Suppose you’ve got a bunch (2:19) of , i.i.d. like , what can you say about the distribution of ?

Assume that these random variable are non-negative, then binding the probability of from below is easy: if one of the ‘s is greater then , then so is the sum. This probability is , 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 , one of the variables must be at least , so . This is nice, but most of the time it’s not enough. To be specific, in our case we had , so we get while the lower bound is . 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 , we might as well truncate it at . That is, given a random variable , we produce a new, truncated variable , which is just the minimum of and . This new variable now has a finite expectation, which we can use. First we note that . Then, using Markov’s inequality we get .

Is this better? in our specific case, , so the bound we got was , which matches the lower bound, yey! If we look closely we see that Markov’s inequality implies that , but in our case we get , 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 ), you usually lose a relatively small factor (in this case ). Still, sometimes the first, simpler, bound is better (here it is , which is better when ).

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 . 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 , if we replace the great circle with something shorter, as long as the product of their length is less then . 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 . 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 that is the number of points of intersection of the curve and a random great circle. Specifically, we want to show that with positive probability.

Consider the expectation, . As always, the expectation is additive, therefore it depends only on the length of the curve and in a linear way. So, , where is the length of the curve and 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 and a uniformly random great circle intersects a great circle at exactely 2 points, almost surely. Therefore .

Since our curve is shorter then a great circle, . However, , almost surely, so whenever , it is at least 2. This means that the probability of 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?

And if I might add:

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 , 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

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

No Chance

What is probability, really? A man is about to undergo cardiac surgery.  The doctors tell him he has a 50% chance of full recovery. What does it mean? He would certainly be more assured if they told him his chances are 90%, but why? Ultimately, he either lives or dies. Why does the proportion of other patients who survived under similar conditions matter to him?

As a mathematical theory, probability is not hard to define, but justifying its application to the “real” world (and frankly, what could be more real than mathematics?) is not trivial at all. Indeed, it can be (and is) argued that there is no satisfactory philosophy of probability.

Furthermore, the introduction of quantum mechanics shifted the question of the meaning of probability from the philosophical to the (meta)physical. Prior to that, probability (in physics) only emerged as a result of our lack of knowledge about the state of the system. Quantum mechanics made the system itself probabilistic, and produced probabilities as its predictions. Some of the implications are explored in the following story: No Chance, by Guy Hasson.

Oded Schramm

It is with great grief that I am (re)opening this probablog with the news of Oded Schramm‘s death in a hiking accident. Oded was probably the world’s leading probabilist (though he may not have called himself that), owing to (but not just to) the invention of the Schramm-Loewner evolution (he called it “stochastic Loewner evolution”). You can read more about him and his mathematics here, here and here.
On a more personal note, while I didn’t know Oded very well, I did meet him more then a couple of times, and we have a joint paper (together with Itai Benjamini). He was one of the major reasons I wanted to get a postdoc position in the thoery group at Microsoft Research, and it certainly helped that he wrote one of my recommendation letters. In the past couple of months (since I started working here) we had a few mathematical conversations, but I was not in a hurry, figuring that I had two whole years to work with him. Also, he did not have much time, being very popular among the many visitors coming here in the summer. He was always a joy to talk to and work with.
The picture above is the last picture he took of himself, on the top of Guye Peak.

Zeroth post

This is the post.

Why probability? because it’s fun, and because that’s the part of mathematics I’ve chosen to work in, not the least due to Itai Benjamini, my PhD supervisor.

Why a blog? because I’ve been enjoying several mathematical blogs recently (Terry Tao’s What’s new and Gowers’s Weblog spring to mind) and thought it would be great if we had something similar for the kind of mathematics which interests me the most – probability. The closest thing I could find was Isabel Lugo’s God Plays Dice (which is now one of my favorites) but I think this blog/field combination is big enough for the both of us.

Why now? why not? seriously, I wanted to do this since the summer, but I always had some other stuff in the way, namely, writing applications for postdoc positions. This is behind me now (mostly – now I have to wait for answers) so there are no more obstacles to fuel my procrastination.

(actually, there might be some, I’ll let you know when they crop up)

So, here it is, my shiny new probablog (the word blogability, suggested to me by someone whose name I dare not disclose, was politely declined). Hopefully, it will last beyond the first couple of posts, and might even lead to some serious probability discussion.

Update (04:55, January 23, 2008): Something cropped up alright.