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