or the original paper, where the idea is ascribed to Rubin).The setting is balls and bins with feedback: I have two bins, and I'm repeatedly randomly throwing balls into the bins one at at time. When there are x balls in bin 1 and y balls in bin 2, the probability the ball I throw lands in bin 1 is x^p/(x^p+y^p), and the probability it lands in bin 2 is y^p/(x^p + y^p). Initially both bins start with one ball. The goal is to show that when p is greater than 1, at some point, one bin gets all the remaining balls thrown. That is, when there's positive feedback, so the more balls you have the more likely it is that you'll get the next one in a super-linear fashion, eventually the system becomes winner-take-all.
We use the following "exponential embedding". Consider the following process for bin 1. At time 0, we associated an an exponentially distributed random variable X_1 with mean 1 = 1/1^p with the bin. The "time" that bin 1 receives its next ball is X_1. Now it has two balls. We then associate an exponentially distributed random variable X_2 with mean 1/2^p with the bin. And so on.
Do the same thing with bin 2, using random variables Y_1, Y_2, ...
Now, at any point in time, due to the properties of the exponential distribution -- namely, it's memoryless, and the minimum of two exponentials with mean a_1 and a_2 will be the first with probability proportional to 1/a_1 and the second with probability 1/a_2 -- if the loads in the bins are x for bin 1 and y for bin 2, then the next ball will fall into bin 1 is x^p/(x^p+y^p), and the probability it lands in bin 2 is y^p/(x^p + y^p). That is, this exponential process is equivalent to the initial balls and bins process.
Now let X = sum X_i and Y = sum Y_i. The infinite sums converge with probability 1 and are unequal with probability 1. So suppose X < Y. Then at some finite "time" in our exponential embedding, bin 1 receives an infinite number of balls while bin 2 just has a finite number of balls, and similarly if Y < X. So eventually, one bin will be the "winner" and take all the remaining balls.
In my mind, that's a beautiful proof.
4 comments:
Are you using this as a metaphor for wealth in this country? :)
Dark humor aside, yes, it's a beautiful proof.
Hi Mike!
Nice. Here are some pedagogical comments.
- If I was teaching this, I would do it just for p=1: it's simpler but the argument is the same and it is just as beautiful. Then in the end I would throw in a comment: "Consider this generalization. The proof extends (exercise)." That is, I try to teach the simplest problem whose solution uses the ideas I want to convey. I know that many mathematicians do the opposite (try to see how far the ideas can go, and show the most general result that can be obtained from those ideas), but I find that simpler works better for me.
- If I was teaching this, instead of defining the process formally I would do it from example, with concrete values for x and y. "When there are 7 balls in bin 1 and 3 balls in bin 2, the probability that the ball lands in bin 1 is 7/(7+3)=.7 and the probability that it lands in bin 2 is 3/(7+3)=.3." Students can always ask questions if that's not enough to make things clear.
- Also, what is missing for a computer scientist's mind such as mine is: Why? Where does this process come from? I almost stopped reading your entry in the middle of the second paragraph because the motivation is missing. Even for a blog entry, a sentence about that would be greatly helpful.
By the way, this is a nice post. Enjoyable for me to read. I knew this already, but if you did it with something that I didn't know, it would be great fun, a very nice way to learn a little nugget of science.
Um, p=2, not p=1. (Embarrassed.)
Hi Mike,
C5838ould you please show why "the infinite sums converge with probability 1 and are unequal with probability 1"? Thank you very much.
Post a Comment