[math-fun] Propp's birthday problem
Propp: 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. --WDS: I agree something must be wrong... But what? Apparently my reasoning was valid (anyhow, yielded the right answer!) when Q=2, but not for Q>2. Perhaps my reasoning still works when Q>2 to yield a lower bound?
Well, ok, let me just try to solve the Q-version of Propp/Pitman problem by brute force. The chance the Nth dice roll yields for the first time Q equal rolls, is k^(-N) times the number of N-letter words from k-size-alphabet containing exactly one Q-subset including the last latter, of all-equal letters, namely Binomial(N-1,Q-1) * (k-1)^(N-Q) * k^(1-N). So the expected value of F(N) ought to be Sum[ Binomial[N-1,Q-1]*(k-1)^(N-Q)*k^(1-N)*F(N), {N,Q,infinity} ] and whenever the sum is doable you will get a closed form. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
So the expected value of F(N) ought to be Sum[ Binomial[N-1,Q-1]*(k-1)^(N-Q)*k^(1-N)*F(N), {N,Q,infinity} ] and whenever the sum is doable you will get a closed form.
--Sorry, that sounded good when I wrote it, but it yields wrong answers. F(N)=1 ==> sum/k=1. F(N)=N ==> sum/k=kQ. F(N)=(N-1)*N/2 ==> sum/k=kQ (kQ+k-2)/2. F(N)=(N choose 3) ==> sum/k=k*Q * (k^2*Q^2+(k-2)*k*3*Q+?) / 6 where ? is a certain quadratic function of k, and these answers are the WRONG answers to Propp's problem. Jeez. This problem evidently is out to get me. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (1)
-
Warren D Smith