Three prisoners paradox

This is quite a famous paradox and it's quite mind boggling indeed without careful analysis. It goes like this:
Three prisoners X, M and N are on a death row, however one of them will be pardoned. X asks the guard whether he will be pardoned, however the guard can't tell him that, but instead tells him that M will be executed. Now X believes that his chance of survival increases from 1/3 to 1/2. However, the truth is that X's chance of survival has not changed a bit, and miraculously it is N's chance of being pardoned that has increased from 1/3 to 2/3!



There are various ways to show this, the one that I am most comfortable with is by using these two theorems:
1. P(A|B) = P(A and B)/P(B) = P(B|A)*P(A)/P(B) (definition of conditional probability and Bayes' Theorem)
2. P(A) = sum of P(A, b) over b (marginalisation)

The description of the paradox assumes a uniform distribution where each of the outcomes (X dies, M dies, N alive), (X dies, M alive, N dies), and (X alive, M dies, and N dies) is given equal probability, i.e. 1/3. Now the key thing is to differentiate between these two statements:
S1. Probability of X alive, given M dies.
S2. Probability of X alive, given the guard tells X that M dies.

S1 has a totally different sample space as compared to S2. In S1, we now have either (X dies, M dies, N alive) or (X alive, M dies, N dies), which gives P(X alive given M dies) = 1/2. There is nothing wrong with this. That is why it seems paradoxical. However, the problem above implies S2.

S2 on the other hand has a sample space (who guard told X will die, fate of X, fate of M, fate of N). And also, the distribution of this sample space is certainly not uniform! Let G denote who the guard names (and to bring up GoT reference, a man needs a name...). We now consider:
1. P(G=M | X dies). The guard can't tell X that he will die, so the guard must name the other person who dies, which in this case M. Hence P(G=M | X dies) = 1.
2. P(G=M | X alive). The guard can choose to name either M or N. Hence P(G=M | X alive) = 1/2.
Now what we really want is P(X alive| G=M). This can be computed by using the above rules I mentioned:
P(X alive| G = M) = P(G=M | X alive) * P(X alive)/P(G=M)
And we have P(G=M) = P(G=M| X alive) * P(X alive) + P(G=M| X dies) * P(X dies), which gives us
P(X alive | G = M) = P(G=M | X alive) * P(X alive) / [P(G=M| X alive) * P(X alive) + P(G=M| X dies) * P(X dies)] (which is basically Bayes' Theorem) = 1/2 * 1/3 / (1/2 * 1/3 + 1 * 1/3) = 1/3.
Hence P(X alive | G = M) = 1/3 which shows that X's chance of survival has not changed, as desired.