System
Alice and Bob are moving independently from one city to another. There are $d$ cities, the probability of moving to another city (for each individual) is $m$ and each move is equiprobable (there is no preferred city). The choice of moving and choice of where to move to of Alice are independent of the choices of Bob.
Terminology
Let $X_t$ be the state of the system at time $t$. Let $S$ be the state in which Alice and Bob are in the same city, while $\bar S$ is the state in which Alice and Bob are in different cities. therefore, $P(X_{t-1}=S \space|\space X_{t}=\bar S)$ is the probability that at time $t-1$ Alice and Bob were in the same city given that they currently are in different cities.
Previous post?
FYI, we have shown in this post (no need to read it) that $P(X_t = S \space|\space X_{t-1} = \bar S) = \frac{m(2d-md-2)}{(d-1)^2}$.
Question
I am trying to understand the relationship between the following eight probabilities
Forward Probabilities
- $P(X_t = S \space|\space X_{t-1} = \bar S)$
- $P(X_t = \bar S \space|\space X_{t-1} = \bar S)$
- $P(X_t = S \space|\space X_{t-1} = S)$
- $P(X_t = \bar S \space|\space X_{t-1} = S)$
Backward Probabilities
- $P(X_{t-1} = S \space|\space X_t = \bar S)$
- $P(X_{t-1} = \bar S \space|\space X_t = \bar S)$
- $P(X_{t-1} = S \space|\space X_t = S)$
- $P(X_{t-1} = \bar S \space|\space X_t = S)$
We will assume that the markov process started at $t=-\infty$.
What relationships are there between these probabilities? How many probabilities do we need to know to infer all the others?
My thoughts
Let $A$ and $B$ be independent variables that can take either values $S$ or $\bar S$. It is clear for me that (forward probabilities)
$$P(X_t = S \space|\space X_{t-1} = A) = 1 - P(X_t = \bar S \space|\space X_{t-1} = A) \space \forall \space A$$
and (backward probabilities)
$$P(X_{t-1} = S \space|\space X = A) = 1 - P(X_{t-1} = \bar S \space|\space X = A) \space\forall \space A$$
Now it feels to me that
$$P(X_t = A \space|\space X_{t-1} = B) = P(X_{t-1} = B \space|\space X = A) \space\forall\space A,B$$
Is it true? What characteristic of my system make it true? (Is it true for my system because $m$ is the same for all pair of cities?)
More details of my comment:
Let $\{X_t\}_{t=-\infty}^{\infty}$ be any irreducible and aperiodic discrete time Markov chain (DTMC) with finite or countably infinite state space $S$. Let $P=(P_{ij})$ be the transition probability matrix. Suppose $\pi = (\pi_i)_{i \in S}$ is vector with nonnegative entries that sum to 1. Suppose also that $\pi = \pi P$ (where we view $\pi$ as a row vector). Then, a fundamental theorem of Markov chains ensures $\pi$ is the unique steady state distribution. The chain has been running since the beginning of time and so we imagine it to be in steady state at all times $t \in \mathbb{Z}$. So $P[X_t=i] = \pi_i$ for all $t$. Define the “reversed” probabilities $P^*_{ij}$: $$ P^*_{ij} = P[X_{t-1}=j | X_t = i] = \frac{P[X_t=i|X_{t-1}=j]P[X_{t-1}=j]}{P[X_t=i]} = \frac{P_{ji}\pi_j}{\pi_i} \quad \forall i, j \in S$$
We define the DTMC to be reversible if $P^*_{ij} = P_{ij}$ for all $i,j \in S$. Now you can see the reversible definition is equivalent to: $$ \boxed{\pi _i P_{ij} = \pi_j P_{ji} \quad \forall i, j \in S}$$ The above boxed equations are called the detail equations. If you were to watch a reversible process on video, you would not be able to determine whether you are watching the video in forward motion or rewind motion, because (it can be shown that) the forward and reversed processes are statistically equivalent.
Now, most ergodic DTMCs are not reversible. However, a class of processes called birth-death processes are known to be reversible. A birth-death process is a particular DTMC $X_t$ with state space $S = \{0, 1, 2, ...\}$ and where the state can increase or decrease by at most one on a single slot (either a "birth," a "death," or stay same). It can be shown that if a birth-death process has a steady state distribution, then it must satisfy the detail equations. That is because steady states for birth-death processes satisfy the following cut set equation at every "cut" between states $i$ and $i+1$: $$ \pi_i P_{i,i+1} = \pi_{i+1}P_{i+1,i} $$
The particular chain in your question looks like a 2-state process with states $0$ and $1$, and so the chain is indeed reversible with $\pi_0 P_{01} = \pi_1 P_{10}$. Even without the theory of birth-death processes, you can draw a generic picture of a 2-state chain with generic transition probabilities $P_{01}$ and $P_{10}$ and then show that, indeed, the steady state must satisfy $\pi_0 P_{01} = \pi_1 P_{10}$.
An example is a discrete time "B/B/1" queue, where $Q(t)$ is the integer number of jobs queued at integer time $t$ and satisfies: $$ Q(t+1) = \max[Q(t) - b(t), 0] + a(t) $$ where $\{a(t)\}_{t=0}^{\infty}$ are i.i.d. Bernoulli arrivals with $P[a(t)=1]=\lambda$, $\{b(t)\}_{t=0}^{\infty}$ are independent and i.i.d. Bernoulli service opportunities (with $P[b(t)=1]=\mu$) and with $0< \lambda < \mu<1$. This is a birth-death process. Since the arrivals to the queue are i.i.d. Bernoulli with rate $\lambda$, the theory of reversibility shows that, in steady state, the departures from the queue are also i.i.d. Bernoulli with rate $\lambda$. In particular, this means that we can analyze tandems of B/B/1 queues very easily. I actually used this tandem property once in a paper "Capacity and Delay Tradeoffs for Ad-Hoc Mobile Networks."