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)?
Best Answer
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.