0

This is question 3 of the Marcov chain chapter of Introduction to Probability models by Ross (12th edition).

There are k players, with player i having value $v_i > 0, i=1,...,k$. In every period, two of the players play a game, while the other k−2 wait in an ordered line. The loser of a game joins the end of the line, and the winner then plays a new game against the player who is first in line. Whenever i and j play, i wins with probability $\frac{v_i}{v_i + v_j}$.

(a) Define a Markov chain that is useful in analyzing this model.
(b) How many states does the Markov chain have?
(c) Give the transition probabilities of the chain.

I'm having a hard time figuring it out how to make a Markov chain out of this problem. Like, should we assume who plays against who first? Also, how does this game end? Any hint how to start this problem would be really appreciated.

Thanks.

Ram Zi
  • 67
  • 3
    You don't need to specify who starts and how the game ends to define the Markov chain. Just specify the states and the transitions between them. – Misha Lavrov Nov 12 '21 at 16:15
  • Thanks @MishaLavrov. Can we define the states as the next person who will be up for the game? For example, if players 1 and 2 are playing, Then one of them will win and play with player 3 and the other one will go to the end of the line. And the probability of going from either of them to 3 will be based on what question gives us? – Ram Zi Nov 12 '21 at 19:41
  • Just 3 players might not be enough for you to understand what's up with this problem. Think about how the rounds might go for, say, $k=4$. – Misha Lavrov Nov 12 '21 at 19:54
  • Well, if my state is the next player who will join the game, and we start with players 1 and 2, let's say player 1 wins. Then player 1 will play against player 3, and player 2 will to the back of the line behind 4. (It can go either way, either 1 wins or 2 wins). Then, if player 3 wins now, 3 will play against 4 and player 1 will go to the end of the line. and so on. But, here, I don't see a difference between 3 or 4 players. So, I think I'm missing your point! – Ram Zi Nov 12 '21 at 20:07
  • Remember, for a Markov chain, you have to be able to predict the next state based only on the current state. If the current state (after many rounds) is, for example, that player 2 is playing against player 4, can you say what the next state will be if player 2 wins? – Misha Lavrov Nov 12 '21 at 20:23
  • Taking different paths, it can be either 1 or 3. So, we won't be sure which one since it will be based on previous games and not just the current game. So, are you saying I cannot define my state as the next player who joins the game? Right? So, what can I use as my states then? – Ram Zi Nov 12 '21 at 20:32
  • Can I solve it like a list model? But states will be (k choose 2) Unique combinations of each 2 players. Does that work? – Ram Zi Nov 12 '21 at 22:22
  • I don't want to tell you if it works or not :) I've already told you how to check if it works! – Misha Lavrov Nov 12 '21 at 23:19

0 Answers0