Probability of reaching a condition

Difficulty
Average 50%

Probability of reaching a condition

The probability of reaching a state and by extension the time to reaching a state refers to the number of times before reaching a state in the Markov chain.

(Xnot)not means a markov chain homogeneous of finite or countable state space X of transition matrix Q: we can interpret Xnot as modeling the state of a system at time n.

The initial chain law (Xnot) having been fixed, only the states likely to be reached intervene in the study of the evolution of the chain. We put XTo = {x ∈ X, there exists n ≥ 0, P (Xnot = x)> 0}.

For a state e ∈ XTo, we will denote by T(not)e the time it takes for the chain to reach state e strictly after time n:

  • T(not)e therefore denote the smallest integer k> 0 such that Xn + k = e if the chain passes through e after time n
  • T(not)e = + ∞ if the chain does not pass through the state e after time n.
  • To simplify the notations T(0)e will also be denoted simply Te.

Let i, e ∈ XTo.

  • For all n ∈ N and k ∈ N , the probability of reaching state e at time n + k for the first time after time n knowing that Xnot = i does not depend on n, we will denote it fie(k) = P (T(not)e = k | Xnot = i). It satisfies the following equation: fie(1) = Q (i, e) and fie(k) = ∑j∈X \ {e} Q (i, j) fI(k - 1) for all k ≥ 2.

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

  • The probability of reaching a state e after time n, knowing that Xnot = i does not depend on n, we will denote it fie : fie = P (T(not)e <+ ∞ | Xnot = i). She checks: fie = Q (ie) + ∑j∈X \ {e} Q (i, j) fI.

The equation for fie reflects the fact that the chain reaches e from a state i either directly, or passes from state i to a state j ≠ e then reaches e from state j.

Note that fie= 1 if and only if fI= 1 for any state j ≠ e such that Q (i, j)> 0.

When the string is ergodic, it is possible to calculate the time to return to a state by calculating the inverse of the stationary probability. For that it is necessary that all the states are positive recurrent, that is to say that its expectation is positive and not infinite:

probability of reaching a state

Example of probability of reaching a state

In order to show how to calculate the probability of reaching a state, we will take the following example.

Suppose the player has 1 euro and plays a game of chance where the stake is 1 euro until he has reached the sum of 3 euro or until he is ruined.

Recall that p denotes 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 af0,3 = 0 since the player cannot play if he has no money initially (0 is an absorbing state). It remains to write the equation for f2,3 which is the probability that a player manages to get 3 euros if he initially has 2 euros. We get: 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}.

This system has only one solution which is f2,3 = p / (1 − p (1 − p) and f1,3 = p² / 1 − p (1 − p).

In particular, if the game is fair, i.e. if p = 1/2, we have1,3 = 1/3 which means that if the player initially has 1 euro, he has a one in three chance of getting 3 euros. The probability that the game will stop 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 by solving the obtained system. This calculation shows that f1,0 + f1,3 = 1, which means that the player necessarily stops at the end of a finite number of games, either because he has managed to obtain 3 euros, or because he is ruined.

Average time to reach from a configuration

In addition to the probability of reaching a state, it is possible to calculate the average time to reach this state.

The mean time to reach is the smallest positive solution in the system:

probability of reaching a state

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 of average time to reach

Here the probability of reaching a state is not calculated. In fact, the probability of reaching a state and the average time to reaching states must be studied together.

A chip jumps over a triangle, with a probability 2/3 clockwise, and 1/3 counterclockwise.

  • The vertices are numbered: 1,2,3.
  • Let's take a look at the hit times. We start from summit 1. We have
    for i = 1: x1=0
  • For i = 2, 3, we have to solve the following systems:
    • x2= 1 + 1/3 x1 + 0 x2+ 2/3 x3
    • x3= 1 + 2 / 3x1+ 1/3 x2+ 0 x3

Which gives for solution the vector (0, 15/7, 12/7)