Under the first rule whoever reaches 11 will win the game:
There are only 8 possible intermediate and final outcomes given that Keathong and Edison are 9-All as shown by the nodes in the diagraph. The scores are given as Edison's Score and Keat Hong's Score. The set of these possible scores are called the State Space of thes Markov Chain.
Assume that each point scored is independent of the previous result, the possibility of Edison scores is p, and for Keathong is q. p+q=1. This is the primary assumption of a Markov chain: since Edison and Keat Hong are well-trained Ping Pong Masters, their performance is independent of how much they have already scored. Otherwise, we cannot call it a Markov Chain.
Hence, the probability of getting from 9-ALL to (10, 9) is p, to (9,10) is q. From 10,9 the chances of getting to 11-9 is p and to 10-ALL is q, similarly for rest of the digraph.
Note that there are two routes to get to 10-ALL: one is when Edison wins the first point and Keat Hong wins the second point, the other one is when Keat Hong wins the first point and Edison wins the second point.
We say two states, I & j, belong to the same equivalent class if we can find routes in the diagraph communicating between them. As we can see from the graph, there are no two states having a dipath communicating back and forth. All the arcs are pointing downwards. Hence, each state is a class on its own!
We say a class is open if once we go out of the state, we cannot find a way back in. Only 2 outgoing arcs are incident on 9-ALL, therefore it is an open class. Even though there are arcs coming into the states (10,9) and (9,10), these two arcs are coming from 9-ALL which is an open class. Therefore we also can't find a route back once we leave 10-9 and 9-10. These two states are open class as well! Same logic applies to 10-10, the two arcs going into 10-ALL are from two separate open classes. It is an open class as well.
We say a class is close if once we go into the state, we cannot find a way out. Since there are only incoming arcs to these 4 states, each state is a close class.
Starting at 9-ALL, what's the probability of the game ending up in each of these final scores? Technically, we call these probability the absorption from 9-ALL to each of the closed classes. A(9-ALL), (11,9) is the probability of the game ends at 11-9 given we start at 9-ALL. Since the states are independent, we can just multiply the possibility along the path. From 9-ALL to 11-9, there is only one possible paths. The possibility of ending up in 11-9 is p*p=p^2. There are 2 routes to get into 11-10, the possibility of the first route is p*q*p and the second is q*p*p. Hence the possibility of getting into 11-10 is 2qp^2. Same logic applies to the other 2 scores: 10-11 is 2pq^2 and 9-11 is q^2. Since these are the only 4 possible results, the sum of the probabilities should be one.
Note that the game will finish in maximum 3 steps once we reach 9-ALL.
Under the second rule each of them must lead by two:
There are infinite possible intermediate outcomes if Keat Hong and Edison always reach a tie. Our previous approach is not the most efficient way to calculate the probability. However, we can analyze the problem from a different angle. Instead of looking at the possible scores, we can classify the state by how much Edison lead. Hence the states are {-2, -1, 0, 1, 2}. Keat Hong will win if the process reaches -2. And Edison will win if he leads 2.
This is called a gambler's ruin problem. We can imagine Keat Hong and Edison as two stubborn gamblers. They bet on the score difference. Each of them has 2 cents to gamble. One dollar for each time a point is scored. They will only stop until one of them goes bankrupt. The Edison's wealth change is equivalent to the score difference. Initially both of them have 2 cents so they are at tie right now. Each time a point is scored, Edison's wealth either decreases by one or increases by one. If Keat Hong wins a point, Edison has to give Keat Hong a cent. From Edison's point of view, his wealth decreases by one. If he loses again, he will go bankrupt, Keat Hong wins the game. If he wins the next point, Keat Hong gives Edison a cent. Then Edison's wealth goes back to 2, they reach a tie again. The game goes on and on until one of them leads 2.
Let K denotes the total wealth of Keat Hong and Edison which is 4.
Let I denotes the initial wealth of Edison which is 2.
The probability of Edison scores a point is p and q for keat Hong.
As the last example, assuming their performance is not affected by how much they have already scored:
Probability of Edison wins = i/k if p=q=0.5
Or 1-(q/p)^i/1-(p/p)^k if p and q are different.
Loading...
3:07
SpongeBob- Poisson Processby kkkk112562 views
Link to this comment:
All Comments (0)