From: lew@ihgp160h200.ih.lucent.com (-Mammel,L.H.)
Subject: Re: Fwd: Birds of the same feather [sci.math added]
Date: 30 Nov 2000 23:05:47 GMT
Newsgroups: sci.math,alt.math.recreational
Summary: [missing]

In article <3A23603E.C448F70C@eigenray.com>, Ray  <usenet@eigenray.com> wrote:
>Let's see how sci.math does with this one...
>
>-------- Original Message --------
>Subject: Birds of the same feather
>Date: Tue, 14 Nov 2000 10:00:24 GMT
>From: Macavity <mxyptlk@hotmail.com>
>Organization: Deja.com - Before you buy.
>Newsgroups: alt.math.recreational
>
>Something I came across yesterday - not sure if it is familiar to you
>all...
>
>You have a black box with N balls in it - each of a different color.
>Suppose you take turns as follows - randomly pick a ball in each hand,
>and paint the left hand ball the same color as the right hand ball.
>You replace both balls in the box before the next turn.
>
>How many turns do you expect before all balls are the same color?


I worked this out as follows. I think this might be more or
less along the lines of Robert Israel's analysis, which
I didn't actually follow, sad to say.

We just analyze one color, looking at the cases where it
"wins". After any draw and replacement ( a turn,) the urn
is in a state i with i red balls. Of course, red (say) "wins"
if i = N, and "loses" if i=0. We note that the probablity
of going from i -> i+1 ( i>0>N ) is always equal to the
probability of i -> i-1, and this value is i*(N-i)/(N-1)/N.

So, we can treat this as a random walk starting from 1
with absorbtion at i=0 and i=N. However,the expected number
of turns per step depends on the state i and is given by
N*(N-1)/i/(N-i)/2 . The 2 is because of the 2 equally
probable transitions.

Now we just have to evaluate the average number of visits
to each state 0<i<N, given that red wins. Since each visit
must terminate with a step, we multiply the visits by the
number of turns per step for each state to get the expected
number of turns taken in each state, and sum over states.

I get that the probability of winning starting from state
i is just i/N, and I get for the average number of visits
to a state, starting from i=1, ( win or lose ) 2*(N-i)/N.

Then the average number of "winning visits" to state i
per trial is :

 	i/N  * 2*(N-i)/N 

and the average number of turns accounted for by these
visits is:

	i/N  * 2*(N-i)/N  * N*(N-1)/i/(N-i)/2 = (N-1)/N
	
but the expected number of wins is 1/N times the number
of trials, so the expected number of turns per winning trial
in each state i is just N-1, and the expected number of turns
in a win for red, or for any other color, is just the number
of nonterminal states times the expected number of turns
in each state, or (N-1)^2.

Lew Mammel, Jr.
==============================================================================

From: israel@math.ubc.ca (Robert Israel)
Subject: Re: Fwd: Birds of the same feather [sci.math added]
Date: 30 Nov 2000 06:52:33 GMT
Newsgroups: sci.math,alt.math.recreational

In article <3A23603E.C448F70C@eigenray.com>, Ray  <usenet@eigenray.com> wrote:

>You have a black box with N balls in it - each of a different color.
>Suppose you take turns as follows - randomly pick a ball in each hand,
>and paint the left hand ball the same color as the right hand ball.
>You replace both balls in the box before the next turn.

>How many turns do you expect before all balls are the same color?

Ariel Landau asked this question in sci.math in September 1995, and 
here was my reply:

From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: A propability problem
Date: 12 Sep 1995 18:37:40 GMT
Organization: University of British Columbia, Vancouver, B.C., Canada
Lines: 41
Distribution: world
Message-ID: <434k1k$phg@nntp.ucs.ubc.ca>
References: <DErCyL.84F@discus.technion.ac.il>
NNTP-Posting-Host: galois.math.ubc.ca

In article <DErCyL.84F@discus.technion.ac.il>, 
lariel@techunix.technion.ac.il (Landau Ariel) writes:
|> Here is an "elementary" probability problem:
|> 
|> From a box containing N>1 coloured balls, we take one ball, and then another
|> ball without replacement, and we paint the second ball of the colour of the
|> first ball (except if they are already of the same colour), and then we put 
|> again the two balls in the box.
|> 
|> At the beginning, the box contains N balls of N different colours.
|> We repeat the previous procedure until all the balls are of the same colour.
|> 
|> What is the expected value of the number of times we have to repeat this
|> procedure?
|> 
|> Conjecture: The solution is (N-1)^2. I could verify it for N=2,3,4,5 and 6.
|> (I guess I would be able to check it for higher values of N as well, but it
|> would take a bit of work...)

Yes, it is (N-1)^2.  
Let Si be the event that the balls eventually end up all coloured i, and
Ii the indicator of this event (1 if it occurs and 0 if not).
Let T be the number of steps until all balls are the same colour.
Let Ai be the initial number of balls of colour i (1 in the problem as 
given,
but let it vary).
Let V(k) = E(I1 T | A1=k) (as far as the random variable I1 T is 
concerned, 
it doesn't matter what Ai is for i <> 1).  We have V(0) = V(N) = 0.
Note that E(I1 | A1=k) = k/N.
By a "first-step analysis", you can show that
    V(k) = k V(1) - (N-1) sum_{j=1}^{k-1} j/(N-k+j) for 1 <= k <= N
For k=N this means V(1) = (N-1)^2/N.
But what we want is
    E(T | A1=A2=...=AN=1) = sum_{i=1}^N E(Ii T | Ai=1) = N V(1) = (N-1)^2.

Also interesting: if N is even and you start out with 2 balls of each of 
N/2
colours, the expected number of steps is (N-1)^2 - N/2.

-- 
Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Y4