Question

We perform a sequence of independent Bernoulli trials. Each has probability p of success (S) and 1−p of failure (F). For each of the following chains, determine whether it is Markovian. If so, find its transition matrix; if not, modify the state space to make it Markovian. a. {Xn } n=0,1,2,… , where Xn​ is the total number of S in the first n trials. b. {Yn }n=0,1,2,… , where Yn is equal to 0,1a,1b, or 2 depending on whether the (n−1) st and the nth trials are SS,SF,FS, or FF, respectively. c. {Zn }n=0,1,2,… , where Zn is the total number of F s in the (n−1) st and the nth trials. d. {Tn }n=0,1,2,… , where Tn is equal to 0 if the (n−1) st and the nth trials are SS and 1 otherwise. e. {Un } n=0,1,2,… , where Un =0 if the nth trial is S or Un =k if the nth trial is F and the last S was obtained at the (n−k) th trial. In other words, Un is the accumulated number of F s since the last S. f. {Vn } n=0,1,2,… , where Vn =i if the nth success is at the i th trial.

Answer 1

a. The chain is Markovian with a transition matrix. b. The chain is not Markovian, but can be modified. c. The chain is not Markovian, but can be modified. d. The chain is Markovian with a transition matrix. e. The chain is not Markovian, but can be modified. f. The chain is not Markovian, but can be modified.

Step-by-step explanation:

a. {Xn} n=0,1,2,… , where Xn is the total number of S in the first n trials:

This chain is Markovian because the current state depends only on the previous state. The state space for this chain is {0, 1, 2, ..., n} where n is the total number of trials. The transition matrix is:

+---+---------------------+| | 0 | 1 | 2 | ... | n |+---+---------------------+| 0 | 1-p | p | 0 | ... | 0 || 1 | 0 | (1-p)| p | ... | 0 || 2 | 0 | 0 | (1-p)| ... | 0 ||...| ... | ... | ... | ... | ... || n | 0 | 0 | 0 | ... | p |+---+---------------------+

b. {Yn}n=0,1,2,… , where Yn is equal to 0,1a,1b, or 2 depending on whether the (n−1)st and the nth trials are SS,SF,FS, or FF, respectively:

This chain is not Markovian because the current state depends on the previous two states. To make it Markovian, we can modify the state space to {0, 1, 2} where 0 represents SS, 1 represents SF or FS, and 2 represents FF. The transition matrix is:

+---+------------------+| | 0 | 1 | 2 |+---+------------------+| 0 | p² | p(1-p) | 0 || 1 | 0 | p(1-p) | p || 2 | 0 | 0 | (1-p)|+---+------------------+

c. {Zn}n=0,1,2,… , where Zn is the total number of F s in the (n−1)st and the nth trials:

This chain is not Markovian because the current state depends on the previous two states. To make it Markovian, we can modify the state space to {0, 1} where 0 represents 0 or 1 F and 1 represents 2 F. The transition matrix is:

+---+------+| | 0 | 1 |+---+------+| 0 | (1-p)| p || 1 | 0 | 1-p|+---+------+

d. {Tn}n=0,1,2,… , where Tn is equal to 0 if the (n−1)st and the nth trials are SS and 1 otherwise:

This chain is Markovian because the current state depends only on the previous state. The state space for this chain is {0, 1} where 0 represents SS and 1 represents SF or FS or FF. The transition matrix is:

+---+---------+| | 0 | 1 |+---+---------+| 0 | 1-p | p || 1 | 0 | 1-p|+---+---------+

e. {Un} n=0,1,2,… , where Un =0 if the nth trial is S or Un =k if the nth trial is F and the last S was obtained at the (n−k)th trial:

This chain is not Markovian because the current state depends on past states. However, it can be modified to be Markovian. We can define a new state space that represents the accumulated number of F's since the last S. The state space will be {0, 1, 2, ..., n}, where n is the total number of trials. The transition matrix will be a square matrix of size (n+1) x (n+1):

+---+---------------------------+| | 0 | 1 | 2 | ... | n |+---+---------------------------+| 0 | p | 1-p | 0 | ... | 0 || 1 | 0 | p | 1-p | ... | 0 || 2 | 0 | 0 | p | ... | 0 ||...| ... | ... | ... | ... | ... || n | 0 | 0 | 0 | ... | 1-p |+---+---------------------------+

f. {Vn} n=0,1,2,… , where Vn =i if the nth success is at the ith trial:

This chain is not Markovian because the current state depends on past states. However, it can be modified to be Markovian. We can define a new state space that represents the number of trials until the ith success. The state space will be {0, 1, 2, ...} and the transition probabilities will depend on the probability of success in each trial. The transition matrix will be an infinite square matrix.