Create a transition table

Question

I am trying to create a transition table for a markov chain but I have difficulties. Consider a game, where each player (of two, lets call them A and B) has a fixed given probability of scoring 3 points, scoring 5 points and scoring 7 points. The probabilies for each player are called p3A,p5A,p7A and p3B,p5B,p7B and finally the probability of zero points for both of them is pZero. This game has 80 rounds. At the end of 1st round, the score difference will be: +3, +5, +7 , -3, -5, -7, 0 (score difference is defined as score A - Score B). Only one player or no player can score in each round. There is no possibility of both players scoring at the same round. Lets call score difference at round R, D :

dif(R,D)

apparently :

dif(1,0)=pZero
dif(1,3)=p3A
dif(1,5)=p5A
dif(1,7)=p7A
dif(1,-3)=p3B
dif(1,-5)=p5B
dif(1,-7)=p7B

dif(1,x)=0 for every other x

so at round 2:

dif(2,14)=dif(1,7)*p7A
dif(2,13)=dif(1,6)*p7A + dif(1,8)*p5A + dif(1,10)*p3A + dif(1,13)*pZero + dif(1,16)*p3B + dif(1,18)*p5B + dif(1,20)*p7B = 0*p7A + 0*.....=0

and so on.

You can tell the pattern, it could easily be rewritten as recursive function. What I want though is to ind the transition table. Apparently at the end of game, at round 80, you can have a difference that varies from +560 to -560.

All examples I have found offer my examples for simple random walks, but not something that complex. I cannot figure out which the states are, and how to generate transition table. Any ideas?Thank you in advance.

Answer 1

The usual way to model a random walk like this as a Markov chain uses an uncountably infinite state space, namely $\mathbb Z$. The transition probabilities would be $$p_{i,i+7}=p_{7A}, p_{i,i+5}=p_{5A}, \dots, p_{i,i-5}=p_{5B}, p_{i,i-7}=p_{7B},$$ with all others zero. Since the state space isn’t finite, there’s no transition matrix. If you limit the number of steps, you could conceivably create a transition matrix (taking care to make sure that the effects of the edges were correct), but I’m not sure that’s going to simplify your computations since this matrix would be quite large. It is mostly empty, with the probabilities running down a few diagonals around the main diagonal, so perhaps you could take advantage of that to simplify computing powers of this matrix.

I have a feeling that a more fruitful approach to solving your problem—compute the probability that player A wins after $n$ rounds—would be to examine the returns to zero of this walk. The last return is the important one, so if you can figure out the probability of that occurring at round $k$, you can sum over the number of rounds and multiply by $P(X_i>0)=p_{A3}+p_{A5}+p_{A7}$.