14
$\begingroup$

This question is a variation of the return to the origin problem.

Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = (a \pm 1, b)$ or $(a , b \pm 1)$, with a uniform probability (i.e. a uniform random walk on $G$).

Let $P_n(r)$ be the probability that $\{T^{s}(0,0) \ \vert \ 1 \le s \le r \} = G$.
So of course $P_n(r) = 0$ iff $r < n^{2}$ and $P_n(r)$ is increasing with $r$.

Let $R_n$ be the number such that $P_n(R_{n}-1)<1/2$ and $P_n(R_{n}) \ge 1/2$.
Note that $R_n$ is hard to compute by brute-force: $R_1 = 1$, $R_2 = 6$, $R_3 = 13$(?).

Question: What is the value of $R_n$?
A formula would be great, but I'm ok with an evaluation.

Remark: This question generalizes to any finite group together with a presentation, and we get an invariant of the group as the maximum for all the presentations, of such number of steps.
For $G = \mathbb{Z}/n$ with the presentation $\langle a \vert a^{n} \rangle$ we get $R_n=1,2,3,6,10,14,19 \dots$ a general formula?
What do we get for the groups $D_n$, $S_n$, $A_n$, $B_n \dots$ (see the common examples)?

$\endgroup$
  • $\begingroup$ Could I ask is there any chance this question arose in relation to the Sekine quantum groups? $\endgroup$ – JP McCarthy May 4 at 5:47
24
$\begingroup$

The quantity $R_n$ is asymptotic to ${4\over \pi}(n\log n)^2$, see "Cover times for Brownian motion and random walks in two dimensions" by Dembo, Peres, Rosen and Zeitouni. This was previously conjectured by Aldous.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.