Random Walker Problem

Question

Consider a random walker on a square lattice. At each step the random walker moves to a nearest neighbor site with equal probability for each of the four sites. The walker starts at the origin and takes 3 steps. The probability that during this walk no site is visited more than once is?

Any help regarding this will be helpful, as I cannot make any head through.

Update

After some thought I have come up with this solution.

So I am at a particular location on this square lattice. The moves that I have are U(Up), D(Down), L(Left) and R(Right), to move onto the next lattice site. For $3$ moves of the random walker, a possible move string will be RRL. And with the additional condition that, no one site is visited more than once we can make the observation that if a move is immediately followed by its reverse move, then a site is visited exactly once for a $3$ move random walk. With these basics, we can now begin the calculation.

So since a move has to followed by its reverse move, RL/LR and UD/DU will always be in the move string ###. For say UD, the string will be UD#, where # can be anything out of $4$ possible choices. The move string can be rearranged amongst themselves $2!$ times. And UD itself can rearranged amongst themselves $2!$ ways. So the total ways this particular UD/DU string can be rearranged is $2! \times 2! \times 4 = 16$. Similarly for the LR/RL string we have $16$ ways of rearrangement.

So the total possibles routes for a single revisit to any particular lattice point is $16 + 16 = 32$. And the total possible routes are $4^3$. So our required probability is $\frac{32}{4^3} = \frac12$.

Can someone go through and let me know where am I making a mistake, as I think the answer is a bit unreasonable. As $50 \%$ of time we revisit a site. Sounds absurd.

Answer 1

The problem is that with your current solution, you're counting some paths multiple times. It's true that there are $8$ paths whose directions contain the substring UD (either .UD or UD.) and similarly $8$ paths containing each of DU, LR, and RL. But there are not $32$ of these total, because UDU, DUD, RLR, and LRL are counted twice.

So there are $28$ distinct paths, for a probability of $\frac{28}{64} = \frac{7}{16}$ that some site is revisited, and a probability of $\frac{9}{16}$ that all visited sites are distinct.

Another way to obtain the same answer is that no matter what the first step is, on the second step there is a $\frac34$ probability of not retracing the first step, and on the third step there is a $\frac34$ probability of not retracing the second step. These are independent, so the probability is $\left(\frac34\right)^2 = \frac{9}{16}$ that all visited sites are distinct.