A puzzle on a square

I had cause to revisit an old @edsouthall tweet:

Random Walk Problem #1
Tricky… pic.twitter.com/RfHA0ntSCg

— Ed Southall (@edsouthall) May 20, 2016

It’s a nice puzzle. Try it yourself! Spoilers below the line.

As a clarification: the square drawn must have the starting point as its top left corner.

---

My approach

Given that you’re at one corner of the square, you always have two moves that will keep you on the square. The probability of every one of the eight moves remaining on the square is ${\left(\frac{1}{2}\right)}^8=\frac{1}{256}$. But we also need to make sure we cover all four edges. How do we do that, given that we stay on track?

Up to rotation/reflection, there are only six possible states we can be in (after we’ve made at least one move). I’m going to adopt a convention of a * showing where the dot is, and a - showing the edges drawn so far.

There’s one four-edge state ($D$), which is an absorbing state: once you’re there, you stay there.

There are two three-edge states: —* ($C$, where you’re in an end spot) and –*- ($c$, where you’re in one of the middle spots).

—* moves to the four-edge state and to –*- with equal probability; –*- stays put and moves to —* with equal probability.

There are two two-edge states: –* ($B$) and -*- ($b$). –* moves to —* and to -*- with equal probability; -*- always moves to –-*.

And there is one one-edge state: -* ($A$) is equally likely to become –* and to remain in place.

What I did was to meticulously catalogue where I could be after each move and spot that in 63 of the 128 possible cases, I ended up in state $D$. But that’s oddly unsatisfying.

Transition matrices

But hang on a second! Going from one state to another with specified probabilities… that’s how the googles work! I can write down a matrix of probabilities like this:

$\mathbf{M}=\left(\begin{array}{cccccc}h& 0& 0& 0& 0& 0\\ h& 0& 1& 0& 0& 0\\ 0& h& 0& 0& 0& 0\\ 0& h& 0& 0& h& 0\\ 0& 0& 0& h& h& 0\\ 0& 0& 0& h& 0& 1\end{array}\right)$,

with $h=\frac{1}{2}$. Each column represents the probability of ending up in state $A$, $B$, $b$, $C$, $c$ or $D$ from each of those positions in the same order. (For example, the fourth column shows that if you’re in position $C$, you have equal probabilities of reaching positions $c$ and $D$.)

We start after one move in position $A$, which I can represent as $\mathbf{A}=(1,0,0,0,0,0{)}^T$.

The probabilities of the states after seven further moves are given by ${\mathbf{M}}^7\mathbf{A}=\frac{1}{128}\left(\begin{array}{c}1\\ 15\\ 7\\ 9\\ 3\\ 63\end{array}\right)$. We’ve a $\frac{63}{128}$ chance of ending up in state $D$.

OEIS

Of course, I can also make use of the OEIS. My scrappy notes show that the number of paths ending in state $D$ (starting after four moves) follow the pattern 1, 3, 10, 25, 63….

That turns out to be listed and has the explicit formula $a(n)=2^{n-1}+2^{\lfloor n/2\rfloor }+2^{\lfloor (n+1)/2\rfloor }-F(n+3)$, where $F(n)$ is the $n$th Fibonacci number.

Why this should be the case, I don’t know.

Ed’s follow-up

After seeing my answer, Ed noted that $\frac{63}{128}$ is very close to a half and asked if that pointed towards a short-cut. Looking at the OEIS formula, I suspect not - it’s just a coincidence that it happened to pass so closely.

Finishing up

As @ImMisterAl pointed out on Twitter, I didn’t actually answer the question asked: the probability of ending up with this pattern is $\frac{1}{256}\times \frac{63}{128}=\frac{63}{32,786}$, or about $\frac{1}{520}$.

---

I’d welcome any other insights you might have!

* Edited 2021-01-25 to fix formatting and answer the question.