3
$\begingroup$

An ant is walking on the squares of a 5x5 grid - it starts in the center square.

Each second, it will choose (with equal probability) to do one of the following:

  • Move north one square
  • Move south one square
  • Move east one square
  • Move west one square
  • Do not move

If it cannot perform the action it has decided on (move west while on the west edge, for example), it sits in place.

After one second, it has a 20% chance of being in the center, and a 20% chance of being in each adjacent square. (and a 0% chance of being in any other square on the board).

  1. What is the probability that the ant is on the center square after 15 seconds?
  2. What is the probability that the ant is on one of the outermost squares after 1 hour?

Any suggestions? In the first question, I don't know how to enumerate all the possible routes that finish on the middle square after 15 moves and divide them by the total number of possible routes. In the second one, I'm completely lost.

Thanks for your help :-)

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ It would be appropriate to credit the source of the problem: Emcien Engineering Test. I suppose it's not against any rules to ask it here, but it kind of defeats the purpose of the test: checking if the job is a good fit for you. $\endgroup$ – user147263 Sep 15 '14 at 11:26
  • $\begingroup$ @Thursday To post an answer or not to post an answer, that is the question... What is your opinion? $\endgroup$ – Did Sep 15 '14 at 11:34
  • 1
    $\begingroup$ @Did It's a software engineering job, and your answer (as written below) is mathematical. I don't think anyone would get hired on the basis of it... Also, I see that "Emcien does not sponsor any Visas", and I dislike that, so I'm not going out of my way to protect their questions. $\endgroup$ – user147263 Sep 15 '14 at 11:39
  • $\begingroup$ Also, it's not a particularly original problem. E.g., the algorithm from my blog post Random Knight could be adapted for this problem. $\endgroup$ – user147263 Sep 15 '14 at 11:46
  • $\begingroup$ Id suggest using markov chains. $\endgroup$ – flawr Sep 15 '14 at 13:12
4
$\begingroup$

An exact computation to answer question 1. is simple in principle, difficult to do exactly with no computer, and the result is frankly not very interesting. Question 2. is more interesting since, after 3600 steps on a graph of 25 vertices with diameter 10, the random walk is close to its stationary distribution.

The random walk is equivalent to the simple reversible random walk on the augmented graph where one adds 3 supplementary loops to each corner, 2 to each side vertex not a corner, and 1 to each other vertex. Every vertex in the augmented graph has degree 5 hence the stationary distribution is uniform. The Markov chain is aperiodic hence, at any large time, the probability to be at any of the vertices of this graph with 25 vertices is approximately 1/25.

The probability to be in any set S of vertices is approximately the size of S divided by 25. There are 4 corners hence the probability to be at one corner is approximately 4/25. There are 16 side squares hence the probability to be on one side is approximately 16/25.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ OMG ! Just saw this answer. Really elegant. Good one ! $\endgroup$ – Yaitzme Sep 15 '14 at 12:14
  • $\begingroup$ For a related blog post see John Cook's post. $\endgroup$ – Michael Lugo Sep 15 '14 at 13:19
  • $\begingroup$ @MichaelLugo Unless I am mistaken, this post answers a different question about a different model. $\endgroup$ – Did Sep 15 '14 at 13:25
  • $\begingroup$ @Did - Is there anyplace where I can read in a little more rigourous explanation about the claims in paragraph 2 of your answer? $\endgroup$ – Yaitzme Sep 15 '14 at 15:07
  • $\begingroup$ @Yaitzme The explanation is fully rigorous. Which part do you fail to find crystal clear? $\endgroup$ – Did Sep 15 '14 at 16:51
3
$\begingroup$

Roll up the grid into a torus, so that the ant can move from the top to the bottom edge or from the left to the right edge (anybody remember Asteroids?). This doesn't change the probability of it being in one of the 16 (original) edge squares, because staying put in an edge square is the mirror image of crossing to the opposite edge.

There are no distinguished squares on the torus, so the probability of each square tends to $1/25$. Hence the answer to the second question is "very close to $16/25$".

This is different from Did's $4/25$, but only because we interpret "outermost" differently.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This answer is too good again. I find my answer childlike now ! $\endgroup$ – Yaitzme Sep 15 '14 at 12:44
  • 1
    $\begingroup$ @Yaitzme: But you are still the only person to answer question 1. $\endgroup$ – TonyK Sep 15 '14 at 12:47
  • $\begingroup$ Why is it that there are no distinguished squares on a torus? All squares don't seem symmetric to me. $\endgroup$ – Yaitzme Sep 15 '14 at 15:17
  • $\begingroup$ @Yaitzme: Topologically they are all the same. $\endgroup$ – TonyK Sep 15 '14 at 18:00
1
$\begingroup$

Let P[t, (x,y)] be the probability that the ant will be at (x,y) at time t. We can form a recurrence relation as such:

P[t, (x,y)] = 0.2 * [(5-No of neighbours of (x,y)) * P[t-1, (x,y)]] + 0.2 * P[t-1, (a,b)]
where (a,b) is a valid point neighbouring (x,y)

Start with P[0, (3,3)]=1, P[0, (a,b)]=0 for all other points and build the recursion.

Answer 1 = P[15, (3,3)]
Answer 2 = P[3600, (1,1)] + P[3600, (1,5)] + P[3600, (5,1)] + P[3600, (5,5)]

I wrote a crude python program which gives the result. Unless I'm wrong, the answer to Q1 is 0.0412498 and the answer to Q2 is 0.16

You can find the code at https://gist.github.com/humachine/8402f2183d126a8eb486

|cite|improve this answer
$\endgroup$
1
$\begingroup$

I solve the problem with markov chains: Enumerate the grid cells as follows: $$\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & \ldots & \\ \vdots \\\end{matrix}$$

Then you can set up a $25 \times 25$ transition matrix $A$. Each entry of the transitionmatrix denotes the probability of a transition from a certain cell to a certain cell. The entry $A_{ij}$ has the probability of transition from the cell $j$ to the cell $i$. The cells on the border of the grid have that special rule that if you do an 'invalid move' you just stay there. This means just that the transition probability of that cell to itself is being increased by that amount. This results in following matrix:

$$A = \begin{pmatrix} C & S & & & 0 \\ S & M & S & & \\ & S & M & S & \\ & & S & M & S \\ 0 & & & S & C \end{pmatrix}$$ where $$ C = \begin{pmatrix} .6 & .2 & & & 0 \\ .2 & .4& .2 & & \\ & .2 & .4& .2 & \\ & & .2 & .4 & .2 \\ 0 & & & .2 & .6\end{pmatrix} \quad M = \begin{pmatrix} .4 & .2 & & & 0 \\ .2 & .2& .2 & & \\ & .2 & .2& .2 & \\ & & .2 & .2 & .2 \\ 0 & & & .2 & .4\end{pmatrix}$$

$$ S = \begin{pmatrix} .2 & & & & 0 \\ & .2& & & \\ & & .2& & \\ & & & .2 & \\ 0 & & & & .2\end{pmatrix}$$

If we know what to get the probability distribution after $n$ steps we just have to write down the start distribution $v$ and compute $A^n v$.

The start distribution in this case was: $v = (0,\ldots, 0, 1,0,\ldots,0)^t$ where the $1$ is in the 13nth entry. (Which is the center cell according to our enumeration.)

With this concept you can easily answer your questions.

The Matlab/Octave code can be found here and can be executed in any online octave interpreter by removing the plot commands at line 34/35

|cite|improve this answer
$\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.