×
Log in to StudySoup
Get Full Access to Introduction To Probability, - 2 Edition - Chapter 7 - Problem 7
Join StudySoup for FREE
Get Full Access to Introduction To Probability, - 2 Edition - Chapter 7 - Problem 7

Already have an account? Login here
×
Reset your password

Consider a Markov chain with some transient and some

Introduction to Probability, | 2nd Edition | ISBN: 9781886529236 | Authors: Dimitri P. Bertsekas John N. Tsitsiklis ISBN: 9781886529236 227

Solution for problem 7 Chapter 7

Introduction to Probability, | 2nd Edition

  • Textbook Solutions
  • 2901 Step-by-step solutions solved by professors and subject experts
  • Get 24/7 help from StudySoup virtual teaching assistants
Introduction to Probability, | 2nd Edition | ISBN: 9781886529236 | Authors: Dimitri P. Bertsekas John N. Tsitsiklis

Introduction to Probability, | 2nd Edition

4 5 1 404 Reviews
24
1
Problem 7

Consider a Markov chain with some transient and some recurrent states. (a) Show that for some numbers c and " with c > 0 and 0 < I < 1, we have P(Xn is transient I Xo = i) :5 C/n , for all i and n 1. (b) Let T be the first time n at which Xn is recurrent. Show that such a time is certain to exist (Le., the probability of the event that there exists a time n at which Xn is recurrent is equal to 1) and that E[T] < 00. Solution. (a) For notational convenience, let qi(n) = P(Xn transient I Xo = i). A recurrent state that is accessible from state i can be reached in at most m steps, where m is the number of states. Therefore, qi (m) < 1. Let {3 = , max qi(m) t=I , ... ,m and note that for all i, we have qi (m) :5 {3 < 1. If a recurrent state has not been reached by time m, which happens with probability at most {3, the conditional probability that a recurrent state is not reached in the next m steps is at most {3 as well, which suggests that qi(2m) :5 {3 2 . Indeed, conditioning on the possible values of Xm, we obtain qi(2m) = P(X2m transient I Xo = i) L P(X2m transient I Xm = j, Xo = i) P(Xm = j I Xo = i) j transient L P(X2m transient I Xm = j) P(Xm = j I Xo = i) J transient L P(Xm transient I Xo = j) P(Xm = j I Xo = i) j transient {3 L P(Xm = j I Xo = i) j transient = {3 P(Xm transient I Xo = i) {3 2. Continuing similarly, we obtain for all i and k 1. Let n be any positive integer, and let k be the integer such that km < n < (k + l)m. Then, we have Thus, the desired relation holds with c = {3- 1 and 'Y = {31/m. (b) Let A be the event that the state never enters the set of recurrent states. Using the result from part (a) , we have P(A) P(Xn transient) C"f n . Since this is true for every n and since 'Y < 1, we must have P(A) = O. This establishes that there is certainty (probability equal to 1) that there is a finite time T that a recurrent state is first entered. We then have DC E[T] = L nP(Xn- 1 transient, Xn recurrent) n=1 00 L nP(Xn- 1 transient) n=1 n=1 00 = c_ n(1 _ 'Y)'Y n-l 1 - 'Y L n=1 c where the last equality is obtained using the expression for the mean of the geometric distribution.

Step-by-Step Solution:
Step 1 of 3

STAT 2000 Chapter 1: Learning from Data  Defining Statistics: Statistics is a way of reasoning along with a collection of tools and methods, designed to help us understand the world  Statistics is the scientific discipline, which consists of: o Formulating a research question o The collection of data o Describing data o Drawing conclusions or generalizations from data Our ability to answer questions and draw conclusions from data depends largely on our ability to understand variation . The key to learning from data is understanding the variation that is all around us. Definition: Statistics, as a field of study, is the science of learning from data. This definition raises two qu

Step 2 of 3

Chapter 7, Problem 7 is Solved
Step 3 of 3

Textbook: Introduction to Probability,
Edition: 2
Author: Dimitri P. Bertsekas John N. Tsitsiklis
ISBN: 9781886529236

The answer to “Consider a Markov chain with some transient and some recurrent states. (a) Show that for some numbers c and " with c > 0 and 0 < I < 1, we have P(Xn is transient I Xo = i) :5 C/n , for all i and n 1. (b) Let T be the first time n at which Xn is recurrent. Show that such a time is certain to exist (Le., the probability of the event that there exists a time n at which Xn is recurrent is equal to 1) and that E[T] < 00. Solution. (a) For notational convenience, let qi(n) = P(Xn transient I Xo = i). A recurrent state that is accessible from state i can be reached in at most m steps, where m is the number of states. Therefore, qi (m) < 1. Let {3 = , max qi(m) t=I , ... ,m and note that for all i, we have qi (m) :5 {3 < 1. If a recurrent state has not been reached by time m, which happens with probability at most {3, the conditional probability that a recurrent state is not reached in the next m steps is at most {3 as well, which suggests that qi(2m) :5 {3 2 . Indeed, conditioning on the possible values of Xm, we obtain qi(2m) = P(X2m transient I Xo = i) L P(X2m transient I Xm = j, Xo = i) P(Xm = j I Xo = i) j transient L P(X2m transient I Xm = j) P(Xm = j I Xo = i) J transient L P(Xm transient I Xo = j) P(Xm = j I Xo = i) j transient {3 L P(Xm = j I Xo = i) j transient = {3 P(Xm transient I Xo = i) {3 2. Continuing similarly, we obtain for all i and k 1. Let n be any positive integer, and let k be the integer such that km < n < (k + l)m. Then, we have Thus, the desired relation holds with c = {3- 1 and 'Y = {31/m. (b) Let A be the event that the state never enters the set of recurrent states. Using the result from part (a) , we have P(A) P(Xn transient) C"f n . Since this is true for every n and since 'Y < 1, we must have P(A) = O. This establishes that there is certainty (probability equal to 1) that there is a finite time T that a recurrent state is first entered. We then have DC E[T] = L nP(Xn- 1 transient, Xn recurrent) n=1 00 L nP(Xn- 1 transient) n=1 n=1 00 = c_ n(1 _ 'Y)'Y n-l 1 - 'Y L n=1 c where the last equality is obtained using the expression for the mean of the geometric distribution.” is broken down into a number of easy to follow steps, and 470 words. This full solution covers the following key subjects: . This expansive textbook survival guide covers 9 chapters, and 326 solutions. The full step-by-step solution to problem: 7 from chapter: 7 was answered by , our top Statistics solution expert on 01/09/18, 07:43PM. This textbook survival guide was created for the textbook: Introduction to Probability,, edition: 2. Since the solution to 7 from 7 chapter was answered, more than 241 students have viewed the full step-by-step answer. Introduction to Probability, was written by and is associated to the ISBN: 9781886529236.

Other solutions

People also purchased

Related chapters

Unlock Textbook Solution

Enter your email below to unlock your verified solution to:

Consider a Markov chain with some transient and some