Use of Statistically Leinert Sets to Calculate Return Probabilities of Random Walks in $\mathbb{F}_{s_{1}}\times\mathbb{F}_{s_{2}}$

Random walks have been studied extensively, but some interesting properties arise when restricting to trees. A tree in graph theory is defined as a finite graph which is undirected and connected, lacks cycles, and stems from a root. As we are considering an unbiased walk, so in terms of the elements of the string, they are equally likely to appear. In the graph sense, the movement in any direction is equally likely. In Figure 1, a sample random walk generated by a, b is shown. Random walks in $\mathbb{F}_{s_{1}}\times\mathbb{F}_{s_{2}}$ which we consider here in this paper can be thought of as a product of one dimension walks. As dimensions increase, the walk can become more complex. An intuitive question then arises: what is the return probability of the walk to the origin? It has been established that random paths on mathematical trees with a number n generators can be expressed using matrices. These paths can either return to the origin or diverge with no way back. This divergence behavior can be understood by studying the radius of convergence.

In 1976, Akemann and Ostrang [1] introduced norms of operators on the Hilbert space: $L^{2}(G)$, where elements can be written as generally infinite linear combinations acting on the space by left multiplication. In 1986, Woess [4] presented work on calculating Norms of Free Convolution Operators, using generating functions to represent return probabilities of random walks on a homogeneous tree of degree 2s. In 2007, M.B. Hastings [2] first presented bounds on Haar Random Matrices. His work analyzed random walks on a Cayley Tree and specifically considered it for the Hermitian Case. A Cayley Tree [3] is an interesting case of trees in graphs, where each non-leaf vertex (i.e. a vertex with no children vertices) has a constant number of vertices stemming from it. For example, a 2-Cayley tree will have 2 vertices stemming from each leaf vertex. This work by Hastings provided the main motivation for the paper presented here.

For the purposes of this paper the walks are unbiased. In this paper these paths were represented using ”words”, i.e. strings generated from an n number of generators. The set of all possible words can be represented as a set S which forms an algebraic group: the free group: F. We modified a key property, known as the Leinert property, to be imposed on this group. We instead applied a Statistically Leinert Property.

Here we consider $G=\mathbf{F}_{1}\times\mathbf{F}_{1}\times\mathbf{F}_{1}=\mathbb{Z}^{3}$, with $X=\{x,y,z\}$ the set of generators for the group. Note that the smallest bad string has length 6, with an example given by

• •

  For $2n=6$, we simply consider every possible arrangement of strings of the above kind. This is just the total number of permutations of a set of three elements, so $b_{6}=3!=6$ total bad strings.

• •

  For $2n=8$, we cannot have kernel substrings of length 8, so the only possibility is to conjugate by an element to get a string $S_{10}=w^{-1}\tilde{S}_{8}w$. $w$ is determined by the ends of $S_{8}$, leaving only one option per string. So again, there are exactly $b_{8}=6$ bad strings of length 8.

• •

  For $2n=10$, we expect that there are 42 bad strings in total. We can construct these in a few ways. First, we take any bad string of length 8 and append a letter to both sides, yielding 12 options. The rest are given by considering

Here is an attempt to create an upper bound. Every string is represented with three walks on each axis of the lattice. For the positive steps, we have a total of $n=n_{x}+n_{y}+n_{z}$ steps to travel. We pick where these go, giving a $\binom{n}{n_{x},n_{y},n_{z}}$ factor. For the remaining spots, we have to decide where the other factors go.

Here we consider $G=\mathbf{F}_{s_{1}}\times\mathbf{F}_{s_{2}}$, with $X=\{x_{1},\ldots,\}$. Note that the smallest bad string has length 8, with an example given by

• •

  For $2n=8$, the total number of bad strings is $\boxed{b_{8}=2s_{1}(s_{1}-1)s_{2}(s_{2}-1),}$ as we can pick anything for $x_{1}$ and $y_{1}$, with $x_{2}$ and $y_{2}$ constrained such that they are not $x_{1}$ and $y_{1}$ respectively. We can also invert the string, providing the factor of 2.

• •

  For $2n=10$, we can use every single string from before and append elements to the end that cancel each other out. Using the kernel form for $S_{8}$ (string of length 8), we can let $\bar{S}=z_{1}^{-1}S_{8}z_{1}$, where $z_{1}\in X$ and $z_{1}\neq x_{1}$ or $y_{2}$. So we have $s-2$ choices for $z_{1}$. There are no other strings of this size that we can consider.

• •

  A general strategy for counting the total number of bad strings of a given length is to sum over the size of the smallest bad substring.

Consider the case where $\alpha_{ij}=a$ are all the same, say $a=\frac{1}{2s}$, for the group $G=\mathbf{F}_{s}\times\mathbf{F}_{s}$. In addition, by symmetry we can argue that the functions $D_{ij}=D$ are all the same. Then we have that $G(z)=Q_{R}(z,G(z))$ is given by the equation

