Crate andys_morning_stroll

source ·
Expand description

Algorithms used to solve Andy’s Morning Stroll:

Andy the ant has spent most of his days living on a strange land consisting of white hexagons that are surrounded by alternating black pentagons and white hexagons (three of each), and black pentagons surrounded by five white hexagons. To us this land is familiar as the classic soccer ball we see above on the left. Due to Andy’s tiny size and terrible eyesight, he doesn’t notice the curvature of the land and avoids the black pentagons because he suspects they may be bottomless pits.

Every morning he wakes up on a white hexagon, leaves some pheromones to mark it has his special home space, and starts his random morning stroll. Every step on this stroll takes him to one of the three neighboring white hexagons with equal probability. He ends his stroll as soon has he first returns to his home space. As an example, on exactly 1/3 of mornings Andy’s stroll is 2 steps long, as he randomly visits one of the three neighbors, and then has a 1/3 probability of returning immediately to the home hexagon.

This morning, his soccer ball bounced through a kitchen with an infinite (at least practically speaking…) regular hexagonal floor tiling consisting of black and white hexagons, a small part of which is shown above on the right. In this tiling every white hexagon is surrounded by alternating black and white hexagons, and black hexagons are surrounded by six white hexagons. Andy fell off the ball and woke up on a white hexagon. He didn’t notice any change in his surroundings, and goes about his normal morning routine.

Let $p$ be the probability that his morning stroll on this new land is strictly more steps than the expected number of steps his strolls on the soccer ball took. Find $p$, rounded to seven significant digits.

First part

Initially, I wrote the RandomWalk trait and the Football struct to implement the walk on a football. The algorithm seemed to strongly hint that the answer was 20, which interestingly is the number of nodes in the graph.

It’s actually not difficult to prove this by taking advantage of the symmetry of the graph and down some relations between the various expected values. Let $E_k$ be the expected length of a starting at node $k$ and walking until we first reach node $0$. Then we wish to find $E_0$. Drawing out the graph, we can see that, by symmetry, there are only 5 distinct types of nodes, where each type must have the same value of $E_k$, so let’s just use $k$ to denote the node, rather than the specific node (i.e. the equivalance class). Then it’s easy to see that the relationships between the $E_k$ are:

  • $E_0 = E_1 + 1$
  • $3E_1 = 3 + 2E_2$
  • $3E_2 = E_1 + E_2 + E_3 + 3$
  • $3E_3 = E_2 + E_3 + E_4 + 3$
  • $3E_4 = 2E_3 + E_5 + 3$
  • $E_5 = E_4 + 1$

Starting with $E_4$ we can progressively substitute out the next highest $E_k$ from each equation to ultimately solve for $E_0 = 20$.

Second part

Having solved the first half I then created a new struct KitchenFloor which implements the RandomWalk trait, to stochastically measure how frequently Andy has a walk that is longer than 20 steps. This approach gives an answer of roughly 0.448, but it wasn’t converging quickly event with a large number of runs, so even after implementing a multithreaded version to get the total number of runs up to 8 billion, I still needed a different approach.

I came up two, both of which are implemented below:

  1. Enumerate every possible walk from the possible $3^{20}$ available (3 choices at each step), then iterate through them (approx. 3.5 billion), counting which ones terminate by arriving back at the home hexagon on or before the 20th step. This is not too bad computationally, but 3.5 billion possibilities take several minutes to calculate on a fast machine.
  2. Build the graph in-memory, and iterate through the 20 steps, tracking how many paths have arrived at each node on the $n$th step by summing surrounding nodes from the previous step. This is certainly the smartest and most computationally efficient solution, yielding a solution in c.1 millisecond on the same machine.

Both approaches above gave the same answer, which also matched the stochastic estimate of 0.448. So the solution is

$$p = 0.4480326 \text{ (7 s.f.)}$$

Structs

  • Decisions
    A helper struct to assist with iterating through the possible choices of path.
  • Expectation
    A struct to calculate the expected length of a random walk, for any type T: RandomWalk. We will use this to calculate the expected values of walks on our Football and KitchenFloor types.
  • Football
    A representation of the football Andy the Ant lives on.
  • GraphPathCounter
    Stores a representation of the underlying graph, tracking how many paths have reached each node at current time step self.step.
  • KitchenFloor
    An implementation of the infinite hexagonally tiled kitchen floor Andy unwittingly found himself walking around on this morning.

Traits

  • RandomWalk
    Implement random walks on a state machine.

Functions

Type Definitions