27 May
2015
27 May
'15
8:29 a.m.
Let the integer-valued random variable N be the number of times you roll a k-sided die until you see a number you've seen before (analogous to successively asking people's birthdays until you encounter the first repeat). E.g., if k=2, then p(N=2)=p(N=3)=1/2. There's no nice formula for the expected value of N, but as I learned from Jim Pitman last week, the formula for the expected value of N-choose-2 couldn't be simpler: it's just k itself! (Check: With k=2, the average of 2-choose-2 and 3-choose-2 is (1+3)/2 = 2.) Can anyone provide a "bijective" proof? Jim Propp