Question

(a) Show that Approximation 1 of Section \(6.8\) is equivalent to uniformizing the continuous-time Markov chain with a value \(v\) such that \(v t=n\) and then approximating \(P_{i j}(t)\) by \(P_{i j}^{* n}\). (b) Explain why the preceding should make a good approximation. Hint: What is the standard deviation of a Poisson random variable with mean \(n\) ?

Short answer

(a) Approximation 1 of Section 6.8 involves uniformizing the continuous-time Markov chain (CTMC) using a common rate v, such that vt = n. The relationship between the transition probabilities of the original CTMC (\(P_{ij}(t)\)) and the embedded discrete-time Markov chain (DTMC) (\(P_{ij}^*\)) is defined as \(P_{ij}^* = \frac{P_{ij}(t)}{v}\). Rewriting this, we have \(P_{ij}(t) = P_{ij}^{*n}\), showing that \(P_{ij}(t)\) is approximated by \(P_{ij}^{*n}\). (b) This approximation works well because it captures the fact that most of the probability mass for a Poisson random variable concentrates around its mean, n. As n increases, the standard deviation also increases, but the relative difference between the standard deviation and the mean decreases. Approximating the CTMC using this embedded DTMC ensures the overall behavior of the system is accurately captured, making it a good approximation.

Step-by-step solution

In section 6.8, Approximation 1 is the procedure of discretizing a continuous-time Markov chain (CTMC) by replacing the original CTMC with an embedded discrete-time Markov chain (DTMC). Essentially, this involves uniformizing the transition rates such that a common rate v is used, where v is chosen such that vt = n. #Step 2: Uniformize the CTMC using value v#

Uniformizing is a technique used to transform a continuous-time Markov chain into an embedded discrete-time Markov chain with a common rate v. Let's denote the original CTMC with transition probabilities \(P_{ij}(t)\) and its embedded DTMC with transition probabilities \(P_{ij}^*\). We can define the uniformizing transformation using the following relation: \[P_{ij}^* = \frac{P_{ij}(t)}{v}\] #Step 3: Approximate P_ij(t) by P_ij^*n##

Since we know that vt = n, we can rewrite the earlier relation as follows: \[P_{ij}(t) = P_{ij}^* v\] Now, by multiplying both sides of the equation by n, we have: \[P_{ij}(t) = P_{ij}^{*n}\] #Step 4: Explain why this approximation is good#

The reason this approximation works well is that it effectively captures the fact that most of the probability mass for the Poisson random variable concentrates around its mean. Since we are choosing a value v based on the mean, the expected number of transitions in the embedded discrete-time Markov chain will be close to n. In other words, as n increases, the standard deviation of a Poisson random variable with mean n will increase, but the relative difference between the standard deviation and the mean will decrease. As a result, approximating the continuous-time Markov chain using this embedded discrete-time Markov chain ensures that the overall behavior of the system is captured accurately, because most of the probability mass is concentrated around the mean. And since we are approximating \(P_{ij}(t)\) by \(P_{ij}^{*n}\), the values will be close to each other, making it a good approximation. Hence, the Approximation 1 of Section 6.8 is equivalent to uniformizing the continuous-time Markov chain with a value v such that vt = n and then approximating \(P_{ij}(t)\) by \(P_{ij}^{*n}\) which should make a good approximation.