You and three friends decide to play a strange game.
Into a hat you place four slips of paper. One has a gold star, one has a red X, and the other two are blank.
Each round will proceed as follows: Each person will select a piece of paper from the hat. Whichever player chooses the slip with the red X joins the "team" of the player who chooses the slip with the gold star. Then all four slips are returned to the hat and the process is repeated. The game ends when all four players are on the same team.
1) On average, how many rounds will the game last until all four players are on the same team?
2) Find a general solution for n players (where the hat contains one gold star, one red X, and n2 blank slips).
Initially we can consider each person to be a team so there are 4 teams. Membership: (1,1,1,1)
With just 1 round this is transformed into 3 teams, one with two members and two with one member each. Membership: (2,1,1). This is the only configuration of 3 teams.
The next round this either does not change (prob. 1/2, as this happens if either of the two members on the 2member team gets the red X so he either stays on the same team or just changes the identity of his teammate) or changes to 2 teams(prob 1/2: either of the singleplayer teams gets the red X). The overall probability is 1/6 of changing to a membership of (2,2) and 1/3 of becoming (3,1); the former if the two marked papers go to the two 1member teams and the latter if one of these team players gets the X and a member of the 2member team gets the star.
Since the probability of remaining (2,1,1) is 1/2, the expected number of rounds to proceed to one of the 2team states is 2, bringing the total expected rounds to 3 so far.
Call the expected number of rounds from (3,1), L and from (2,2), E (lopsided and even).
From the (3,1) state, the probability of going to (4), that is, the end state, is 1/4. The probability of remaining in the (3,1) state is (3/4)*(2/3)=6/12=1/2. The probability of going to the (2,2) state is (3/4)*(1/3)=3/12=1/4.
So from the (3,1) state, the expected remaining length,
L = 1/4 * 1 + 1/2 * (1+L) + 1/4 * (1+E).
Similarly, from the (2,2) state the expected remaining length of the game is,
E = 1 + (1/3) * E + (2/3) * L  the 1 being combined 1/3 * 1 + 2/3 * 1
or
2/3 * E = 1 + (2/3) * L
or
E = 3/2 + L
Substituting int he previous equation:
L = 1/4 * 1 + 1/2 * (1+L) + 1/4 * (1+3/2 + L)
= 1/4 + 1/2 + 1/4 * 5/2 + L/2 + L/4
L/4 = 11/8
L = 11/2
E = 14/2 = 7
Remember that in the transition from 3 teams to 2, the state (3,1) is twice as likely as to (2,2) so the overall added rounds is
(2/3)*L + (1/3)*E = 11/3 + 14/6 = 6
and the expected length of the game is 3 + 6 = 9 rounds.
Simulation verification:
DEFDBL AZ
RANDOMIZE TIMER
n = 4
DO
tr = tr + 1
REDIM team(n)
FOR i = 1 TO n: team(i) = i: NEXT
DO
r1 = INT(n * RND(1) + 1)
DO
r2 = INT(n * RND(1) + 1)
LOOP UNTIL r2 <> r1
team(r2) = team(r1)
drawct = drawct + 1
done = 1
FOR i = 1 TO n  1
IF team(i) <> team(i + 1) THEN done = 0
NEXT
LOOP UNTIL done
PRINT tr, drawct / tr
LOOP
finds an average of 9.003221150570205 rounds after 161433 trials, when manually stopped.
Part 2:
Substituting other values of n, as in
DEFDBL AZ
RANDOMIZE TIMER
n = 5
FOR tr = 1 TO 200000
REDIM team(n)
FOR i = 1 TO n: team(i) = i: NEXT
DO
r1 = INT(n * RND(1) + 1)
DO
r2 = INT(n * RND(1) + 1)
LOOP UNTIL r2 <> r1
team(r2) = team(r1)
drawct = drawct + 1
done = 1
FOR i = 1 TO n  1
IF team(i) <> team(i + 1) THEN done = 0
NEXT
LOOP UNTIL done
PRINT tr, drawct / tr
NEXT
finds 16.05239 for n=5 after 200,000 iterations.
n=6 yields 24.962935 and n=7 yields 35.97036 trials on average.
It appears that the expected number of rounds is (n1)^2.

Posted by Charlie
on 20140228 17:22:44 