If N denotes the number of times you toss a k=2-sided coin until one side has come up Q=3 times, then the expected value of N-choose-3 is (2/8)(1)+(6/16)(4)+(12/32)(10)=11/2, not k^(Q-1)=4, so Warren's formula is incorrect, and the reasoning that he applied to the case Q=2 is inadequate. Jim Propp On Wednesday, May 27, 2015, Warren D Smith <warren.wds@gmail.com> wrote:
James Propp: 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?
--WDS SOLUTION: Nice formula. N-choose-2 is the number of dice-pairs, and among those pairs, there is EXACTLY ONE equal-pair, because when you rolled N-1 dice no two were equal, but then the Nth dice is equal, necessarily to exactly one, of the preceding.
The chance a given pair is equal is 1/k. Among (N choose 2) pairs we have exactly one such special pair, so the "rate" of special pairs clearly being 1/k, we see that the expected value of (N choose 2) must equal k.
EXTENDED RESULT: More generally, if you kept rolling dice until a Q-element subset of the dice all happened to be equal (for the first time when N dice have been rolled) then expected value of (N choose Q) would equal k^(Q-1).
RELATED PUZZLE FOR YOU: In a random permutation of k items. Start from a random item. Walk to its successor (according to the perm) then to its successor, and so on, until you re-reach the item you started with, in all visiting N of the items (forming a cycle in the perm with cardinality N). The expected value of (N choose Q) is, I believe, binomial(k+1,Q) * [k-Q+1]/[k*(Q+1)] for any fixed integer Q>0.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun