for Knot Diagrams

Andrew Rechnitzer

University of British Columbia

University of British Columbia

hchapman.github.io/talks/amssf_markov

Special Session on Mathematical Methods for the Study

of the Three Dimensional Structure of Biopolymers

AMS 2018 Fall Western Sectional Meeting

SFSU, San Francisco CA

October 28^{th} 2018

**Crossings** are the primary components of knot diagram models

Crossings may be viewed as **self-contacts** where enzymes may act to change DNA topology

Strand passage action, *e.g.* topo-IV

Coherent smoothing action, *e.g.* XerCD-*dif*-FtsK complex

**No known algorithms** for **directly sampling** knot diagrams uniformly

Related to **lack of exact enumeration** \(\{k_n\}\) for knot diagrams

Sample 4-valent maps uniformly, but only accept knot diagrams

- Samples diagrams of
**specified size**\(n\) - Distribution is
**exactly uniform**across a size \(n\) - Knots are
**rare**; most samples**rejected** - Knots of
**fixed type**are**exponentially rare**among all knots

Sample states from Markov process that explores knot diagrams

- Samples diagrams of
**all possible sizes** - Stationary distribution
**approximately uniform**across any given size **Only knot diagrams**are sampled- Extends to sampling diagrams
**of any fixed type**

One step of a **diagram Markov chain** takes as input a knot diagram, performs with some probability a **Reidemeister transition**, and returns the resulting knot diagram

**Aperiodic** as there is always a chance a transition fails

**Connected** as all valid transitions have nonzero probability and;

We weight transition probabilities to enforce **detailed balance**, that
\[ P(D \to N) \pi(D) = P(N \to D)\pi(N) \]

So the Markov chain is **ergodic**

Given *a priori* approximate enumeration data \(\{g_n\}\) so that \(g_n \approx k_n\):

Only perform transitions from \(n\)-crossing diagrams to \(m\) crossing diagrams with probability \(g_n/g_m\)

The approximate enumeration \(\{g_n\}\) can be calculated iteratively using the Markov process itself

Knot diagrams are sampled

**uniformly for any given size**, and- approximately
**each size is equally likely**

Shadow Markov chan is nicer than fixed knot type Markov chain;

The shadow Markov chain is connected with maximum size limit

Explore statistics for knot shadows and convergence of distribution

Gauss diagram animation for 10000 attempted transition steps

Check distribution validity by comparing statistics:

In limit, \(\frac 13\) of faces in 4-valent maps are monogons

Find that both samples of **knot shadows** have similar counts of monogons, both different from **all maps**

Normalize statistics: Subtract off limit linear behavior for all maps

Similar to monogons, we get linear behavior for all other face degrees

Both knot shadow samplers yield similar counts

Normalize statistics: Subtract off limit \(y = n p_{k}\) behavior of all maps

\(n\) | 4-valent \(p_k\) | MCMC \(p_k\) |
---|---|---|

1 | \(\tfrac 13 = 0.\overline{3}\) | \(0.35036 \pm 4(10^{-5})\) |

2 | \(\tfrac 16 = 0.1\overline{6}\) | \(0.14056 \pm 3(10^{-5})\) |

3 | \(\tfrac {13}{108} = 0.12\overline{037}\) | \(0.12257 \pm 3(10^{-5})\) |

4 | \(\tfrac {55}{648} \approx 0.08488\) | \(0.08298 \pm 2(10^{-5})\) |

2-gons and 4-gons are **more rare** in knot shadows; all other faces are more common

The **average \(v_2\) invariant** over all crossing assignments of a plane curve is a spherical curve invariant

In agreement with quadratic growth in the Petaluma model (Even Zohar *et al.* '16); \(m\) petals can correspond to \(O(m^2)\) crossings

Normalize statistics: Subtract off least-squares linear fit

Efficiency and speed of convergence is related to classical questions

Viewing Markov chain as "BFACF for diagrams" suggests experiments on diagrams, such as:

H. Chapman and A. Rechnitzer. *A Markov chain sampler for plane curves*. Submitted.