# On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
## Appendix A Omitted Proofs
### Proof of Lemma 2  
The proof uses the path coupling method, which is a fundamental technique in the theory of Markov chains [61]. Before getting to the proof of Lemma 2, let us start by recalling some useful notions and set some notation. * **Distance and neighbors on the hypercube**: Denote by \(\mathcal{X}=\{0,1\}^{M}\) the \(M\)-dimensional hypercube. \(\mathcal{X}\) has a natural graph structure: two vertices \(\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}\) are neighbors, denoted \(\boldsymbol{x}\sim\boldsymbol{x}^{\prime}\), iff they differ in exactly one coordinate. Denote by \(\mathbf{d}_{\text{H}}(\cdot,\cdot):\mathcal{X}\times\mathcal{X}\to[0,\infty)\) the Hamming distance: \[\mathbf{d}_{\text{H}}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\sum_{i=1}^{M} \mathbf{1}_{x_{i}\
eq x_{i}^{\prime}}\,.\] Of course, Hamming distance coincides with the shortest path distance with respect to the graph structure on \(\mathcal{X}\). * **Coupling:** Let \(X\) and \(X^{\prime}\) be two random variables taking values on \(\mathcal{X}\). Denote by \(\mathbb{P}_{X}\) and \(\mathbb{P}_{X^{\prime}}\) the laws of \(X,X^{\prime}\), respectively. A coupling between \(X,X^{\prime}\) is a probability distribution \(\mathbb{P}_{X,X^{\prime}}\) on \(\mathcal{X}\times\mathcal{X}\), whose \(X\)-marginal is \(\mathbb{P}_{X}\) and \(X^{\prime}\)-marginal is \(\mathbb{P}_{X^{\prime}}\). In other words, a coupling is an embedding of two random variables onto a joint probability space, defined by a joint law. **Notation. ** For \(\boldsymbol{x}\in\mathcal{X}\), let \(X_{\boldsymbol{x}}\) be the \(\mathcal{X}\)-valued random variable whose law corresponds to running one step of Glauber dynamics, starting from the initial state \(\boldsymbol{x}\) (using the notations of Algorithm 1, one has \(\boldsymbol{x}^{(0)}=\boldsymbol{x}\) and so \(X_{\boldsymbol{x}}\stackrel{{ d}}{{=}}\boldsymbol{x}^{(1)}\), where \(\stackrel{{ d}}{{=}}\) indicates equality in distribution). The following result follows from ([61], Corollary 14.7):  
**Theorem A1**. : _Suppose that there is \(0\leq\eta<1\) with the following property: for any two neighbors \(\boldsymbol{x}\sim\boldsymbol{x}^{\prime}\), there exists a contracting coupling of \(X_{\boldsymbol{x}}\) and \(X_{\boldsymbol{x}^{\prime}}\) with_  
\[\mathbb{E}[\mathbf{d}_{\text{H}}(X_{\boldsymbol{x}},X_{\boldsymbol{x}^{\prime} })]\leq\eta\,.\]  
_Then, for any initial state \(\boldsymbol{x}^{(0)}=\boldsymbol{x}\) and \(t\geq 1\), one has_  
\[\mathbf{d}_{\text{TV}}\Big{(}\mathbb{Q}^{(t)},\mathbb{Q}^{(\infty)}\Big{)} \leq M\cdot\eta^{t}\,.\]_Here, \(\mathbb{Q}^{(t)}\) is the law of \(\mathbf{x}^{(t)}\), the state of Glauber dynamics at time \(t\), starting from \(\mathbf{x}^{0}=\mathbf{x}\), and \(\mathbb{Q}^{(\infty)}\) is the stationary distribution._  
The proof of Lemma 2 follows by constructing a contracting coupling between \(X_{\mathbf{x}}\) and \(X_{\mathbf{x}^{\prime}}\) for any \(\mathbf{x}\sim\mathbf{x}^{\prime}\), and applying Theorem A1. The construction proceeds as follows. Let \(\mathbf{i}\sim\text{Uniform}([M])\) be a random coordinate to update. For all \(\ell\in[M]\), let  
\[q_{0}(\ell)=\exp\biggl{\{}-\frac{1}{2\sigma^{2}}\|\mathbf{y}-A\mathbf{x}_{\ell=0}\|^{2 }\biggr{\}},\quad q_{1}(\ell)=\exp\biggl{\{}-\frac{1}{2\sigma^{2}}\|\mathbf{y}-A \mathbf{x}_{\ell=1}\|^{2}+\lambda\biggr{\}},\]  
and  
\[p_{1}(\ell)=\frac{q_{1}(\ell)}{q_{0}(\ell)+q_{1}(\ell)}=\varphi\biggl{(} \lambda+\frac{1}{2\sigma^{2}}\Bigl{\{}\|\mathbf{y}-A\mathbf{x}_{\ell=0}\|^{2}-\|\mathbf{y}- A\mathbf{x}_{\ell=1}\|^{2}\Bigr{\}}\biggr{)}\,,\]  
where \(\varphi(x)=1/(1+e^{-x})\) is the logistic function. Let \(p_{1}(\ell)^{\prime}\) be defined similarly, with \(\mathbf{x}\) replaced by \(\mathbf{x}^{\prime}\). To obtain \(X_{\mathbf{x}}\) and \(X_{\mathbf{x}^{\prime}}\), sample \(U\sim\text{Uniform}[0,1]\), independent of \(\mathbf{i}\).