where $Q_{R}$ is to denote replacing $D(z)$ with $\frac{z^{2}}{R^{2}-z^{2}}$, since $D(z)\leq\frac{z^{2}}{R^{2}-z^{2}}$. Therefore $Q(z,t)\leq Q_{R}(z,t)$. Moving terms to the other side and squaring gives us

This yields a quadratic equation in $G$, namely $AG^{2}+BG+C=0$, where

Therefore $G=\frac{1}{2A}(-B\pm\sqrt{B^{2}-4AC})$, and as a power series $G$ returns real values for all values of $z$, so we can solve for the radius of convergence as $B^{2}-4AC=0$:

Expanded out, the equation is

This equation in $z$ yields the radius of convergence for $G$, assuming that $z<R$. Here is an example plot comparing the curves $y=\left(2\sqrt{2x-1}\right)^{-1}$ and $(x,y)=(s,z)$, where $(x,y)$ satisfy the cubic equation above:

The purple points in the plot show numerically computed radii of convergence using the following method. Let $(U_{1},\ldots,U_{s})\in\operatorname{U}(N)$ and $(V_{1},\ldots,V_{s})\in\operatorname{U}(N)$ be Haar randomly sampled unitary matrices. Then the dots are given by computing the quantity $z^{-1}=\|a\sum_{i}U_{i}\otimes I+I\otimes V_{i}\|$, with $\|.\|$ the 2-norm. Here each point is given by averaging over 4 computations, $a=1$, and $N=75$.

More generally, if we had some unknown function $D$, then we can use the quadratic formula once more to find the relation for $D$:

The sign is indeterminate as $D$ cannot be determined. If $D=0$, then we get $z^{-1}=2a\sqrt{2s-1}$ as expected.

Note that in the above equation, it is quadratic in $R^{2}$, which we can solve as

Let $\beta^{(2n)}$ denote the number of bad strings of length $2n$ for a set $X\subset G$, and let $\mathcal{B}^{(2n)}=\frac{\beta^{(2n)}}{s(s-1)^{2n}}$ be the frequency of bad strings of length $2n$. Say that $G=\mathbf{F}_{s}\times\mathbf{F}_{s}$, with $X$ the generator set. We have an upper bound on $\beta^{(2n)}$ that goes to 0 as $s\to\infty$, therefore so does $\beta^{(2n)}$. Recall from the definition of $d_{ij}^{(2n)}$ that only bad strings contribute to a nonzero quantity, so we can say that $D_{ij}(z)=\frac{c^{2}z^{2}}{1-c^{2}z^{2}}$, where $c$ is the asymptotic exponential rate of encountering these strings. Therefore $c<c_{\text{max}}$, where $c_{\text{max}}$ is the exponential rate of encountering any kind of bad string. Since $c_{\text{max}}\to 0$, so does $c$, and therefore $D_{ij}(z)\to 0$ as we increase $s$. More conveniently, given some fixed uniform constant for all of the coefficients of $\alpha$, we expect that the radius of convergence for $G(z)$ will be $r^{-1}\sim 2a\sqrt{2s-1}$.

Take for example $G=\mathbb{Z}^{s}$. The norm for $\alpha$ with all coefficients set to 1 is $\|\alpha\|=s$. I expect that the frequency of bad strings does not vanish as we increase $s$, and in fact we have some nice asymptotic relation.

In the Woess paper, they show that $r^{-1}=P(\theta)/\theta=\min\{P(t)/t:t\geq 0\}$, or $r=\max\{t/P(t):t\geq 0\}$, where

Another approach is to state that since $G(z)=P(zG(z))$, the radius of convergence is bounded by $G(z)$ having a finite derivative, and so if the graph of $G(z)$ has a vertical slope for a finite $G(z)$ value, then that could also be the radius of convergence. Suppose that $y=P(xy)$, then the derivative is given by

Letting $y^{\prime}\to\infty$, we must have that

Note that the first term simplifies to

One option here is to just explicitly solve for the curve for $G(z)$ where we can. If all the constants are $\alpha_{i,j}$ and we do not have the identity, then this simplifies a lot:

Here are some examples of bad strings, to show that they exist for groups of the form $G=\mathbf{F}_{s_{1}}\times\ldots\times\mathbf{F}_{s_{m}}$, where $s_{i}\in\mathbb{N}$ for all $i$. If $m=1$, then the set $X$ of generators for $G$ is a Leinert set, as they have no nontrivial algebraic relations. If $m\geq 2$, then we run into problems.

1. (1)

   Consider $G=\mathbf{F}_{s_{1}}\times\mathbf{F}_{s_{2}}$, which has the generator set $X=\{x_{1},\ldots,x_{s_{1}},y_{1},\ldots,y_{s_{2}}\}$. Here in this group the $x$’s commute with the $y$’s. If $s_{1}$ and $s_{2}$ are greater than 1, then we can let $S$ be the string

   $$S=x_{1}^{-1}x_{2}y_{1}^{-1}y_{2}x_{2}^{-1}x_{1}y_{2}^{-1}y_{1}=e.$$

