# The solution

To satisfy my child self, we need to catch Raikou in the fastest clock time, not the fewest number of graph moves. This distinction is important, since graph moves are not all equally fast: from Violet City, it’s much faster to pop to Ecruteak via Routes 36 and 37 than to Azalea Town via Routes 32 and 33.

The absolute fastest way to complete one graph move is to take a single step across the boundary between two locations; the roaming Pokémon will instantaneously move as soon as we do that. Taking one step back across the boundary will complete another graph move and force Raikou to move again. If we keep hopping back and forth between two locations, Raikou will very quickly dart around the world map and eventually run into us by random chance. This ends up being faster than any strategy that requires hundreds of steps to actively move around the map. But where is the best place to wait?

Intuitively, it seems that we should camp out near a route that’s “well-connected” in some sense, but it’s not clear what measure of centrality gives the best answer. High-degree vertices in the Johto graph $$G$$ seem like good candidates, since we can expect Raikou, when left to its own devices, to return to a vertex $$v$$ every $$\frac{2|E(G)|}{\deg(v)}$$ steps. This would argue in favour of Johto Route 31, which is adjacent to five other routes (Routes 30, 32, 36, 45, and 46) on the roaming Pokémon’s trajectory.

Of course, we don’t intend to leave Raikou to its own devices, so the vertex with the highest degree isn’t necessarily the best answer to our question. Raikou starts out at a random starting position after every encounter, so the measure we want to optimize is $$\frac{1}{|V(G)|}\sum_u T(u, v),$$ where $$T(u, v)$$ is the expected time for a random walk starting at $$u$$ to reach our vertex $$v$$. This value can be computed using Tetali’s formula $$T(u, v) = \frac{1}{2}\sum_{w\in V(G)} \deg(w) (R_{uv} + R_{vw} - R_{uw}),$$ where $$R_{xy}$$ is the effective resistance between the points $$x$$ and $$y$$ if the edges of the graph were all replaced with 1-ohm resistors. Yes, we’re going to use the math of electrical networks to catch the rarest electric-type Pokémon!

Effective resistance can be computed by hand using Kirchoff’s and Ohm’s Laws, but it’s much easier to plug it into SageMath, which uses a a nifty formula based on the Laplacian matrix of the graph.

SageMath code to compute hitting times
G = Graph({ 29: [30, 46], 30: [31], 31: [32, 36, 45, 46], 32: [33, 36], 33: [34], 34: [35], 35: [36], 36: [37], 37: [38, 42], 38: [39, 42], 42: [43, 44], 43: [44], 44: [45], 45: [46] })

R_matrix = G.effective_resistance_matrix()

def R(u, v):
return R_matrix[G.vertices().index(u)][G.vertices().index(v)]

def hitting_time(u, v):
return 1/2 * sum(G.degree(w) * (R(u,v) + R(v,w) - R(u,w)) for w in G.vertices())

def avg_hitting_time(v):
return mean([hitting_time(u, v) for u in G.vertices()])

{ v: avg_hitting_time(v) for v in G.vertices() }


If we’re hopping back and forth between a route and a town (where wild Pokémon don’t appear), we can only capture Raikou after an even number of steps. We can account for this by computing resistances in the product graph $$H = G \times K_2$$ instead.1

SageMath code to compute hitting times accounting for parity
H = G.tensor_product(graphs.CompleteGraph(2))
R_matrix = H.effective_resistance_matrix()

def R(u, v):
return R_matrix[H.vertices().index(u)][H.vertices().index(v)]

def hitting_time(u, v):
return 1/2 * sum(H.degree(w) * (R(u,v) + R(v,w) - R(u,w)) for w in H.vertices())

def avg_hitting_time(v):
return mean([hitting_time((u,0),(v,0)) for u in G.vertices()])

{ v: avg_hitting_time(v) for v in G.vertices() }


Somewhat anticlimactically, Route 31 comes out on top with this measure too, but it does tell us that Route 36 is better than Route 42 despite their identical degrees.

But this still isn’t the final answer. As you might imagine, having the opportunity to catch our target on every step is generally better than only being able to catch it on the even steps. There are four pairs of routes in Johto for which this is possible (i.e. we can hop back and forth between them without a town or other time-consuming Raikou-free area getting in the way). The expected capture time when straddling one of these special boundaries can be computed using the same effective resistance calculations as the above if we merge the vertices $$(u, 0)$$ and $$(v, 1)$$ corresponding to our location after an even or odd number of steps, respectively.

SageMath code to compute capture times along route-route boundaries
@CachedFunction
def H(routes=None):
if routes is None:
return G.tensor_product(graphs.CompleteGraph(2))
else:
x, y = routes
graph = H(None).copy()
graph.merge_vertices([(x, 0), (y, 1)])
return graph

@CachedFunction
def R_matrix(routes):
return H(routes).effective_resistance_matrix()

def hitting_time(routes, u, v):
H0 = H(routes)
R = lambda x,y: R_matrix(routes)[H0.vertices().index(x)][H0.vertices().index(y)]
return 1/2 * sum(H0.degree(w) * (R(u,v) + R(v,w) - R(u,w)) for w in H0.vertices())

{
(x, y): mean([ hitting_time((x,y), (u,0), (x,0)) for u in G.vertices() ])
for (x, y) in [(30,31), (31,30), (35,36), (36,35), (36,37), (37,36), (45,46), (46,45)]
}


All four route pairs yield an expected capture time faster than relying on Route 31 alone.2

## Conclusion

Although Raikou will on average arrive at Route 31 faster than any other route, the best place to catch the roaming legendary Pokémon is the boundary between Johto Routes 36 and 37. Hop back and forth between those two routes, and before you know it, you’ll be one step closer to completing your Pokédex!

1. Unlike $$G$$, the product $$H = G \times K_2$$ is bipartite, and the bipartition lets us keep track of the parity of Raikou’s walk. It’s valid to look at random walks on $$H$$ instead of $$G$$ since the natural homomorphism $$f: H \rightarrow G$$ induces a probability-measure-preserving isomorphism between walks with a fixed starting vertex in $$H$$ and walks with the corresponding fixed starting vertex in $$G$$. ↩︎

2. The expected capture time differs slightly depending on which route we begin on. Both values, shown on the chart as different shades of pink, serve as bounds for the expected capture time in the repeated version of the game — when we encounter Raikou but fail to catch it in a Pokéball before it runs away to a random location. The relative frequency in which Raikou is encountered on each of the two routes, and therefore the expected capture time of the repeated version of the game, is left as an open problem. ↩︎