In this discussion we’re going to look at
a single game of tennis being played by two people, the server and the other person not
serving. In tennis usually the server has an advantage, at least if that person has
a good serve. p is the probability the server wins any given point and q which is 1-p is
the probability the other player wins, and generally if the two players are relatively
equal in ability p will be higher than q because of the advantage the server has. Here are
all the different scores that can occur in this tennis game between the server and the
non server. Let’s track one possible scenario. Let’s say that on the first point the server
wins it to go up 15-0. Then the server wins another point to be up 30-0. Then the non
server wins a point so it’s 30-15. Then the server wins again to go up 40-15. Then the
server loses the next point so he’s still a point ahead so it’s server’s advantage.
And let’s say the non server wins the next point so it goes to deuce. Then the server
wins a point so it goes back to server’s advantage. Then the server wins again so the server is
2 points ahead and wins the game, and that’s an absorbing state, the server has won the
game. The game starts out of course with the score being 0-0. Now after the first point
is played, either the server will have won that point so the server will be ahead 15-0,
or the non server will have won the point, so the non server will be ahead 15-0. And
those probabilities are p and q. After another point has been played, the score will be one
of the scores shown here. If the server was up 15-0 after the first point, and he wins
another point to go to 30-0. If he loses the next point it goes to 15 all. Fill in the
probabilities of those 2 transitions. If the non server wins at 15-0, then server wins
and it goes to 15 all, non server wins again and it goes 30-0. So what are the possible
scores after another point is played? They’re the ones that are showing here. Let’s see
how we get there if the server is up 30-0 and wins another point it goes to 40-0. If
the server loses the next point then it goes to 30-15. From the state where it’s tied at
15 all, if the server wins then the server goes up 30-15, if the non server wins then
the non server goes up 30-15. And from the state where the non server is up 30-0, it
either goes to non server up 30-15 or non server up 40-0. What are the possible scores
after another point has been played? From the case where the server is ahead 40-0, if
the server wins another point he has won the game. If he loses the point it goes to 40-15.
So let’s fill in those 2 transitions. Probability p and q. From the case where server is up
30-15 if he wins the next point it’s 40-15, if he loses it goes to 30-30 which is deuce.
That’s what you call it in tennis when the score is tied and any player to win the game
needs to get 2 points ahead. From the case where the non server is ahead 30-15, it can
go to deuce if the server wins the point or to 40-14 if the non server wins. And from
this final case of 40-0 it can go to 40-15 if the server wins or to game over, non server
winning if the non server wins another point. So we have already hit the two absorbing states.
S winning or N winning means game over. Those are the 2 absorbing states. The server wins
the game or the non server wins the game. Any game is going to wind up one of those
two things happening. Now the states that haven’t appeared yet are the states where
it’s somebody’s advantage. And we’re now showing those. Server’s advantage means if server
wins the next point server has won the game. If server loses it goes back to deuce. And
similarly when non server has advantage. So the transition probabilities that are missing
are server’s advantage and server wins with game over. Server’s advantage and server loses
it goes back to deuce. Non server’s advantage and non server wins it goes to game over.
Server wins it goes back to deuce. From server being ahead 40-15 if server loses it goes
to server’s advantage. Because server is still a point ahead. If server wins it means game
over. From non server ahead 40-15 if nonserver wins it’s game over. If non serve loses then
non server is still a point ahead so it goes to non server’s advantage. Let’s see we need
a q right here. And we still need to fill in the probabilities, the one from deuce if
server wins it goes server’s advantage and if non server wins it goes to non server’s
advantage. So I think that’s all the probabilities now filled in. We have the two black boxes
representing the 2 absorbing states. The game will end when somebody wins. Let’s catalog
the nonabsorbing states, 0-0 where we started is of course nonabsorbing. And after 1 point
has been played somebody will be ahead 15-0. After two points have been played somebody
will be ahead 30-0 or else it will be tied. After 3 points have been played we’ll be at
one of these places. Then after 4 points we might be here or here. Now every nonabsorbing
state I’ve circled so far is a state we can enter only once but the remaining ones, deuce,
server’s advantage, and non server’s advantage, are states where you can cycle through them
any number of times. But in any case along with our 2 absorbing states we have 15 nonabsorbing
states. So altogether that’s 17 states. So we’re looking at a 17-state Markov chain.
So our transition matrix would be a 17×17 matrix. The transition matrix will be 17×17
matrix, let’s remember the pattern. Remember we know we have 2 absorbing states. So that
means since we always list our absorbing states first, the first row will be a 1 followed
by zeroes. The 2nd row will look like this. And because we have 2 absorbing states, we
slice off the first 2 columns and the first 2 rows. We name this piece R. And this piece
Q. So Q will be 15×15. And the primary computation we have to do is, we take the identity matrix
the same size as Q, subtract off Q, find the inverse of that, and that’s what’s called
N. That’s a very important matrix that gives us a lot of information. And the other computation,
for the probability of entering the 2 absorbing states, is B=NR, so in this case that would
be multiplying a 15 by 15 matrix times a 15 row, 2 column matrix. So B would be a 15 by
2 matrix itself. But the point is if we do those two matrix computations, then we can
answer pretty much any question we are asked about this absorbing Markov chain. And the
matrix tool does this computation rather nicely. That sounds like a lot of work since Q is
15 by 15. That means it has 225 entries. But 80 to 90% of them are zeroes. So the easy
way to enter this matrix is just to type out a row of 15 zeroes and then copy and paste
that 15 times to give you a matrix full of zeroes and then simply change the few entries
that need to be something else. So you don’t have much editing to do, to change that into
the matrix that you want to enter into the matrix tool. Here are examples of questions
that would be of interest to solve. You need values for p and q. But once you have numerical
values, what are the chances that the server will win the game? You can do that calculation
based on those matrices. Expected value for number of points played? On average how long
will the game go? How many times will the score be tied at deuce? These are the kinds
of things you can get out of those two matrices we were just talking about. The matrix N and
the matrix B.

Tagged : # # # # # # # #

Dennis Veasley

3 thoughts on “Tracking a tennis game – a 17-state Markov Chain”

  1. Wow. So much wrong with this. Firstly, it's said "fifteen-love" not "fifteen-zero". Also, deuce is 40-40 as anyone who's ever seen or played a game knows. From 40-15 up, if a player loses it goes to 40-30. Then they can either win the whole game or lose to go to deuce.

Leave a Reply

Your email address will not be published. Required fields are marked *