14
$\begingroup$

enter image description here

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 consumption, 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.

$\endgroup$
  • 1
    $\begingroup$ Nice problem. What is your source? $\endgroup$ – Did Oct 7 '14 at 8:34
  • $\begingroup$ @Did I had a similar problem in a book. I thought of this myself though. I don't know if it is even solvable.. $\endgroup$ – pkwssis Oct 7 '14 at 8:39
  • $\begingroup$ Why the costs 1 and sqrt(2)? $\endgroup$ – Did Oct 7 '14 at 8:40
  • 1
    $\begingroup$ 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"? $\endgroup$ – Leen Droogendijk Oct 7 '14 at 9:53
  • 1
    $\begingroup$ 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.... $\endgroup$ – achille hui Oct 7 '14 at 13:41
6
$\begingroup$

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:

enter image description here

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

$\endgroup$
7
$\begingroup$

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:

enter image description here

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:

enter image description here

------------------------ 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)

enter image description here

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – JLee Oct 7 '14 at 20:54
  • $\begingroup$ 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. $\endgroup$ – user22961 Oct 7 '14 at 21:31
  • $\begingroup$ 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. $\endgroup$ – JLee Oct 7 '14 at 21:35
  • $\begingroup$ @JLee Yes that's what I considered.. $\endgroup$ – pkwssis Oct 8 '14 at 0:51
  • $\begingroup$ @Pkwssis Would you like me to run the sim for those 4 squares only? I don't mind at all. $\endgroup$ – JLee Oct 8 '14 at 4:29
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +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. $\endgroup$ – achille hui Oct 7 '14 at 21:57
  • $\begingroup$ @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? $\endgroup$ – Chris Culter Oct 7 '14 at 22:34
  • $\begingroup$ 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 $\endgroup$ – achille hui Oct 7 '14 at 22:49
  • $\begingroup$ "The fun is figuring out the answer, not writing them down" Amen to that! $\endgroup$ – Chris Culter Oct 7 '14 at 23:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Chris Culter Oct 8 '14 at 0:59
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.