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](http://en.wikipedia.org/wiki/Presentation_of_a_group#Common_examples))? 



In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?
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.


