Markov Chain

From http://mason.gmu.edu/~scannon/MarkovChain/example.html

Example of a Markov chain Model

Consider a shooting game where the shooter is shooting at a target and the results can either be a hit or a miss.

Suppose that the shooting rule has the following form:

- If the shooter hits at one time, the probability that he/she will hit on the next shoot is 0.75
- If the shooter misses at any shoot, the probability that he/she will miss on the next shoot is 0.65

This statements defined conditional probability and they are Markovian in character because the state of any (n+1)shoot only depend on the state of the (n) shoot.

Now let p(n) be the probability that the nth shoot is a hit.
Let q(n) be the probability that the nth shoot is a miss.
Since the sum of the probabilities must equal to 1 we get

p(n) = 1 - q(n) and q(n) = 1- p(n)

From the problem statement we know that:
- If the shooter hit at the nth shoot, then

p(n+1) = 0.75 75% chance to hit at the (n+1) shoot

q(n+1) = 0.25 25% chance to miss at the (n+1) shoot

- If the shooter misses at the nth shoot, then:

p(n+1) = 0.35 35% chance to hit at the (n+1) shout

q(n+1) = 0.65 65% chance to miss at the (n+1) shoot

So the probability that the shooter will hit at any (n+1) shoot is

- p(n+1) = 0.75p(n) + 0.35q(n)

Since q(n) = 1- p(n) then

p(n+1) = 0.75p(n) + 0.35(1-p(n)) = 0.40p(n) + 0.35

The dynamical system equation for this model is

P(n+1) = 0.40p(n) + 0.35

Tree diagram for the Markov chain:

/ hit (0.75*0.75)
/
0.75
/
/
hit
/ / / 0.75 0.25
/ \ miss (0.75*0.25)
/
/
hit \ / hit (0.25*0.35)
0.25 0.35
\ /
\ /
\ /
miss
0.65
\miss (0.25*0.65)

For our example assume that the first shoot (n = 0) was a hit(p(0) = 1)
the following tree diagram shows the probabilities of hitting and missing at (n+1) and (n+2)

This tree diagram show how we can get the probability of hitting or missing on the (n = 2) shoot assuming that the shooter hits on the initial shout (n = 0).

Since we know that he/she hit on the initial shoot then the probability that the next shoot (n = 1) will be a hit is p(1)= 0.75 and the probability that it will be a miss is q(1) = 0.25.

Now if he/she hit at (n = 1) then:

p(2) = 0.75 75% chance to hit at the (n = 2) shoot
q(2) = 0.25 25% chance to miss at the (n = 2) shoot

If he/she miss at (n = 1) then:

p(2) = 0.35 35% chance to hit at the (n = 2) shoot
q(2) = 0.65 65% chance to miss at the (n = 2) shoot

If we only know that the initial shoot was a hit and we do not know if the second shoot was a hit or a miss, we can still calculate the probability of a hit or a miss in the (n = 3) shoot.

p(2) = 0.75 p(1) + 0.35q(1)

Because the initial shoot was a hit then p(1) = 0.75 and q(1) = 0.25

So p(2) = 0.75 * 0.75 + 0.35 * 0.25
p(2) = 0.65

Solving For the long term probability.

In our model we found that p(n+1) = 0.40p(n) + 0.35

This is a first order affine dynamical system equation.
The equilibrium value is p = (0.35/(1 - 0.40)) = 0.58

Furthermore this equilibrium is a stable since the coefficient of p(n) in the general solution is less than 1.

So the general solution is

p(k) = c(0.40)^k + 0.58

Where the constant c depend on the initial probability.

Lets consider different values for the initial probabilities and see if the system will go to the equilibrium value (0.58) that we calculated and said that it is stable.

Let the probability that the shooter will hit at (n = 0) = p0

Then p(0) = c(0.4)^0 + 0.58

p(0) = c + 0.58 = p0
==> c = p0 - 0.58

and p(k) = (p0 - 0.58) * (0.40)^k + 0.58

We will try three different values of p0 ( p0 > 0.58 , p0 = 0.58 , and p0 < 0.58)

(1) p0 = 0.70
p(k) = 0.12 (0.40)^k + 0.58

(2) p0 = 0.58
p(k) = 0.58

(3) p0 = 0.50
p(k) = - 0.08(0.40)^k + 0.58

On the second case where p(k) = 0.58 the conversion of the system to the equilibrium value is clear. For the other two values the tables, and the graphs bellow shows the conversion of the system.

Initial value p0 = 0.70 Initial value p0 = 0.50
n = p(n) p(n)
0 0.7 0.5
1 0.628 0.26
2 0.5992 0.452
3 0.5877 0.5288
4 0.5831 0.55952
5 0.5812 0.571808
6 0.5805 0.576723
7 0.5802 0.578689
8 0.5801 0.579476
9 0.58 0.57979
10 0.58 0.579916
11 0.58 0.579966
12 0.58 0.579987
13 0.58 0.579995
14 0.58 0.579998
15 0.58 0.579999
16 0.58 0.58
17 0.58 0.58
18 0.58 0.58
19 0.58 0.58
20 0.58 0.58

From the table above we see that the long range probability does not depend on the initial value.

Here is a hit and miss chart showing how a person would actually do and how it compares to our theoretical overall accuracy.