Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.07564 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912005775949824 |
|---|---|
| author | Păun, Udrea |
| author_facet | Păun, Udrea |
| contents | The pivot algorithm -- we also call it the pivot chain -- is an algorithm for approximately uniform sampling from $Ω_{N},$ the set of $N$-step self-avoiding walks on $\mathbb{Z}^{d}$ ($N,$ $d\geq 1$). Based on this algorithm and the $G$ method, we construct another algorithm/chain, called the pivot$^{\text{+}}$ algorithm/chain, for approximately uniform sampling from $Ω_{N},$ here, $N\geq 2$. The pivot$^{\text{+}}$ algorithm samples the pivot from the set $\left\{ 1,2,...,N-1\right\} $ according to the uniform probability distribution on this set while the pivot algorithm samples the pivot from the set $\left\{0,1,2,...,N-1\right\} $ according to the uniform probability distribution on this set, so, on the pivot, the pivot$^{\text{+}}$ algorithm is better than the pivot algorithm. Further, we obtain another important thing, namely, the pivot$^{\text{+}}$ algorithm/chain enters, at time $1$, a set $2d$ times smaller than $Ω_{N},$ and stays forever in this set, so, at times $1,2,...$ we work with a chain having a state space $2d$ times smaller than $Ω_{N}$. As to the speed of convergence, we conjecture that the pivot$^{\text{+}}$ algorithm/chain is faster than the pivot algorithm/chain. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_07564 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | $G$ Method in Action: Pivot$^{\text{+}}$ Algorithm for Self-avoiding Walk Păun, Udrea Probability The pivot algorithm -- we also call it the pivot chain -- is an algorithm for approximately uniform sampling from $Ω_{N},$ the set of $N$-step self-avoiding walks on $\mathbb{Z}^{d}$ ($N,$ $d\geq 1$). Based on this algorithm and the $G$ method, we construct another algorithm/chain, called the pivot$^{\text{+}}$ algorithm/chain, for approximately uniform sampling from $Ω_{N},$ here, $N\geq 2$. The pivot$^{\text{+}}$ algorithm samples the pivot from the set $\left\{ 1,2,...,N-1\right\} $ according to the uniform probability distribution on this set while the pivot algorithm samples the pivot from the set $\left\{0,1,2,...,N-1\right\} $ according to the uniform probability distribution on this set, so, on the pivot, the pivot$^{\text{+}}$ algorithm is better than the pivot algorithm. Further, we obtain another important thing, namely, the pivot$^{\text{+}}$ algorithm/chain enters, at time $1$, a set $2d$ times smaller than $Ω_{N},$ and stays forever in this set, so, at times $1,2,...$ we work with a chain having a state space $2d$ times smaller than $Ω_{N}$. As to the speed of convergence, we conjecture that the pivot$^{\text{+}}$ algorithm/chain is faster than the pivot algorithm/chain. |
| title | $G$ Method in Action: Pivot$^{\text{+}}$ Algorithm for Self-avoiding Walk |
| topic | Probability |
| url | https://arxiv.org/abs/2310.07564 |