/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 38 Recall that state \(i\) is said ... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 4: Problem 38

Recall that state \(i\) is said to be positive recurrent if \(m_{i, i}<\infty\), where \(m_{i, i}\) is the expected number of transitions until the Markov chain, starting in state \(i\), makes a transition back into that state. Because \(\pi_{i}\), the long-run proportion of time the Markov chain, starting in state \(i\), spends in state \(i\), satisfies $$ \pi_{i}=\frac{1}{m_{i, i}} $$ it follows that state \(i\) is positive recurrent if and only if \(\pi_{i}>0\). Suppose that state \(i\) is positive recurrent and that state \(i\) communicates with state \(j .\) Show that state \(j\) is also positive recurrent by arguing that there is an integer \(n\) such that $$ \pi_{j} \geqslant \pi_{i} P_{i, j}^{n}>0 $$

Short Answer

Expert verified
Given that state i is positive recurrent and communicates with state j, we found an integer n where \(P_{i,j}^n > 0\). Then, we established a relationship between \(\pi_j\), \(\pi_i\), and \(P_{i,j}^n\) and showed that \(\pi_j \ge \pi_i P_{i,j}^n > 0\). Since \(\pi_j > 0\), it follows that state j is positive recurrent.

Step by step solution

01

Show that there exists an integer \(n\) such that \(P_{i,j}^n > 0\)

Since state i communicates with state j, there exists some integer n such that the probability of transitioning from state i to state j in n steps is greater than zero. In other words, there exists an integer n where \(P_{i,j}^n > 0\).
02

Express \(\pi_j\) in terms of \(\pi_i\) and \(P_{i,j}^n\)

Recall that the relationship between the long-run proportion of time spent in a state and the expected number of transitions until returning to that state is given by \(\pi_i = \frac{1}{m_{i,i}}\). Thus, we can rewrite the equation for state j as: \[\pi_{j} = \frac{1}{m_{j, j}}\] Because state i communicates with state j, we can write the expected number of transitions until returning to state j as the sum of the expected number of transitions from state j to state i, and the expected number of transitions until returning to state i after making the transition from state j: \[m_{j, j} = m_{j, i} + m_{i, i}\]
03

Find the lower bound for \(\pi_j\) using \(\pi_i\) and \(P_{i,j}^n\)

We can rewrite step 2 using \(\pi_i\) and \(\pi_j\): \[\frac{1}{\pi_j} = \frac{1}{\pi_i} + m_{j, i}\] Since we know that \(\pi_i > 0\), we can multiply both sides by \(\pi_i\): \[\frac{\pi_i}{\pi_j} = 1 + \pi_i m_{j, i}\] Rearrange the terms to get: \[\pi_j = \frac{\pi_i}{1 + \pi_i m_{j, i}}\] Since we know that there is an integer \(n\) such that \(P_{i,j}^n > 0\) (Step 1) and \(\pi_i > 0\), the right side of the inequality is positive: \[\pi_j \ge \pi_i P_{i,j}^n > 0\]
04

Given the inequality, conclude that state j is positive recurrent

