Operation Research (Markov Chains) 16.3-2. Suppose that a communications network

Question

Operation Research (Markov Chains)

16.3-2. Suppose that a communications network transmits binary digits, 0 or 1, where each digit is transmitted 10 times in succes- sion. During each transmission, the probability is 0.99 that the digit entered will be transmitted accurately. In other words, the proba- bility is 0.01 that the digit being transmitted will be recorded with the opposite value at the end of the transmission. For each trans- mission after the first one, the digit entered for transmission is the one that was recorded at the end of the preceding transmission. If Xo denotes the binary digit entering the system, X1 the binary digit recorded after the first transmission, X2 the binary digit recorded after the second transmission,..., then (X,) is a Markov chain. (a) Construct the (one-step) transition matrix. c (b) Use your OR Courseware to find the 10-step transition ma- trix p(lo, Use this result to identify the probability thata digit entering the network will be recorded accurately after the last transmission. c (c) Suppose that the network is redesigned to improve the prob- ability that a single transmission will be accurate from 0.99 to 0.999. Repeat part (b) to find the new probability that a digit entering the network will be recorded accurately after the last transmission.

Explanation / Answer

a) We have two states, let '00' be the first and '11' the second one. Assuming such a labelling, the transition matrix is

P=(p1q1pq)P=(p1p1qq)

as, for example, the [2,1]2,1] cell represents the probability of mistake while sending '11' message. (i.e. probability of going from state '11' to state '00' in one step. Still in other words: receiving '00' when '11' is being transmitted via given link).

b) Since our Markov chain is irreducible and both states are aperiodic, the stationary distribution =[1,2]T=[1,2]T exists and is unique. We can find it by solving system of equations

[12](p1q1pq)=[12][12](p1p1qq)=[12]

together with 1+2=1.1+2=1. My computation yields 1=1q2(p+q)1=1q2(p+q) and 2=1p2(p+q)2=1p2(p+q).

c) It is the question about the probability of going from '00' to '00' in exactly two steps. Such a scenario can be realized in two ways:

Hence, the answer is p2+(1p)(1q)p2+(1p)(1q). Alternatively, you can compute the [1,1][1,1] cell of P2P2 - two-step transition probability matrix.

Ad d) One can consider 5050 as sufficiently large number of steps to approximate limnpn11limnp11n that is equal to 11 (see limiting distribution theorem). Hence, the answer is 1q2(p+q)1q2(p+q).

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.