Hamiltonian Monte Carlo Markov chain for discrete distributions I am reading a paper about how to run HMC Markov chain to sample from a discrete probability distribution. The central idea is to map the discrete distribution to a continuous one. There are pieces of explanation in Page $2$ which I do not understand.
We are interested in sampling from a probability distribution $p(\textbf{s})$ defined over $d$-dimensional binary vectors $\textbf{s} \in \{−1, +1\}^d$, and given in terms of a function $f(\textbf{s})$ as
$$
p(\textbf{s}) = \frac{1}{Z} f(\textbf{s})
$$
Here $Z$ is a normalization factor, whose value will not be needed. Let us augment the distribution $p(\textbf{s})$ with continuous variables $\textbf{y} \in \mathbb{R}^d$ as
$$
p(\textbf{s},\textbf{y}) = p(\textbf{s})p(\textbf{y}|\textbf{s})\tag{2}
$$
where $p(\textbf{y}|\textbf{s})$ is non-zero only in the orthant defined by
$$s_i = sign(y_i)\quad i = 1,\ldots,d \tag{3}$$
The essence of the proposed method is that we can sample from $p(\textbf{s})$ by sampling $\textbf{y}$ from
$$p(\textbf{y}) = \sum_{\textbf{s}'}p(\textbf{s}′)p(\textbf{y}|\textbf{s}′) = p(\textbf{s})p(\textbf{y}|\textbf{s})\tag{4}$$
and reading out the values of $\textbf{s}$ from $(3)$. In the second line we have made explicit that for each $\textbf{y}$, only one term in the sum in $(4)$ is non-zero, so that $p(\textbf{y})$ is piecewise defined in each orthant.

I understand that $(2)$ is a joint distribution and thus I understand the first equality in $(4)$ (we are finding the marginal probability) but I don't understand why the second equality in $(4)$ is true?


I understand that $(3)$ is a mapping from $\textbf{y}$ to $\textbf{s}$. So if we can sample $\textbf{y}$, $(3)$ gives us a corresponding $\textbf{s}$. But I don't understand these two lines: "where $p(\textbf{y}|\textbf{s})$ is non-zero only in the orthant" and "In the second line we have made explicit that for each $\textbf{y}$, only one term in the sum in $(4)$ is non-zero". May I know why the above two are true? Thanks.

 A: It's easier to see what's going on by approaching the problem from the opposite direction.  The authors want to get samples of a random binary $\ d$-vector $\ \textbf{s}\ $ with probability mass function $\ p_\textbf{s}(s)=P(\textbf{s}=s)=\frac{1}{Z}f(s)\ $ by instead drawing samples of a random vector $\ \textbf{y}\ $, continuously distributed over $\ \mathbb{R}^d\ $, and putting $\ \textbf{s}_i=sign(\textbf{y}_i)\ $.  If $\ \textbf{y}\ $ has density $\ p_\textbf{y}\ $ and $\ \mathscr{O}_s\ $ is the orthant where $\ sign (y_i)=s_i\ $, then the density $\ p_\textbf{y}\ $ has to be chosen so that
$$
P\big(\textbf{y}\in\mathscr{O}_s\big)=\int_{\mathscr{O}_s}p_\textbf{y}(y)\,dy=p_\textbf{s}(s)\ .
$$
The joint distribution of $\ \textbf{y}\ $ and $\ \textbf{s}\ $ will be given by
\begin{align}
P\big(\textbf{y}\in A, \textbf{s}=s\big)&=P\big(\textbf{y}\in A\cap\mathscr{O}_s\big)\\
&=\int_{\mathscr{O}_s\cap A}p_\textbf{y}(y)\,dy\ ,
\end{align}
because the event $\ \big\{\textbf{y}\in A\big\}\cap\big\{\textbf{s}=s\big\}\ $ occurs if and only if the event $\ \big\{\textbf{y}\in A\cap\mathscr{O}_s\big\}\ $ does.  Dividing the above equation by $\ p_\textbf{s}(s)\ $, we get
\begin{align}
P\big(\textbf{y}\in A\ \big|\,\textbf{s}=s\big)&=\frac{P\big(\textbf{y}\in A, \textbf{s}=s\big)}{p_\textbf{s}(s)}\\
&=\int_{\mathscr{O}_s\cap A}\frac{p_\textbf{y}(y)}{p_\textbf{s}(s)}\,dy\\
&=\int_{A}\frac{\chi_{_{\scriptsize{\mathscr{O}_s}}}(y)p_\textbf{y}(y)}{p_\textbf{s}(s)}\,dy\ ,
\end{align}
where $\ \chi_{_{\scriptsize{\mathscr{O}_s}}}\ $ is the characteristic function of $\ \mathscr{O}_s\ $. By definition, the integrand in this last integral  is the conditional density $\ p_{\textbf{y}|\textbf{s}}\ $ of $\ \textbf{y}\ $ given $\ \textbf{s}\ $:
$$
p_{\textbf{y}|\textbf{s}}(y|s)=\frac{\chi_{_{\scriptsize{\mathscr{O}_s}}}(y)p_\textbf{y}(y)}{p_\textbf{s}(s)}\ ,
$$
and the presence of the characteristic function tells us that it vanishes when $\ y\ $ lies outside the orthant $\ \mathscr{O}_s\ $.  The joint probability mass function-density function $\ p_{\textbf{s},\textbf{y}}\ $ of $\ \textbf{s}\ $ and $\ \textbf{y}\ $ is just the numerator of the fraction on the right of the equation immediately above:
$$
p_{\textbf{s},\textbf{y}}(s,y)=\chi_{_{\scriptsize{\mathscr{O}_s}}}(y)p_\textbf{y}(y)\ ,
$$
so if we multiply both sides of that equation by $\ p_\textbf{s}(s)\ $, we get
$$
p_{\textbf{s},\textbf{y}}(s,y)=p_\textbf{s}(s)p_{\textbf{y}|\textbf{s}}(y|s)\ ,
$$
which is just the authors' equation $(2)$ in slightly less ambiguous notation.
