Say I have this Markov chain. Then I perform bisimulation on it, where I find the largest relation between the states of the Markov chain. Finally I can construct a bisimulation quotient/minimization (I think this is similar to a DFA minimisation) where the markov chain has become significantly smaller. That's all good.
What I'm speculating about is whether the steady state distribution actually changes? If it does then how is it still related to the original steady state distribution of the un-minimised markov chain?
I can't seem to get my head around it. You have new states where each contains a group of states. But the probability would still be the same, you just have less states in the probability transition matrix. Right?
First of all, the topic of bisimulation may not be familiar to others, so I would encourage you to provide some references, especially when talking about bisimilar stochastic processes. I think, it shall be related to the probabilistic notion of lumpability.
Now, bisimulation is a relation between two systems: two Markov Chains may be bisimilar if they have the same labelling/output structure, but different state spaces - in fact our main hope is that we can find a bimilar Markov Chain over a smaller state space. Say, we start with a Markov Chain $C$ with $n$ states and construct a bisimilar Markov Chain $\bar C$ with $m<n$ states. Their invariant distributions cannot be the same for a simple reason that an invariant distribution of $C$ satisfies $\pi\in \Delta_n$ whereas $\bar\pi \in \Delta_m$, where $$ \Delta_i:=\{p\in\Bbb R^n_+:p\cdot \mathbf 1 = 1\} $$ is the $i$-dimensional probability simplex. Yet, it is an interesting question whether $\bar\pi$ can be obtained from $\pi$ in a simple way.
Ok, let $X$ be the state space of $C$ and $\bar X$ be the state space of $\bar C$, and let $p$ and $\bar p$ be the corresponding stochastic matrices. Let $f:X\to \bar X$ denote the abstraction map, that is for all $x\in X$ and $\bar y\in \bar X$ it holds that $$ \bar p(\bar y|f(x)) = \sum_{y\in f^{-1}(\bar y)}p(y|x). $$ Let $\pi$ be any invariant distribution of $p$, that is for all $y\in X$ $$ \sum_{x\in X} p(y|x)\pi(x) = \pi(y). $$ Denote $\bar\pi := f_*\pi$ that is $\bar\pi(\bar y) := \sum_{y\in f^{-1}(\bar y)}\pi(y)$. We have $$ \begin{align} \sum_{\bar X\in \bar X}\bar p(\bar y|\bar x)\bar\pi(\bar x) &= \sum_{\bar x\in \bar X}\sum_{x\in f^{-1}(\bar x)}\bar p(\bar y|\bar x)\pi(x) = \sum_{x\in X}\bar p(\bar y|f(x))\pi(x) \\ &= \sum_{x\in X}\sum_{y\in f^{-1}(\bar y)}p(y|x)\pi(x) = \sum_{y\in f^{-1}(\bar y)}\sum_{x\in X}p(y|x)\pi(x) \\ &= \sum_{y\in f^{-1}(\bar y)}\pi(y) = \bar\pi(\bar y). \end{align} $$