Question

A flea moves around the vertices of a triangle in the following manner: Whenever it is at vertex \(i\) it moves to its clockwise neighbor vertex with probability \(p_{i}\) and to the counterclockwise neighbor with probability \(q_{i}=1-p_{i}, i=1,2,3\). (a) Find the proportion of time that the flea is at each of the vertices. (b) How often does the flea make a counterclockwise move that is then followed by five consecutive clockwise moves?

Short answer

In the long-term, the proportion of time the flea is at each of the vertices is given by: \[\pi_1 = \frac{q_2 p_3}{D}, \quad \pi_2 = \frac{p_1 q_3}{D}, \quad \pi_3 = \frac{q_1 p_2}{D},\] where \(D = q_2 p_3 + p_1 q_3 + q_1 p_2\). The frequency of a counterclockwise move followed by five consecutive clockwise moves is given by: \[\text{Frequency} = \pi_1(q_1 p_1^5) + \pi_2(q_2 p_2^5) + \pi_3(q_3 p_3^5)\]

Step-by-step solution

Define the Markov chain

Let \(X=\) {1, 2, 3} be the state space representing the vertices of the triangle. We can represent the given system as a Markov chain with 3 states, where \(X_n\) represents the position of the flea at time n. The given probability transition is then: $$P = \begin{pmatrix} 0 & p_1 & q_1\\ q_2 & 0 & p_2\\ p_3 & q_3 & 0 \end{pmatrix}$$

Find the stationary distribution

To find the proportion of time the flea is at each vertex, we need to find the stationary distribution of the Markov chain. A stationary distribution, denoted by \(\pi\), satisfies: $$\pi P = \pi$$ Writing the equations from this and using the constraint that the sum of probabilities is 1, we get: \begin{align*} \pi_1 &= \pi_2 q_2 + \pi_3 p_3 \\ \pi_2 &= \pi_1 p_1 + \pi_3 q_3 \\ \pi_3 &= \pi_1 q_1 + \pi_2 p_2 \\ \pi_1 + \pi_2 + \pi_3 &= 1 \end{align*}

Calculate the long-term proportions

Solving the system of linear equations above, we get the long-term proportion of time the flea is at each vertex as: $$\pi_1 = \frac{q_2 p_3}{D}, \quad \pi_2 = \frac{p_1 q_3}{D}, \quad \pi_3 = \frac{q_1 p_2}{D},$$ where \(D = q_2 p_3 + p_1 q_3 + q_1 p_2\).

Find the frequency of moves

To find the frequency of a counterclockwise move followed by 5 consecutive clockwise moves, we can use the long-term probabilities of the Markov chain. Let the flea be at vertex \(i\). The probability of it making a counterclockwise move is \(q_i\), and the probability of making five consecutive clockwise moves is \(p_i^5\). Therefore, the probability of the moves happening while at vertex \(i\) is \(q_i p_i^5\). To find the frequency of the given moves, we sum the probabilities over all vertices and multiply by the long-term proportions: $$\text{Frequency} = \pi_1(q_1 p_1^5) + \pi_2(q_2 p_2^5) + \pi_3(q_3 p_3^5)$$

Key concepts

Stationary Distribution

In Markov chain theory, the concept of a stationary distribution is pivotal in understanding the long-term behavior of a process. This distribution, typically represented by a vector denoted as \( \pi \), provides the probabilities that the process would be in a particular state after a large number of steps. If you imagine a flea hopping around the triangle's vertices, its location over an infinite amount of time reaches a stable distribution known as the stationary distribution.

For a stationary distribution to exist, it must satisfy a balance equation \( \pi P = \pi \), where \( P \) is the probability transition matrix of the Markov chain. This means the distribution doesn't change after one transition, marking a kind of equilibrium for the probabilities of the states. In our exercise, we determine the stationary distribution by solving linear equations derived from this balance, along with the condition that the sum of the probabilities in \( \pi \) must be 1. The solution represents the proportion of time the flea spends at each vertex in the long run.

Probability Transition Matrix

The probability transition matrix, an essential concept in Markov chain analysis, denotes the probabilities of moving from one state to another in one step. In our triangle-hopping flea example, the matrix \( P \) is defined with the elements representing the probability, say \( p_i \), of moving to a clockwise vertex, and \( q_i = 1 - p_i \), of moving to a counterclockwise vertex from vertex \(i\).

Each row of the transition matrix must sum up to 1 since the probabilities of moving to any other state must account for all possible scenarios. The matrix form makes it convenient to perform calculations, specifically when determining the stationary distribution. By defining the probabilities in such an organized structure, the exercise simplifies the complex behavior of the flea's movement into an algebraic problem.

State Space

The state space of a Markov chain represents all possible states in which the process could be at any given time. Think of it as the 'universe' of possible positions or conditions the process, like our flea, can find itself in. For the triangle problem, the state space is \( X = \{1, 2, 3\} \), indicating the three vertices of the triangle.

Understanding the state space is critical because it lays out the structure upon which the probability transition matrix is constructed. In our case, a very small and discrete state space is presented, but Markov chains can handle vastly more complex and even continuous state spaces, which allows for a diverse range of real-world applications.

Long-term Proportions

Long-term proportions are about understanding the frequency of the process, such as our flea's hopping pattern, being in a specific state as time goes to infinity. It’s the eventual behavior if we were to observe the flea for a very long period.

In the provided exercise, after finding the stationary distribution, we use it to calculate the long-term proportions, which tell us the proportion of time the flea spends at each vertex. To go further, as asked in part (b) of the exercise, we can even determine the frequency of specific sequences of steps, like the counterclockwise move followed by five clockwise moves, which integrates our knowledge of long-term behavior (stationary distribution) with the specific rules of transition (probability transition matrix).