Stochastic Processes – Problem 3: Prove

Under probability measure $\mathbb{P}$, let $X_t$ be a Markov chain on state space $\Omega$ with transition kernel $p(x,y)$ and invariant distribution $\pi$. Define a subset-valued Markov chain $S_t$ by: given $S_t = S \subset \Omega$, sample $U \sim \mathrm{Uniform}[0,1]$ independently and set $$S_{t+1}=\left\{y\in\Omega:\frac{\sum_{x\in S}\pi(x)p(x,y)}{\pi(y)}\ge U\right\}.$$ Let $P$ denote the law of $S_t$, and let $P^t(x,y):=\mathbb{P}(X_t=y\mid X_0=x)$. Prove $$P^t(x,y)=\frac{\pi(y)}{\pi(x)}\,P(y\in S_t\mid S_0=\{x\}).$$

Step 1. For any fixed subset $S \subset \Omega$, define $$a_S(y):=\frac{\sum_{z\in S}\pi(z)p(z,y)}{\pi(y)}.$$ Because $\pi$ is invariant, $0 \le a_S(y) \le 1$.

Step 2. From the update rule with $U \sim \mathrm{Uniform}[0,1]$, $$P(y\in S_{t+1}\mid S_t=S)=a_S(y)=\frac{\sum_{z\in S}\pi(z)p(z,y)}{\pi(y)}.$$ Taking expectation over $S_t$, $$P(y\in S_{t+1}\mid S_0=\{x\})\n=\frac{1}{\pi(y)}\sum_{z\in\Omega}\pi(z)p(z,y)\,P(z\in S_t\mid S_0=\{x\}).$$

Step 3. Define $$H_t(x,y):=\frac{\pi(y)}{\pi(x)}P(y\in S_t\mid S_0=\{x\}).$$ Then the relation above becomes $$H_{t+1}(x,y)=\sum_{z\in\Omega}H_t(x,z)p(z,y).$$ This is exactly the Chapman-Kolmogorov recursion.

Step 4. Initial condition: when $t=0$, $S_0=\{x\}$, so $$H_0(x,y)=\frac{\pi(y)}{\pi(x)}\mathbf 1_{\{y=x\}}=\mathbf 1_{\{y=x\}}=P^0(x,y).$$ Hence, by induction on $t$, $H_t(x,y)=P^t(x,y)$ for all $t\ge0$, proving the claim.

QED.