element $x$ from the set $S$ with the successful probability $P(x=a)=\frac{w(a)}{M}$, where $w(a)$ is the weight of $a\in S$, and failing probability $P(x\notin
S)=1-\frac{\sum_{b\in S}w(b)}{M}$. At each time, if a random element $a$ is successfully selected from $S$, we say acceptance or $a$ is accepted, and if no element is selected from $S$, we say rejection. Hence, at each time the probability of acceptance is $\frac{\sum_{b\in S}w(b)}{M}$ and probability of rejection $1-\frac{\sum_{b\in S}w(b)}{M}$. With some fundamental statistical knowledge, the total weight of $S$ can be approximated by multipling $M$ and the ratio of acceptance over all the samplings. For our purpose, generalized Bregman’s bound in Lemma 5 provides such a suitable large $M$, and self-reducing method for counting Hamiltonian cycles naturally proposes such a sampling procedure, which is sequential sampling procedure guaranteed by Lemma 4. For more details about sequential acceptance/rejection method, we refer to [@HL08].

In order to make use of the generalized Bregman’s bound in Lemma 5, before resuming the acceptance/rejection algorithm, we need to scale the matrix $A_G$ to nearly be doubly stochastic and make each entry in \[0,1\][@KK96]. Hence the algorithm has two phases.\
\
**Sub Algorithm I. Scale Matrix**\
$Input:$ $A_G$, $\varepsilon$\
$Output:$ $X$, $Y$, 