From the inequality \(\pi_j \ge \pi_i P_{i,j}^n > 0\), we know that \(\pi_j > 0\). Since state j has a positive long-run proportion of time spent in it, state j is positive recurrent. In conclusion, if state i is positive recurrent and communicates with state j, then state j is also positive recurrent.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Positive Recurrent States
In the captivating world of Markov Chains, a state is termed as "positive recurrent" if it fulfills a specific criterion. Essentially, a state is positive recurrent when the expected number of transitions needed for the chain to return to that specific state, starting from itself, is finite. This is mathematically represented as \(m_{i, i} < \infty\). When a state is positive recurrent, it implies that the state has a positive long-run proportion of time that the Markov chain spends in that state. If a state \(i\) meets this condition, the long-run proportion of time, \(\pi_i\), is greater than zero: \(\pi_i > 0\). This concept is pivotal for understanding the long-term behavior and stability of certain states within a Markov chain. When analyzing Markov Chains, it's crucial to identify which states are positive recurrent, as they indicate states where the system will consistently return to over time.
Transition Probabilities
Transition probabilities are fundamental in Markov Chains, as they denote the likelihood of moving from one state to another in a defined number of steps or transitions. Suppose we are considering transitioning from state \(i\) to state \(j\). We express this as \(P_{i,j}\), which indicates the probability of this transition occurring. When states communicate, this means there is a path with non-zero probability that allows transitions between them in some sufficient number of steps. For example, if \(P_{i,j}^n > 0\) for some integer \(n\), it signifies there is a way to move from state \(i\) to state \(j\) in \(n\) steps. These probabilities help define the behavior and potential outcomes within a Markov process, modeling how likely it is to be in one state given a start in another.
Long-Run Proportion of Time
The long-run proportion of time spent in a state is a crucial measure in Markov Chains. It helps us understand how frequently or infrequently a particular state might appear as time approaches infinity. Denoted as \(\pi_i\) for state \(i\), this proportion is calculated as the reciprocal of \(m_{i,i}\), the expected number of steps to return to the state: \(\pi_i = \frac{1}{m_{i,i}}\). When this proportion is greater than 0 (\(\pi_i > 0\)), it implies that the state is positive recurrent, meaning the system will return to this state repeatedly over an extended period. This measure is pivotal for predicting the behavior of a system described by a Markov Chain, as it shows the balance of time spent across different states during its operation.
Communicating States
In the study of Markov Chains, communicating states are those states between which there exists a non-zero probability path, allowing transitions in both directions. When two states communicate, it means each can reach the other, potentially over several steps. This relationship is fundamental when considering the structure and behavior of Markov Chains, as it helps determine whether states are part of a larger interconnected set or isolated. For instance, if state \(i\) communicates with state \(j\), there exists some integer \(n\) for which \(P_{i,j}^n > 0\) and \(P_{j,i}^m > 0\) for some integer \(m\). Understanding these paths is essential for determining the recurrent nature of states and the overall ergodicity of the chain.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

A certain town never has two sunny days in a row. Each day is classified as being either sunny, cloudy (but dry), or rainy. If it is sunny one day, then it is equally likely to be either cloudy or rainy the next day. If it is rainy or cloudy one day, then there is one chance in two that it will be the same the next day, and if it changes then it is equally likely to be either of the other two possibilities. In the long run, what proportion of days are sunny? What proportion are cloudy?

It follows from Theorem \(4.2\) that for a time reversible Markov chain $$ P_{i j} P_{j k} P_{k i}=P_{i k} P_{k j} P_{j i}, \quad \text { for all } i, j, k $$ It turns out that if the state space is finite and \(P_{i j}>0\) for all \(i, j\), then the preceding is also a sufficient condition for time reversibility. (That is, in this case, we need only check Equation \((4.26)\) for paths from \(i\) to \(i\) that have only two intermediate states.) Prove this. Hint: Fix \(i\) and show that the equations $$ \pi_{j} P_{j k}=\pi_{k} P_{k j} $$ are satisfied by \(\pi_{j}=c P_{i j} / P_{j i}\), where \(c\) is chosen so that \(\sum_{j} \pi_{j}=1\)

A DNA nucleotide has any of four values. A standard model for a mutational change of the nucleotide at a specific location is a Markov chain model that supposes that in going from period to period the nucleotide does not change with probability \(1-3 \alpha\), and if it does change then it is equally likely to change to any of the other three values, for some \(0<\alpha<\frac{1}{3}\). (a) Show that \(P_{1,1}^{n}=\frac{1}{4}+\frac{3}{4}(1-4 \alpha)^{n}\). (b) What is the long-run proportion of time the chain is in each state?

Let the transition probability matrix of a two-state Markov chain be given, as in Example 4.2, by $$ \mathbf{P}=\left\|\begin{array}{cc} p & 1-p \\ 1-p & p \end{array}\right\| $$ Show by mathematical induction that $$ \mathbf{P}^{(n)}=\left\|\begin{array}{|ll} \frac{1}{2}+\frac{1}{2}(2 p-1)^{n} & \frac{1}{2}-\frac{1}{2}(2 p-1)^{n} \\ \frac{1}{2}-\frac{1}{2}(2 p-1)^{n} & \frac{1}{2}+\frac{1}{2}(2 p-1)^{n} \end{array}\right\| $$

