0

I have been having struggling with this question for some time now and nothing comes to mind:
A group of $n$ processors are arranged in an ordered list. At every step, a task comes into the first processor in the list, if it cannot solve the task, it goes on to the second processor, if the second one cannot solve it, it moves on to the third and so on until it either gets solved or it leaves the last processor unsolved. If processor $i$ solved the problem, then it switches places with the processor preceding it. If processor $1$ solved the problem, or none of the processors solved it, the list stays the same. Pocessor $i$, if attempting a task, will solve it, independently of everything else, with probability $p_i$. If a Markov chain with states $(\sigma (1),...,\sigma(n))$ is created from this process, where $\sigma$ is a permutation, what are its long term probabilities? I.e. what is $$\lim P(X_n=(\sigma(1),...,\sigma(n))$$ Since a given permutation can only transition into a transposition of itself $$P((x_1,...,x_i,x_{i+1},...,x_n)\to(x_1,...,x_{i+1},x_{i},...,x_n))=p_{x_i}\prod_{k=1}^i (1-p_{x_k})$$ However, the long term proportions have me stumped. I solved the specific case for $n=2,3$ to look for some pattern in the expressions but I came up empty handed, maybe because of some mistake in the computations.
Any suggestions or hints?

GuPe
  • 7,318

1 Answers1

0

Suppose the chain is time reversible, then for a given permutation $\sigma$ and transposition $\tau_i$ of the ordering of the processors $$\pi (\sigma)P(\sigma,\tau_i \sigma)=\pi(\tau_i \sigma)P(\tau_i \sigma,\sigma) \tag{0}$$ If $\tau_i$ transposes $\sigma(i)$ with $\sigma(i+1)$ we have $$\pi (\sigma)p_{\sigma(i+1)}q_{\sigma(i)}\prod_{k=1}^{i-1}q_{\sigma(k)}=\pi(\tau_i \sigma)p_{\sigma(i)}q_{\sigma(i+1)}\prod_{k=1}^{i-1}q_{\sigma(k)}$$

Where $q_x=1-p_x$ and the above implies that $$\pi (\sigma)\left(\frac{q_{\sigma(i+1)}}{p_{\sigma(i+1)}}\right)^{-1}\frac{q_{\sigma(i)}}{p_{\sigma(i)}}=\pi(\tau_i \sigma)\tag{1}$$

Which shows that that every time we move an element $\sigma(i)$ of the permutation to the right we multiply the expression by $\frac{q_{\sigma(i)}}{p_{\sigma(i)}}$ and we multiply by $\left(\frac{q_{\sigma(i+1)}}{p_{\sigma(i+1)}}\right)^{-1}$ if an element $\sigma(i+1)$ gets shifted to the left. If we wish to transform $\sigma$ back to $\epsilon$ (the identity permutation), then, for all $i$ we must shift $\sigma(i)$ back to $i$, i.e. move it $\sigma(i)-i$ places to the right (this is because of *) this entails multiplying $\pi(\sigma)$ by $\left(\frac{q_{\sigma(i)}}{p_{\sigma(i)}}\right)^{\sigma(i)-i}$, doing this for all $i$ yields

$$\pi(\sigma)\prod_{i=1}^n\left(\frac{q_{\sigma(i)}}{p_{\sigma(i)}}\right)^{\sigma(i)-i}=\pi(\epsilon)$$ Or $$\pi(\sigma)=\pi(\epsilon)\prod_{i=1}^n\left(\frac{q_{\sigma(i)}}{p_{\sigma(i)}}\right)^{i-\sigma(i)}\tag{2}$$

where we use that $\sum_{\sigma} \pi (\sigma)=1$ to get $$\pi(\epsilon) = \left(\sum_{\sigma}\prod_{i=1}^n\left(\frac{q_{\sigma(i)}}{p_{\sigma(i)}}\right)^{i-\sigma(i)}\right)^{-1}$$

With this ansatz, define $\pi(\sigma)$ by $(2)$ for all $\sigma$. Then, because $\tau_j\sigma(i)=\sigma(i)$ for all $i \ne j,j+1$, $\tau_j\sigma(j)=\sigma(j+1)$, $\tau_j\sigma(j+1)=\sigma(j)$:

$$\begin{align}\pi(\tau_j \sigma) &= \pi(\epsilon)\prod_{i=1}^n\left(\frac{q_{\tau_j\sigma(i)}}{p_{\tau_j\sigma(i)}}\right)^{i-\tau_j\sigma(i)} \\ \\ &=\pi(\epsilon)\prod_{i=1,i\ne j,j+1}^n\left(\frac{q_{\tau_j\sigma(i)}}{p_{\tau_j\sigma(i)}}\right)^{i-\tau_j\sigma(i)} \left(\frac{q_{\tau_j\sigma(j)}}{p_{\tau_j\sigma(j)}}\right)^{j-\tau_j\sigma(j)} \left(\frac{q_{\tau_j\sigma(j+1)}}{p_{\tau_j\sigma(j+1)}}\right)^{j+1-\tau_j\sigma(j+1)}\\ &=\pi(\epsilon)\prod_{i=1,i\ne j,j+1}^n\left(\frac{q_{\sigma(i)}}{p_{\sigma(i)}}\right)^{i-\sigma(i)} \left(\frac{q_{\sigma(j+1)}}{p_{\sigma(j+1)}}\right)^{j-\sigma(j+1)} \left(\frac{q_{\sigma(j)}}{p_{\sigma(j)}}\right)^{j+1-\sigma(j)}\\ &=\pi(\epsilon)\prod_{i=1,i\ne j,j+1}^n\left(\frac{q_{\sigma(i)}}{p_{\sigma(i)}}\right)^{i-\sigma(i)} \left(\frac{q_{\sigma(j+1)}}{p_{\sigma(j+1)}}\right)^{j+1-\sigma(j+1)}\left(\frac{q_{\sigma(j+1)}}{p_{\sigma(j+1)}}\right)^{-1} \left(\frac{q_{\sigma(j)}}{p_{\sigma(j)}}\right)^{j-\sigma(j)}\left(\frac{q_{\sigma(j)}}{p_{\sigma(j)}}\right) \\ &=\pi(\epsilon)\prod_{i=1}^n\left(\frac{q_{\sigma(i)}}{p_{\sigma(i)}}\right)^{i-\sigma(i)} \left(\frac{q_{\sigma(j+1)}}{p_{\sigma(j+1)}}\right)^{-1} \left(\frac{q_{\sigma(j)}}{p_{\sigma(j)}}\right)\\ &=\pi(\sigma) \left(\frac{q_{\sigma(j+1)}}{p_{\sigma(j+1)}}\right)^{-1} \left(\frac{q_{\sigma(j)}}{p_{\sigma(j)}}\right) \end{align}$$

So $(1)$ is verified,$(0)$ follows from $(1)$, and summing $(0)$ over all permutations shows that $\pi(\sigma)$ satisfies the long term equations.
$$(*) $$

  1. In $\sigma$, $\sigma(i)$ is in slot $i$
  2. In $\epsilon$, $\sigma(i)$ is in slot $\sigma(i)$
  3. In $\epsilon$, $i$ is in slot $i$. $$ $$ How far away is $\sigma(i)$ in $\sigma$ from $\sigma(i)$ in $\epsilon$ ($\text{target}$)? $$\begin{bmatrix}\text{slots} & 1 & \cdots & i & \cdots &\sigma(i) &\cdots&n \\ \epsilon & 1 & \cdots & i & \cdots &\sigma(i) &\cdots&n\\ \sigma & \sigma(1) & \cdots & \sigma(i) & \cdots & \text{target} &\cdots&\sigma(n)\end{bmatrix}$$ The answer is $\sigma(i)-i$ units to the right, because if $\sigma(i)\ge i \Rightarrow \sigma(i)-i\ge 0 $, and we want the exponent of $\frac{q_{\sigma(i)}}{p_{\sigma(i)}}$ to be positive so that $\sigma(i)$ moves to the right toward $\text{target}$.
GuPe
  • 7,318