[math-fun] Propp's birthday problem
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)
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
On Wed, May 27, 2015 at 1:15 PM, James Propp <jamespropp@gmail.com> wrote:
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.
I think that this solution is incomplete. After N rolls, we have chosen (N choose 2) pairs, But we have not chosen them at random, so I think something further needs to be said to argue that choosing (N choose 2) pairs by choosing N values, and choosing all pairs from those values, gives the same result as jif we chose( N choose 2) pairs completely at random.
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).
The extended result is wrong, so whatever additional justification is needed in the original problem is something that isn't true in the extended problem. Take the case of k = 2, Q = 3, where we are flipping a coin until we see the same side 3 times. This will take 3, 4, or 5 flips, with probability 1/4, 3/8, 3/8 So (N choose 3) has value 1, 4, or 10 with probability 1/4, 3/8,, or 3/8, for an expected value of 5.5, not 4.
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.
How do you evaluate (N choose Q) for N < Q in evaluating this formula? as 0? Andy
participants (3)
-
Andy Latto -
James Propp -
Warren D Smith