Question l{-'-l marks) {i} Consider a fully connected Markov chain with states {Eh . . . , E,-._-} and transition matrix {11),}- 2 pg, r',j = 1, . . . , N (such as the example shown in Fig. 6 of the notes]. Using only Eq. {11] of the notes for the probability of a path through the Markov chain and Eq. {13) for the proper- ties of the transition probabilities, show that the sum of the probabilities over all possible paths .1: = 31,...,:cg ofxedlengthL is 1. {ii} Consider a Markov chain with states {E51, . . . , EN}, together with beginning and end states H and 3 (such as the example shown in Fig. T of the notes}. Assume that the transition from any state E,- to the end state is p,\" = 1-, independent of i. Show using only Eq. {11'} and Eq. {16) of the notes that the sum of the probabilities of all possible paths I = 13,11, . . . ,IL, .5 of given length L is 71:1 1-}L'1. Hence show that the sum of the probabilities over all possible sequences of any length is 1. (iii) Consider the following scenario, which is famously referred as the Gambler's ruin problem. A gambler begins with $1, and makes a sequence of bets. For each bet, they win $1 dollar with probability p, and lose $1 dollar with probability 4; = 1 p. The gambler quits and stops playing if either they go broke i.e., have $21 dollars, or when they reach N dollars i.e., they have won {N 1) dollars. Dene a nite state Markov Chain that describes the above scenario. In particular, draw an appropriate diagram representing the chain, dene the set of states, and the matrix of transition probabilities. Please do not explicitly include any beginning and end states; it should be straight forward to see that the gambler having $1 constitutes a beginning state while the gambler having $0 and $N dollars both constitute end states. Suppose p = {1.3 and N = 21, nd: (a) The probability that the gambler will keep winning in the rst 3 bets. {b} The probability that the gambler will lose all his money before or at the 4th bets