An ant on an infinite chessboard

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.

• Nice problem. What is your source?
– Did
Oct 7, 2014 at 8:34
• @Did Cost is proportional to distance, apparently. Oct 7, 2014 at 8:41
• If the ant is supposed to use all its energy it can never make a diagonal move: the only way that $x\cdot 1+y\sqrt 2$ equals 20 is when $y=0$. Should the problem read: "find the probability that, at the moment the ant is no longer able to move, the ant will be 2 units away from its initial position"? Oct 7, 2014 at 9:53
• By quasi brute-force, the probability I get is $26872167014433/2^{49} \approx 0.047734557665594$. It is sort of hard to describe what I have done and I've no other way to validate whether this number make sense or not. Let's wait whether other people can make another independent estimate/calculation.... Oct 7, 2014 at 13:41
• By a completely different way of counting (similar to the spirit in Dale M's answer), I can reproduce numbers in above comment exactly. So the probability is indeed about 4.77%. I'll post an answer describing the counting later (maybe tomorrow?) Oct 7, 2014 at 20:02

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:

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)

• @Pkwssis When I looked it over, I realized that there are only 4 valid ending points that are considered "within 2 units", correct? If so, I can modify my answer.
– JLee
Oct 7, 2014 at 20:54
• I understand the word "within" as "less or equal," thus, we are interested when the and ends up back in the exact center, or anywhere in the 3×3 square centered over the initial position (that's distances 1 and $\sqrt 2$), or in any of the four squares labelled "2" on your diagram. Anywhere else you would be farther than 2 grid units.
– user22961
Oct 7, 2014 at 21:31
• In the question, the comment "considering that the case that it finally ends up 2 units to the east (we can multiply by four to get all the cases)." makes me think that he meant just those 4 squares.
– JLee
Oct 7, 2014 at 21:35
• @JLee Yes that's what I considered.. Oct 8, 2014 at 0:51
• @Pkwssis Would you like me to run the sim for those 4 squares only? I don't mind at all.
– JLee
Oct 8, 2014 at 4:29

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\ .$$

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.

• +1 Cool, it saves me the trouble to write an answer! I look back at what I got, I have the same set of numbers of breakdown of paths by number of diagonal moves. Oct 7, 2014 at 21:57
• @achillehui Aww, I was looking forward to your answer. :) Was it also going to be a direct solution of the Markov chain state, or did you figure out a simpler approach? Oct 7, 2014 at 22:34
• The two ways I derive the answer are both computer assisted solution to the Markov chain state. Though one of it is closer to Dale H's answer in enumerating the possible combination of where the diagonal moves can go. It is sort of incomplete and I need a computer to help me filling a lot of gaps. As of this moment, both of them won't be any simpler than what you have done. The fun is figuring out the answer, not writing them down ;-p Oct 7, 2014 at 22:49
• "The fun is figuring out the answer, not writing them down" Amen to that! Oct 7, 2014 at 23:32
• @LeenDroogendijk That's already accounted for. In principle, at every time step, I applied a transition matrix for which every column sums to $1$. In practice, I wanted to use integer arithmetic, so I multiplied the transition matrix by $8$, and every column sums to $8$. A state with $\geq\sqrt2$ energy gets a column with $8$ entries equal to $1$; a state with energy $\in[1,\sqrt2)$ gets a column with $4$ entries equal to $2$; and a state with $<1$ energy left gets a column with $1$ entry equal to $8$. After $n$ steps, dividing by $8^n$ is the right normalization. Oct 8, 2014 at 0:59

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?