I have a problem about Metropolis-Hasting algorithm that I understand intuitively, but find it difficult to write a clear proof.
Let $X$ be a finite set and $\pi : X \to [0,1]$ be the (difficult to sample) probability measure. For every $x \in X$ we have the proposal $Q_{X_n}$ with probability measure $q_{x} : X \to [0,1]$.
Define the acceptance probability of candidate $n+1$ by $$p(x,y) := \min\bigg\{\frac{\pi(y)}{\pi(x)} \frac{q_y(x)}{q_x(y)}, 1\bigg\} $$ and let $X_n, Y_n$ be two random variables such that $Y_n \sim Q_{X_n}$ (i.e we draw the next candidate according to $Q_{X_n}$) and $X_{n+1} := Y_n$ with probability $p(x,y)$ while $X_{n+1} := X_n$ (i.e rejection) with probability $1 - p(x,y)$
I want to prove that first $\mathbb{P}(Y_n = y|X_n = x) = q_x(y)$ and then show (using the law of total probability) that $$X_n \sim \pi \implies X_{n+1} \sim \pi$$
Both statements seem intuitively clear, since first $Y_n \sim Q_{X_n}$ and we can write $$\mathbb{P}(Y_n = y|X_n = x) = \frac{\mathbb{P}(Y_n = y,X_n = x)}{\mathbb{P}(X_n = x)} $$ but $X_n$ and $Y_n$ are not independent, their dependance is already "encoded" in $Q_{X_n}$ so this should definitely be equal $q_x(y)$, but I am not sure how to show that and also how to translate the second statement. Any help/hint would be great!
I think $P(Y_n = y \mid X_n = x)$ is defined as $q_x(y)$ (at least, that is how I interpret what "$Y_n \sim q_{X_n}$" means), so I am not sure there is anything that needs to be proved there.
Law of total probability: $$P(X_{n+1}=y) = \sum_{x \in X} P(X_n = x) P(X_{n+1}=y \mid X_n=x)$$
Hint 1: Show that $$P(X_{n+1} = y \mid X_n=x) = \begin{cases}q_x(y)p(x,y) & x \ne y \\ q_y(y) p(y,y) + \sum_{y' \ne y} q_y(y')(1-p(y,y')) & x = y \end{cases}$$
Plugging this in yields $$P(X_{n+1}=y) = \left(\sum_{x \ne y } \pi(x) q_x(y) p(x,y)\right) + \pi(y) q_y(y) p(y,y) + \pi(y) \sum_{y' \ne y} q_y(y') (1-p(y,y'))$$
Use the definition of $p(\cdot, \cdot)$ to cancel terms until you are left with $\pi(y)$.