Contenus

Toggle## 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.

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

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

For a state e ∈ X_{To}, 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 X_{n + 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 T_{e}.

Let i, e ∈ X_{To}.

- 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 X_{not}= i does not depend on n, we will denote it f_{ie}(k) = P (T^{(not)}_{e}= k | X_{not}= i). It satisfies the following equation: f_{ie}(1) = Q (i, e) and f_{ie}(k) = ∑_{j∈X \ {e}}Q (i, j) f_{I}(k - 1) for all k ≥ 2.

The equation for f_{ie}(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 X
_{not}= i does not depend on n, we will denote it f_{ie}: f_{ie}= P (T^{(not)}_{e}<+ ∞ | X_{not}= i). She checks: f_{ie}= Q (ie) + ∑_{j∈X \ {e}}Q (i, j) f_{I}.

The equation for f_{ie} 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 f_{ie}= 1 if and only if f_{I}= 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:

## 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 f_{1,3}. The equation with i = 1 and e = 3 is written f_{1,3} = pf_{2,3} + (1 - p) f_{0,3}. We af_{0,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 f_{2,3} which is the probability that a player manages to get 3 euros if he initially has 2 euros. We get: f_{2,3} = 1 - p + (1 - p) f_{1,3}. We therefore have to solve a system of 2 equations with 2 unknowns: {f_{1,3} = pf_{2,3}; f_{2,3} = p + (1 - p) f_{1,3}}.

This system has only one solution which is f_{2,3} = p / (1 − p (1 − p) and f_{1,3} = p² / 1 − p (1 − p).

In particular, if the game is fair, i.e. if p = 1/2, we have_{1,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 f_{1,0}, f_{2,0} and F_{3,0} and by solving the obtained system. This calculation shows that f_{1,0} + f_{1,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

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

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

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: x_{1}=0 - For i = 2, 3, we have to solve the following systems:
- x
_{2}= 1 + 1/3 x_{1}+ 0 x_{2}+ 2/3 x_{3} - x
_{3}= 1 + 2 / 3x_{1}+ 1/3 x_{2}+ 0 x_{3}

- x

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