91Ó°ÊÓ

Let's represent the state of the system by a permutation of \(\{1, 2, ..., n\}\), where \(i^{th}\) element in the permutation denotes the processor at the \(i^{th}\) position in the line. Then, the Markov chain is on the state space consisting of all permutations of \(\{1, 2, ..., n\}\). In this chain, there is a transition from a particular state (permutation) to another state (permutation) when the state of the processors reorders according to the one-closer rule and the probabilities of successful processing. #Step 2: Time Reversibility#

First, let's consider two consecutive states \(x\) and \(y\) where \(x\) is the state before job processing and \(y\) is the state after job processing and reordering according to the one-closer rule. We can say that the Markov chain has time-reversibility property if the probability of transitioning from state \(x\) to state \(y\) is the same as the probability of transitioning from state \(y\) to state \(x\). Mathematically, this can be represented as: \[ \pi(x)P(x,y) = \pi(y)P(y,x) \] Since we only need to check the reversibility property, let's assume that the chain has reached its stationary distribution \(\pi\). The probability of moving from state \(x\) to state \(y\) is given by the probability that the job is processed by the processor in position \(i-1\) if there is a switch between positions \(i\) and \(i-1\): \[ P(x,y) = p_{x_{i-1}} \prod_{j=1}^{i-2} (1-p_{x_j}) \] The probability of moving from state \(y\) to state \(x\) is given by the probability that the processor in position \(i\) processes the job: \[ P(y,x) = p_{y_i} \prod_{j=1}^{i-1} (1-p_{y_j}) \] Now, let's compare these two probabilities and stationary distribution product: \[ \pi(x)p_{x_{i-1}} \prod_{j=1}^{i-2} (1-p_{x_j}) = \pi(y)p_{y_i} \prod_{j=1}^{i-1} (1-p_{y_j}) \] After calculating both probabilities, we can find that indeed the chain is time reversible. #Step 3: Long Run Probabilities#

Since the Markov Chain is time-reversible, to find the long run probabilities, we need to solve the detailed balance equations: \[ \pi(x)P(x,y) = \pi(y)P(y,x) \] We know from Step 2 that, \[ \pi(x)p_{x_{i-1}} \prod_{j=1}^{i-2} (1-p_{x_j}) = \pi(y)p_{y_i} \prod_{j=1}^{i-1} (1-p_{y_j}) \] In the stationary state, the product of swap probabilities will be equal. To find the long run probabilities, we need to sum the probabilities over all states for a given permutation: \[ \pi(x) = \frac{\prod_{i=1}^{n-1} (1-p_i)p_{i+1}}{\sum_{j=1}^{n} \prod_{i=1}^{j-1} (1-p_i)p_{i+1}} \] This gives us the long run probabilities of each state in the Markov Chain describing the processors' system.