Proving a Markov Chain (Conditional Independence) Suppose that the joint distribution of $(X,Y,Z)\sim p(x,y,z)=p(x)~p(y|x)~p(z|x)$. This means that the following Markov chain holds:
$$Y-X-Z.$$
Suppose that now we define a random variable $\tilde{X}$ (with the same support set as $X$) such that the Markov chain
$$\tilde{X}-(Y,Z)-X,$$
holds and such that $P(\tilde{X}=\tilde{x}\big|Y,Z)=P(X=\tilde{x}\big|Y,Z)$. Hence the marginal distributions of $(X,Y,Z)$ and $(\tilde{X},Y,Z)$ are the same, and hence the Markov chain $Y-\tilde{X}-Z$ holds. Does the Markov chain $Y-(X,\tilde{X})-Z$ hold as well? In other words, does the relation
$$p(y|x,\tilde{x},z)=p(y|x,\tilde{x})$$
hold? Or instead, can anyone propose a counter example?
 A: Edit: just realized I missed a condition in my earlier answer.
In general the Markov chain would still not hold, because $P(X,\tilde{X},Y,Z)=P(Y,Z)P(\tilde{X}|Y,Z)P(X|Y,Z)=P(Y,Z)\frac{P(\tilde{X})P(Y|\tilde{X})P(Z|\tilde{X})}{P(Y,Z)}\frac{P({X})P(Y|X)P(Z|{X})}{P(Y,Z)}=\frac{P(\tilde{X})P({X})P(Y|\tilde{X})P(Y|X)P(Z|{X})P(Z|\tilde{X})}{P(Y,Z)}.$
Again, consider a binary Markov Chain that generates $X,Y,Z$, such that $P(X,Y,Z)\neq 0$ in all cases, and $Y,Z$ are not independent (both can be easily satisfied). The above quantity can not the factorized into a distribution for the needed Markov chain because $P(Y,Z)$ cannot be factorized (proof: check the determinant). So the answer is still no.
Here is my earlier answer where I ignored the condition that $\tilde{X}-Y,Z-X$ needs to be a Markov chain, and a simpler example can be found in that case.    
No, it does not hold even if $(X,Y,Z)$ are jointly independent.
Consider a joint distribution of $(X,\tilde{X},Y,Z)$ that is uniform on the subset of $\{0,1\}^4$ satisfying their parity sum is $0$. It is easy to verify that $(X,Y,Z)$ and $(\tilde{X},Y,Z)$ are uniformly random on $\{0,1\}^3$, but conditioned on $(X,\tilde{X})$, $Y$ and $Z$ are not independent, i.e., $Y$ and $Z$ are not fixed but $Y$ xor $Z$ is fixed.  
