Conference rusure::math

I don't know what is meant by the "average" number of tosses each has to make.

There is no upper bound on the number of tosses each has to make until they
obtain the proper sequence of outcomes.  However, the probability that each
will require more than n tosses decreases asymptotically towards zero as
n increases without bound.

These probabilities are given as follows:

P(Arthur needs >n tosses to obtain HH) = f(n+2) / 2^n, 
where f(i) is the i-th Fibonacci number, starting with 
	f(1) = f(2) = 1, 
	f(3) = 2, 
	f(i+2) = f(i+1) + f(i),    etc.

P(Betty needs >n tosses to obtain HT) = (n+1) / 2^n.

There is a 50% chance Arthur will require 4 or fewer tosses to finish, and
there is a 50% chance Betty will require 3 or fewer tosses to finish.

Arthur has about a 14% chance of needing more than 10 tosses, while Betty
has only about a 1% chance of needing more than 10 tosses.

Re: .1 

The formulas were derived by conjecture after looking at small values of n.

They may be verified by mathematical induction.

    Arther wants two heads (like Zaphod has!).  The expected number of
    tosses is:
    	E = 1/2 * (1+H) + 1/2 * (1+E), where
    	H = 1/2 * 1     + 1/2 * (1+E).
    So
      	E = 6 (tosses).
    
    Betty wants a head and a tail, in that order.  The expected tosses are:
    	E = 1/2 * (1+H) + 1/2 * (1+E), where
    	H = 1/2 * (1+H) + 1/2 * 1.
    (Note that after head-head, we don't have to go back to the beginning).
    So
    	E = 4 (tosses).
    
>   (ii) What is the probability that Betty makes _fewer_ tosses
>   than Arthur (rather than the same number or more than Arthur)?
    
    Let Pa(n) be the probability that Arthur has to make n tosses, and
    let Pb(n) be the probability that Betty has to make n tosses.  Then
    (ii) is simply:
    
        inf inf
    	Sum Sum Pa(a) * Pb(b) * (b < a)
    	a=2 b=2
    
    So whats Pa(n)?  Think of this as a three-state machine,
    	Starting state "s", final state "a", and transition table:
    
    		State Coin NextState
    		  s     H    h
    		  s     T    s
    		  h     H    a
    		  h     T    s
    
    	Pa(1) = 0
    	Pa(n) = 1/2 * Ph(n-1),			Pa(0) = 0
        Ph(n) = 1/2 * Ps(n-1),			Ph(0) = 0
        Ps(n) = 1/2 * Ps(n-1) + 1/2 * Ph(n-1),	Ps(0) = 1
    
    So
    	Ps(1) = 1/2
    	Ps(n) = 1/2 * Ps(n-1) + 1/4 * Ps(n-2),
    	Ps(n) = F(n+1)/2^n,	where the F are Fibonacci numbers.
    And
    	Pa(1) = 0
    	Pa(n) = 1/4 Ps(n-2) = F(n-1)/2^(n-4).
    
    Et cetera.

    Re: .3

    >	Pa(n) = 1/4 Ps(n-2) = F(n-1)/2^(n-4).	[ F(n) is the nth Fibonacci # ]
						[ F(1) = F(2) = 1 ]
						[ F(n) = F(n-1) + F(n-2), n>2 ]
    I get:
	Pa(n) = 1/4 Ps(n-2) = F(n-1)/2^n
    and by a similar derivation for Pb(n):
	Pb(n) = (n-1)/2^n

    Now:
	inf         inf
	sum Pa(i) = sum Pb(i) = 1
	i=2         i=2
 
    So, interestingly (to me at least!):

	inf              inf
	sum F(i-1)/2^i = sum (i-1)/2^i = 1
	i=2              i=2

    - Don

From .1, the probability of finishing in exactly n tosses is
	Pa(n) = f(n-1)/2^n  for Arthur, and
	Pb(n) = (n-1)/2^n   for Betty.

From .3, the answer to (ii) is

        inf inf
    	Sum Sum Pa(a) * Pb(b) * (b < a)
    	a=1 b=1

          inf a-1		         inf 		a-1
    	= Sum Sum F(a-1)/2^a (b-1)/2^b = Sum F(a-1)/2^a Sum (b-1)/2^b
    	  a=2 b=1			 a=2 		b=1

          inf 				       inf
    	= Sum F(a-1)/2^a (2^(a-1)-a)/2^(a-1) = Sum F(a-1)/2^a (1-a/2^(a-1))
    	  a=2 				       a=2

From .4, we know the sum of F(a-1)/2^a, so the above summation becomes

              inf 
    	= 1 - Sum 2 a F(a-1)/4^a
    	      a=1		(note that we lowered the index to 1)

But F(n) = c0 r0^n + c1 r1^n, where r0 = (1+sqrt(5))/2, r1 = (1-sqrt(5))/2,
c0 = 1/sqrt(5), and c1 = -1/sqrt(5).  So the above becomes:

              inf 
    	= 1 - Sum 1/2 a (c0 (r0/4)^(a-1) + c1 (r1/4)^(a-1))
    	      a=1

Notice that 1 + x + x^2 + ... = 1/(1-x), and by taking derivatives of both
sides, we have
				inf
	1 + 2 x + 3 x^2 + ... = Sum a x^(a-1) = 1/(1-x)^2
				a=1

So the answer to (ii) can now be simplified to

        
    	1 - 1/2 c0/(1 - r0/4)^2 + 1/2 c1/(1 - r1/4)^2

which is

	65/121 ~= 0.53719008.

    The published solution confirms the responses here.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.