In a Markov decision problem, another criterion often used, different than the expected average return per unit time, is that of the expected discounted return. In this criterion we choose a number \(\alpha, 0<\alpha<1\), and try to choose a policy so as to maximize \(E\left[\sum_{i=0}^{\infty} \alpha^{i} R\left(X_{i}, a_{i}\right)\right]\) (that is, rewards at time \(n\) are discounted at rate \(\left.\alpha^{n}\right)\) Suppose that the initial state is chosen according to the probabilities \(b_{i} .\) That is, $$ P\left\\{X_{0}=i\right\\}=b_{i}, \quad i=1, \ldots, n $$ For a given policy \(\beta\) let \(y_{j a}\) denote the expected discounted time that the process is in state \(j\) and action \(a\) is chosen. That is, $$ y_{j a}=E_{\beta}\left[\sum_{n=0}^{\infty} \alpha^{n} I_{\left[X_{n}=j, a_{n}=a\right\\}}\right] $$ where for any event \(A\) the indicator variable \(I_{A}\) is defined by $$ I_{A}=\left\\{\begin{array}{ll} 1, & \text { if } A \text { occurs } \\ 0, & \text { otherwise } \end{array}\right. $$ (a) Show that $$ \sum_{a} y_{j a}=E\left[\sum_{n=0}^{\infty} \alpha^{n} I_{\left\\{X_{n}=j\right\\}}\right] $$ or, in other words, \(\sum_{a} y_{j a}\) is the expected discounted time in state \(j\) under \(\beta\). (b) Show that $$ \begin{aligned} \sum_{j} \sum_{a} y_{j a} &=\frac{1}{1-\alpha}, \\ \sum_{a} y_{j a} &=b_{j}+\alpha \sum_{i} \sum_{a} y_{i a} P_{i j}(a) \end{aligned} $$ Hint: For the second equation, use the identity $$ I_{\left\\{X_{n+1}=j\right\\}}=\sum_{i} \sum_{a} I_{\left\\{X_{n-i}, a_{n-a}\right\rangle} I_{\left\\{X_{n+1}=j\right\\}} $$ Take expectations of the preceding to obtain $$ E\left[I_{\left.X_{n+1}=j\right\\}}\right]=\sum_{i} \sum_{a} E\left[I_{\left\\{X_{n-i}, a_{n-a}\right\\}}\right] P_{i j}(a) $$ (c) Let \(\left\\{y_{j a}\right\\}\) be a set of numbers satisfying $$ \begin{aligned} \sum_{j} \sum_{a} y_{j a} &=\frac{1}{1-\alpha}, \\ \sum_{a} y_{j a} &=b_{j}+\alpha \sum_{i} \sum_{a} y_{i a} P_{i j}(a) \end{aligned} $$ Argue that \(y_{j a}\) can be interpreted as the expected discounted time that the process is in state \(j\) and action \(a\) is chosen when the initial state is chosen according to the probabilities \(b_{j}\) and the policy \(\beta\), given by $$ \beta_{i}(a)=\frac{y_{i a}}{\sum_{a} y_{i a}} $$ is employed. Hint: Derive a set of equations for the expected discounted times when policy \(\beta\) is used and show that they are equivalent to Equation \((4.38) .\) (d) Argue that an optimal policy with respect to the expected discounted return criterion can be obtained by first solving the linear program $$ \begin{array}{ll} \operatorname{maximize} & \sum_{j} \sum_{a} y_{j a} R(j, a), \\ \text { such that } & \sum_{j} \sum_{a} y_{j a}=\frac{1}{1-\alpha}, \\ \sum_{a} y_{j a}=b_{j}+\alpha \sum_{i} \sum_{a} y_{i a} P_{i j}(a) \\ y_{j a} \geqslant 0, \quad \text { all } j, a \end{array} $$ and then defining the policy \(\beta^{*}\) by $$ \beta_{i}^{*}(a)=\frac{y_{i a}^{*}}{\sum_{a} y_{i a}^{*}} $$ where the \(y_{j a}^{*}\) are the solutions of the linear program.
See all solutions

Recommended explanations on Math Textbooks

Decision Maths

Read Explanation

Pure Maths

Read Explanation

Mechanics Maths

Read Explanation

Statistics

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Logic and Functions

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.