notation in SHC procedure, then $C^{i+1}=(C^{i}_{j_i1})^{'}$, $i=1,\cdots,n-1$ and $C^1=C$, we have\
$$P(\pi(k)=j_k)=
\frac{C^k(j_k,1)Br((C^k_{j_k1})^{'})}{Br(C^k)},$$ where $k=1,2,\cdots,n-1$ and $P(\pi(n)=j_n)=\frac{C^n(j_n,1)}{Br(C^n)}$.\
Since the selection at each level in Step 6 is independent of the other, the probability of selecting $\mathcal {H}_1$ is the telescoping product. Noting that $C^{i+1}=(C^{i}_{j_i1})^{'}$, $i=1,\cdots,n-1$ and $C^1=C$, then\
$$\begin{split}
P(H=\mathcal{H}_1)&=P(\pi=j)=\prod\limits^n_{k=1}P(\pi(k)=j_k)
=\frac{\prod_{i=1}^{n}C^i(j_i,1)}{Br(C)} =\frac{W(\mathcal
{H}_1)}{Br(C)}.
\end{split}$$

Since each Hamiltonian cycle in $G_C$ can be accepted with certain probability proportional to its weight, the acceptance set $S$ is the set of all the Hamiltonian cycles in $G_C$. Then $$P(H\in S)=\sum\limits_{\mathcal{H}\in
G_C}P(H=\mathcal{H})=\frac{W_H(G_C)}{Br(C)}.$$ Hence, $$P(H=\mathcal{H}_1|H\in S)=\frac{W(\mathcal{H}_1)}{W_H(G_C)}.$$

In Sub Algorithm II, let $x_k$, $1\leq k\leq t$, denote the indication function of acceptance or rejection in Step 6, that is, $x_k=1$ if a Hamiltonian cycle is accepted and $x_k=0$ otherwise. Obviously, $x_k$, $1\leq k\leq t$, are i.i.d. Bernoulli random variables with $P(x_1=1)=p=W_H(G_C)/Br(C)=\operatorname{ham}(C)/Br(C)$. Let $A^{\varepsilon}_G$ be the matrix obtained in Step 1 of Sub Algorithm I. Hence, by Lemma 6 and noting $t=4N(\varepsilon/2)^{-2}\log(\delta^{-1})$, where $N=Br(C)/\operatorname{ham}(C)$, a simple calculation shows $$P((1-\varepsilon/2)\operatorname{ham}(A^{\varepsilon}_G)\leq
\widetilde{\operatorname{ham}}(A_G)\leq
(1+\varepsilon/2)\operatorname{ham}(A^{\varepsilon}_G))\geq
1-\delta.$$ Noting $\operatorname{ham}(A_G)\leq
\operatorname{ham}(A^{\varepsilon}_G)\leq
(1+\varepsilon/3)\operatorname{ham}(A_G)$, thus the proof completes.   $\Box$\
\
\
****\
\
*4.1. Complexity of the Algorithm*

Due to ellipsoid method[@KK96], the running time of matrix scaling is $O(n^4\log n)$. So the complexity of 