Expand all Collapse all | Results 1 - 2 of 2 |
1. CJM 2011 (vol 64 pp. 961)
Densities of Short Uniform Random Walks We study the densities of uniform random walks in the plane. A special focus
is on the case of short walks with three or four steps and less completely
those with five steps. As one of the main results, we obtain a hypergeometric
representation of the density for four steps, which complements the classical
elliptic representation in the case of three steps. It appears unrealistic
to expect similar results for more than five steps. New results are also
presented concerning the moments of uniform random walks and, in particular,
their derivatives. Relations with Mahler measures are discussed.
Keywords:random walks, hypergeometric functions, Mahler measure Categories:60G50, 33C20, 34M25, 44A10 |
2. CJM 2007 (vol 59 pp. 828)
Non-Backtracking Random Walks and Cogrowth of Graphs Let $X$ be a locally finite, connected graph without vertices of
degree $1$. Non-backtracking random walk moves at each step with equal
probability to one of the ``forward'' neighbours of the actual state,
\emph{i.e.,} it does not go back along
the preceding edge to the preceding
state. This is not a Markov chain, but can be turned into a Markov
chain whose state space is the set of oriented edges of $X$. Thus we
obtain for infinite $X$ that the $n$-step non-backtracking transition
probabilities tend to zero, and we can also compute their limit when
$X$ is finite. This provides a short proof of old results concerning
cogrowth of groups, and makes the extension of that result to
arbitrary regular graphs rigorous. Even when $X$ is non-regular, but
\emph{small cycles are dense in} $X$, we show that the graph $X$ is
non-amenable if and only if the non-backtracking $n$-step transition
probabilities decay exponentially fast. This is a partial
generalization of the cogrowth criterion for regular graphs which
comprises the original cogrowth criterion for finitely generated
groups of Grigorchuk and Cohen.
Keywords:graph, oriented line grap, covering tree, random walk, cogrowth, amenability Categories:05C75, 60G50, 20F69 |