At the start of the game, let Z be the random variable representing the number of moves required for Max to complete this game. What is the value of E[Z] and why?

Question

The game starts with 6 empty glasses on the table, labeled m1,m2,m3,m4,m5,m6.Max has to make "moves" to play this game.Each move is:"Select a glass at random (probability of selecting each glass is equal). If the selected glass is empty, then fill it up with juice. If selected glass is already filled with juice, then drink it completely to make it empty again". The game ends when all the 6 glasses are filled with juice at the same time (Max will drink all 6 glasses of juice to make them empty again, and the game ends there).

Answer 1

Remember: E[Z] = ∑ P(Z=z)*z

Note that "picking glasses until you're done" follows a geometric distribution, and you can use the memoryless property once you get back to the original state. More on this later.

Consider a couple of easier versions of this problem:

i) There's only two glasses: A and B.

E[Z] = P(The next two moves finish the game: A then B, or B then A)*2

+P(Picked the same glass twice: AA, or BB) * (2+E[Z]) -----------------> I can multiply by (2+E[Z]) because of the memoryless property, since picking the same glass twice is like restarting the game.

Now Solve:

E[Z] = (.5)*2+(.5)*(2+E[Z])

E[Z] = 1 + 1 +(.5)*E[Z]

E[Z] = 4.

ii) There's 3 glasses: A, B, C

Consider the game state after moving 3 times from the start. Either (I) the game is over, or (II) there is 1 full glass and two empty glasses.

Consider the game state after moving twice from situation (II). Either the game is over, or the game is back to situation (II)

Let x=P(finishing the game in 3 moves).

Let y =P(finishing the game in 2 moves, given the game is in situation (II) )

Let W = the expected number of additional moves, given the game is in situation (II)

E[Z] = 3*x + (1-x)*(E[W])

E[W] = y*2 +(1-y)*(2+E[W])

Solving this all out:

x = 6/27

y = 2/9

E[W] = 9

E[Z] = 23/3.

Follow the pattern of generalizing game states and using the memoryless property for the actual question.