Mean recurrent time

(Xn)n denotes a homogeneous Markov chain of finite or countable states with its transition matrix Q:  Xn models the state of a system at time n.

The initial law of the chain (Xn) having been fixed, only the linked states intervene in the study of the evolution of the chain: Xa = {x ∈ X, there exists n ≥ 0, P(Xn = x) > 0}.

For a state e ∈ Xa, we denote by T(n)e the time it takes the chain to reach the state e strictly after the instant n:

  • T(n)e denotes the smallest integer k> 0 such that Xn+k = e if the chain goes through e after the instant n
  • T(n)e = +∞ if the chain does not go through state e after moment n.

Let’s i, e ∈ Xa.

  • For all n ∈ N and k ∈ N, the probability of reaching the state e at the instant n + k for the first time after the instant n knowing that Xn = i does not depend on n, we note fi,e(k) = P(T(n)e = k|Xn = i). It satisfies the following equation: fi,e(1) = Q(i, e) and fi,e(k) = ∑j∈X\{e} Q(i, j)fj,e(k − 1) for all k ≥ 2.

The equation for fi,e(k) simply translates the fact that to arrive for the first time in the state e in k steps, starting from the state i, it is necessary to go from the state i to a state j ≠ e, then starting from j, arrive for the first time in e in k – 1 step.

  • The probability of reaching state e after time n, knowing that Xn = i does not depend on n, we denote it fi,e : fi,e = P(T(n)e < +∞|Xn = i). It verifies: fi,e = Q(i e) + ∑j∈X\{e} Q(i,j)fj,e.

The equation for fi,e reflects the fact that the chain reached from a state i either directly or goes from state i to a state j ≠ e then reached e from state j.

Note that fi,e=1 if and only if fj,e=1 for all states j ≠ e such that Q(i, j)> 0.

When the chain is ergodic, it is possible to calculate the return time in a state by calculating the inverse of the stationary probability. For this it is necessary that all the states are a positive recurrence, that is to say that its expected value is positive and not infinite:

markov3

Example

Suppose that a player has 1 euro and plays a game of chance where the bet is 1 euro until he has reached the sum of 3 euros or until it is ruined. Remind that p is the probability that he wins a game and therefore wins 1 euro and 1-p is the probability that he loses the game and therefore loses 1 euro.

We are looking for the probability that he will thus succeed in having 3 euros, that is to say f1,3. The equation with i = 1 and e = 3 is written f1,3 = pf2,3 + (1 − p)f0,3. We have f0,3 = 0 since the player can not play if he does not have money initially (0 is an absorbing state). It remains to write the equation for f2,3 which is the probability that a player gets to get 3 euros if he initially has 2 euros. We obtain: f2,3 = 1 − p + (1 − p)f1,3. We therefore have to solve a system of 2 equations with 2 unknowns: {f1,3 = pf2,3; f2,3 = p + (1 − p)f1,3}.

The unique solution is: f2,3 =p/(1−p(1−p) and f1,3 =p²/1−p(1−p).

In particular, if the game is fair, ie if p = 1/2, we have f1,3 = 1/3 which means that if the player initially has 1 euro, he has one chance out of three d ‘get to get 3 euros. The probability that the game stops because the player is ruined is calculated in a similar way by writing the equations satisfied by f1,0, f2,0 and f3,0 and solving the system obtained. This calculation makes it possible to see that f1,0 + f1,3 = 1, which means that the player necessarily stops after a finite number of games either because he managed to obtain 3 euros, or because he is ruined.

Time to reach a class / state

This time is the smallest positive solution of the system:

markov4

where the absorbent class designates the states in which the system begins. Indeed, since we start from these states, the average time to reach them is 0 movement.

Example

A flea jumps on a triangle, with a probability 2/3 clockwise, and 1/3 counterclockwise.

  • Let’s call the vertices: 1,2,3.
  • Let’s look at reaching times. We start from the vertex 1. We have i = 1 : x1=0
  • For i = 2, 3, we have to solve the following system:
    • x2=1+ 1/3 x1 + 0 x2+ 2/3 x3
    • x3=1+ 2/3x1+ 1/3 x2+ 0 x3

The solution is (0, 15/7, 12/7)

Publicités