An ant on an infinite chessboard

Question

There is an infinite chessboard, and an ant $A$ is in the middle of one of the squares.

The ant can move in any of the eight directions, from the center of one square to another. If it moves 1 square north, south, east or west; it requires $1$ unit energy. If it moves to one of its diagonal neighbor (NE, NW, SE, SW); it requires $\sqrt 2$ units of energy. It is equally likely to move in any of the eight directions. If it initially has $20$ units of energy, find the probability that, after using the maximum possible energy, the ant will be $2$ units away from its initial position.

Assumption

If in case it doesn't have enough energy to move in a particular set of directions, it will move in any of the other directions with equal probability.

I approached this problem, considering that the case that it finally ends up $2$ units to the east (we can multiply by four to get all the cases).

If it ends up $2$ units to the east, then $\text{Total steps to right}=2+\text{Total steps to left}$.

We will somehow balance these steps, considering that the ant has a total of $20$ units of energy at the start.

I don't know how to effectively calculate the sample space either.

If the ant takes a total of $n$ steps, such that while taking all $n$ steps it is equally likely to move in any of the eight directions, then the sample space would be $8^n$.

But here we do not know $n$. Further, if the energy left after the second-last step is less than $\sqrt 2$ and more than $1$, then the ant will not be able to move diagonally.

I wasn't able to think of much after this. Help is appreciated.

Answer 1

Here is a solution in terms of formulas. My ant starts at $(0,0)$ and visits lattice points.

Energywise the history of the ant can be encoded as a word $AADADAAAD\ldots$ where the letter $A$ denotes a move parallel to one of the axes and $D$ a diagonal move. The individual letters are obtained by a coin toss, and the word ends when the ant's energy is used up. Denote by $a$ and $d$ the number of $A$- resp. $D$-steps. Then $$d\leq d_a:=\left\lfloor{20-a\over\sqrt{2}}\right\rfloor\ .$$ Each word corresponds to a staircase path in the first quadrant of the $(a,d)$-plane, as shown in the following figure:

The path ends at a red point, where there is no more energy for an additional step. At a blue point the following rule takes place: If a $D$ is thrown (with probability ${1\over2}$) at that point the ant makes an $A$-move nevertheless. It follows that all paths end at a red point $(a,d_a)$. The probability $p(a)$ that the number of $A$-moves is exactly $a$ is then given by the following formulas: $$p(a)=0\qquad{\rm if}\qquad d_a=d_{a+1}\ ;$$

$$p(a)={a+d_a\choose d_a}2^{-(a+d_a)} \qquad{\rm if}\qquad d_{a-1}>d_a>d_{a+1}\ ;$$ $$p(a)= {a+d_a\choose d_a}2^{-(a+d_a)}+{1\over2}{a-1+d_a\choose d_a}2^{-(a-1+d_a)}\qquad{\rm if}\qquad d_{a-1}=d_a>d_{a+1}\ .$$ We now compute the probability $p_{20}(a)$ that the actual grid path of the ant ends at $(2,0)$, given that it makes $a$ type $A$ moves. It is easy to see that $a$ has to be even in such a case. Given $a$, there are $h$ horizontal moves and $v=a-h$ vertical moves of the ant, where $0\leq h\leq a$. In reality we have $h+d_a$ independent horizontal $\pm1$-steps, which should add up to $2$, and $a-h+d_a$ vertical $\pm1$-steps, which should add up to $0$. Therefore $h+d_a$ has to be even as well. On account of the Bernoulli distribution of the $\pm1$ signs we obtain in this way $$p_{20}(a)=\sum_{0\leq h\leq a, \ h+d_a\ {\rm even}}{a\choose h} 2^{-a}{h+d_a\choose (h+d_a)/2-1}\cdot{a-h+d_a\choose(a-h+d_a)/2} 2^{-(a+2d_a)}\ .$$ The requested probability $p$ therefore comes to $$p=4\sum_{0\leq a\leq 20, \ a\ {\rm even}} p(a)\>p_{20}(a)\ .$$ The computation gave $$p={26872167014433\over562949953421312}\doteq0.0477346\ .$$

Answer 2

Thanks for the interesting and creative problem.

It made me curious as to how large the path could get for Energy = 20, so I mapped it:

The origin is the green cell and the possible end cells are yellow. The cells that your question asks for percentages on are the orange squares.

With problems like these with a gajillion possibilities, I lean heavily toward using a simulator.

I ran 4 simulations, each for 100 million trials, and since all 4 of them gave similar results, I concluded that the number of trials for each run was large enough. Here are the results:

------------------------ Original answer end ------------------------

Edit: This may be overkill, but I was curious how many distinct stopping points there were, and I wanted to see how the probabilities decreased as the endpoint got further from the origin.

So, I altered the sim again and re-ran it for 2,147,483,646 runs, and here are those results. The percentages are out of all possible paths, not just for the white slice shown. I am showing only the slice because it considers all 161 distinct points (and makes it small enough to read, but you'll probably need to save it to your machine to view it). All other possible ending points are a reflection of these points.

Quite a few possible ending points far from the origin were never hit once, and some were hit only once (15,10; 16,7; and 17,0)

Answer 3

There's probably an elegant approach, but I can't think of one. Computers to the rescue! We can exactly solve $20$ generations of the Markov chain on states (x, y, energy) with just $37932$ multiply-add operations on $64$-bit integers. I got the same answer as achille hui: $55034198045558784/ 8^{20} \approx 4.8\% $. Here's a breakdown of paths that stopped at a distance of $2$ by the number of diagonal moves:

d[0]  =      225684492800
d[1]  =     4280403359232
d[2]  =                 0
d[3]  =                 0
d[4]  =  2261233261281280
d[5]  =  5136894294884352
d[6]  =                 0
d[7]  = 23843942578520064
d[8]  = 19845792415088640
d[9]  =                 0
d[10] =                 0
d[11] =  3931022473297920
d[12] =                 0
d[13] =                 0
d[14] =    10806934634496

For example, $2261233261281280 / 8^{20}$ is the probability of stopping at a distance of $2$ after performing a total of $4$ diagonal moves (and $14$ non-diagonal moves). To explain the zeros, $\left\lceil d\sqrt{2}\right\rceil$ must be even in order to execute an even number of non-diagonal moves and end on a square of the same color as the starting square.

Answer 4

This is small enough that you can enumerate the possibilities.

To solve the sub-problem, at some point in the sequence you need either 2 lefts $p=\frac{1}{64}$ and $c=2$ or 2 diagonals $p=\frac{2}{64}$ and $c=2\sqrt2$.

There also need to be an even number of other moves that all cancel out $p=\frac{1}{8}$ and $c=2$ or $c=2\sqrt2$ and diagonals are as likely as orthogonals.

If all moves are orthogonal there can be a maximum of 10 pairs (counting the 2 lefts) if all are diagonal then then the maximum is 7.

What are the combinations?