2. (2)

   Consider $m\geq 3$, then for this group we can consider the string

   $$S=x_{1}^{-1}y_{1}z_{1}^{-1}x_{1}y_{1}^{-1}z_{1}=e,$$

   where $x_{1}$, $y_{1}$, and $z_{1}$ are generators associated with three different copies of a free group in the total group $G$.

There are some cases that do provide Leinert sets.

1. (1)

   If $G=\mathbf{F}_{1}\times\mathbf{F}_{1}$, then the generator set $X=\{x,y\}$ is Leinert, as the only way for $x_{i}\neq x_{i+1}$ is if $x_{i}=x$ for all odd $i$ and $x_{i+1}=y$, and vice versa.

2. (2)

   Similarly to before, $G=\mathbf{F}_{1}\times\mathbf{F}_{2}$ is also Leinert.

A primary method of showing that $X$ is statistically Leinert is to construct an upper bound on $b_{2n}$. Here is one way to count the number of bad sets, possibly construct upper bounds for $b_{2n}$ in the case $G=\mathbf{F}_{s_{1}}\times\mathbf{F}_{s_{2}}$:

1. (1)

   Consider the string from the previous subsection,

   $$S=x_{1}^{-1}x_{2}y_{1}^{-1}y_{2}x_{2}^{-1}x_{1}y_{2}^{-1}y_{1}=e.$$

   We consider all strings of this length and form that equal the identity. We have to pick two different generators each (and we can swap the $x$’s and $y$’s in their role), which leads to a total of $2s_{1}(s_{1}-1)s_{2}(s_{2}-1)$ different strings of that form. Let’s call this form the kernel string.

2. (2)

   An alternative upper bound is the following, which is a very loose bound. The total number of walks of length $2n$ on the free group of $s$ generators from the identity to the identity is bounded by $(2s-1)^{n}\binom{2n}{n}$.

Consider $s_{1}=s_{2}=2$. This does not form a Leinert set due to the arguments from before,

For some numerics on the number of bad strings in various cases, consider the group $G$ from before. For strings of length $2n<8$, there are no bad strings. Here are some computations on the exact number of bad strings, or at least tight lower bounds. For notation purposes, if $S$ is a valid string of the form

then define the conjugate string $\tilde{S}$ to be

• •

  For $2n=8$, we established that $b_{8}=2s_{1}(s_{1}-1)s_{2}(s_{2}-1)$.

• •

  For $2n=10$, we can use every single string from before and append elements to the end that cancel each other out. Using the kernel form for $S_{8}$ (string of length 8), we can let $\tilde{S}=z_{1}^{-1}S_{8}z_{1}$, where $z_{1}\in X$ and $z_{1}\neq x_{1}$ or $y_{2}$. So we have $s-2$ choices for $z_{1}$. We can also consider strings of the form

  $$S_{10}=x_{1}^{-1}w_{2}x_{4}^{-1}y_{1}y_{2}^{-1}x_{4}w_{2}^{-1}x_{1}y_{2}^{-1}y_{1}=e.$$

• •

  For $2n=12$, we can use any string from $b_{10}$ or use strings of the following form:

  $$S_{12}=x_{1}^{-1}w_{2}w_{3}^{-1}x_{4}y_{1}^{-1}y_{2}x_{4}^{-1}w_{3}w_{2}^{-1}x_{1}y_{2}^{-1}y_{1}=e.$$

  Given a kernel string $S_{8}$, we can look at strings of the form $z_{1}^{-1}z_{2}S_{8}z_{2}^{-1}z_{1}$, where we choose $z_{1}$ and $z_{2}$. $z_{2}$ has $s-2$ options, so $z_{1}$ has $s-3$ options. For strings of the form $S_{10}$, we have $b_{8}$ times the number of options for $w_{2}$ and $w_{3}$, which is hard to determine.

  • –

    If $w_{2}=x_{4}$, then $w_{3}$ has $s-1$ options. If $w_{3}=x_{1}$, then $w_{2}$ has $s-1$ options.

  • –

    Otherwise, $w_{2}$ has $s-2$ options from not equaling $x_{4}$ and $w_{3}$ has $s-2$ options as well.

  We multiply by 2 again since we can also place the $w$’s between the $y$’s instead, so we have

  $$b_{12}=b_{8}[(s-2)(s-3)+4(s-1)+2(s-2)^{2}]$$

• •

  In general, given $b_{2n}$, we have two options:

  1. (1)

     We can take a bad string $S_{2n-2}$ and conjugate by a letter $z$, giving $(s-2)$ strings.

  2. (2)

     We can produce a bad string that has no bad substrings. The number of these is hard to find.