[MUSIC PLAYING] If you need to know the best counter to the queen's gambit, you ask a chess grand master.

If you need to figure out the average number of steps it would take before a randomly moving knight returns to its starting square, you ask a mathematician.

Let's make the problem more precise.

Put a knight in its usual starting spot on the board.

It doesn't matter if you choose the first row, or the last row, or the second to left, or the second to right, they're all symmetric.

From there, the knight has three legal moves, any of these capital L shaped jumps.

And it makes each of these jumps with probability 1/3, meaning that it jumps here a third of the time, here a third of the time, and here a third of the time.

The knight continues moving this way.

Among all of its allowable moves, it picks a square randomly, with uniform or equal probability, and hops to it.

In our example, the knight now has six legal moves, each with a 1/6 chance.

Now that the knight's in the middle of the board, it has the freedom to make all eight possible moves.

Eventually, the knight makes its way back to its starting spot.

About 18% of the time, it hops back in two moves.

But it could take a much longer path, like this, or this.

Once it gets to the center of the board, it has a lot of options for where to jump, and could wander around for a long time before getting back to its starting spot.

So how many times will the knight move, on average, until it gets back to its original square?

To answer this question, we're going to do something very common in mathematics.

We'll abstract away from the specifics of our problem, and place it in a well studied structure, or format.

In this case, it's something called a Markov chain.

The first ingredient for a Markov chain is a state space.

In our case, the state space is the 64 squares of the chessboard.

Each square is called a state.

The second ingredient for a Markov chain is a probability transition function.

These tell us how likely the knight is to jump from one square, or state, in the language of Markov chains, to another.

These arrows show us that, from the corner, the knight has a 1/2 chance to jump here, and a 1/2 chance to jump here.

From a central square, we show the eight equally likely jumps with these arrows.

A similar story holds here.

We could keep filling in the chessboard with arrows like these, or these, or these.

Technically, every square should have arrows coming out of it, but if we drew them all in, there'd be so many arrows that the whole picture would be cluttered.

In fact, that's the rule about probability transition functions.

Every state has to have outgoing arrows that add up to exactly 1.

Since the arrows tell us how likely a knight is to jump from one square to another, the requirement that they add up to 1 can be interpreted as saying there's a 100% chance of jumping somewhere.

So a Markov chain is simply made of two things-- a state space and a probability transition function.

In order to solve our problem about the randomly hopping knight, we need to learn a little more about general Markov chain theory.

To help with that, let's check out a different example.

A super weird radio station plays two kinds of music-- K-pop and Ska.

These are the states of the Markov chain.

2/3 of the time, the next song is the same genre as the song that's currently playing.

And the other 1/3 of the time, it switches genres.

That's the probability transition function indicated by the arrows.

Now, I want to introduce the stationary distribution.

The stationary distribution assigns one number to each state.

The specific numbers it assigns are determined by the answer to this question-- if we have a huge number of radios, what fraction should be tuned to K-Pop, and what fraction should be tuned to Ska, so that, after they all randomly switch songs, the same fraction of radios are tuned to each channel?

In this case, with the probability transition function indicated, the stationary distribution of the Markov chain has value 1/2 on K-Pop, and value 1/2 on Ska.

If we have 1,000 radios, and about half the radios are tuned to K-Pop and half to Ska, at the next song change, a third playing K-Pop will switch to Ska, but the same number playing Ska will switch to K-Pop.

So it stays balanced.

That's what makes it a stationary distribution.

A slightly more intuitive way to think about it is the following-- if you listen to one radio for a really long time, what fraction of songs you hear will be K-Pop, and what fraction will be Ska?

About half and half.

Here's a theorem about stationary distributions-- pick a state in the Markov chain and give it the generic name State(X).

Starting from State(X), the average number of hops it will take to return to State(X) is 1 divided by the value of the station distribution at State(X).

This kind of makes sense.

The bigger the stationary distribution, the more popular the state is, and the less time it takes to return to it.

For a formal proof, check out the resources in the description, including the textbook where I first saw this problem.

Let's apply the theorem to our radio station.

If we're listening to a K-Pop song, how long will it take to hear another K-Pop song?

There's a 2/3 chance that the next song will be a K-Pop song.

But it's also possible that we'll listen to some Ska songs before returning.

Applying the theorem, we can see that, on average, it will take 1 divided by 1/2, or 2, songs before we hear another K-Pop song.

What if the radio station decided that people really liked K-Pop?

So they changed the probability transition function, and now it has a 3/4 chance of staying on K-Pop.

They also lowered the probability it will stay on Ska, like this.

Then, the stationary distribution is different.

It plays K-Pop 2/3 of the time, and Ska 1/3 of the time.

Applying that to our theorem, after hearing a K-Pop song, you'll now have to wait less time-- 1 and 1/2 songs on average-- before hearing another K-Pop pop song, which makes sense.

Let's go back to the knight randomly hopping around a chessboard.

Now that we know what a stationary distribution is, and how it relates to the time it takes to return to a given state in a Markov chain, we can solve our knight problem.

In order to answer our question-- on average, how many hops will it take before a knight returns to its original square?-- we need to find the stationary distribution, and use the theorem.

If a knight hops around randomly for a really long time, what fraction of its time will it spend on each square?

Intuitively, the squares in the center should have a bigger fraction, since they're easier to access.

And the corners will have a smaller fraction.

But how do we compute the exact number?

You're welcome to pause the video here and try to figure it out yourself.

It's a fun challenge.

But if you're ready to hear the solution, I'll tell you now.

First, we're going to fill a chessboard with knights in a particular way.

On each square, place the number of knights that corresponds with the number of possible moves a knight can make from that square.

So the corner squares each have two knights, and the central squares each have eight knights, and the ones closer to the edges either have three, four, or six knights.

This is how many knights we'll put on each square.

Now, here's my big claim-- if all the knights take one random hop, then, on average, the same number of knights will end up on each square.

Why?

Let's look at two squares, like C7 and E8, as they're known in chess parlance.

C7 has six knights on it, and E8 has four.

All of these knights jump randomly.

Each of the six nights on C7 has a 1/6 chance of jumping to E8.

So on average, exactly 1 knight will jump to E8.

Similarly, each of the four knights on E8 has a 1/4 chance of jumping to C7.

So on average, exactly one knight will jump to C7.

This means that C7 and E8 will swap a knight, ending up with the same number they started with.

There's nothing special about C7 and E8.

It works for any two squares that are a knight's move away from each other.

So all the squares swap pieces, and the configuration of knights ends up exactly as it started.

This collection of knights is very close to the stationary distribution.

All we have to do is figure out what fraction of knights are on each square.

The total number of knights is 336.

So we divide the number of knights on each square by 336 to get the fraction.

Now, this is the stationary distribution for the Markov chain.

Now that we know the stationary distribution, we can apply the theorem from earlier to finally answer our question.

How many random hops, on average, will the knight take before returning to its original square?

Well, to figure out the stationary distribution at the original square, we divide 3 by 336 to get 1/112.

Our theorem says that we divide 1 by 1/112 to get the expected number of moves before the knight returns.

That means it will take, on average, 112 random hops before the knight returns to its square.

So if it hopped once a second, the average amount of time it would take to return is a little under two minutes.

But as we saw earlier, it will sometimes return in just two seconds.

So in order for the average to be as big as two minutes, the knight must sometimes spend a long time hopping around before finding its way home.

Here's a challenge for you.

If you started the knight in the corner, instead of its usual square, how many hops would it take, on average, for it to return?

And another challenge.

If you start a rook in the corner, how many moves will it make, on average, until it returns to its starting square.

Leave your answers in the comments.

See you next week on Infinite Series.

You all had a bunch of great responses to our episode Exploring Pi in Different Metrics.

Funky Tom noted that pi in the L2 metric is famously irrational, but pie in the L1 metric is an integer.

So they ask, how often pi will be irrational in Lp metrics?

Well, as p varies from 1 to infinity, pi will take on all values between 3 and 4.

A lot of those values are rational, like 3.2 and 3.762.

But almost every number is irrational.

There are more precise versions of this statement, but I'll just say that pi will very often be irrational, because most numbers are.

Taylor Kinser asked if it's possible for pi to equal infinity.

Well, maybe.

In the episode, we were talking about metrics that are linear in some sense, that is, we want to measure length in a way that scales.

So the distance between 2-0 and the origin should be twice as long as the distance between 1-0 and the origin.

In this case, pi will always be between 3 and 4-- inclusive.

But as A F pointed out, if we drop that requirement, weird things happen.

There's this funny metric called the discrete metric, where the distance between any two points is 1, unless they're the same point.

Then, the distance between a point and itself is 0.

There's a good debate in the comments about what a circle might look like under this metric, and what that makes pi.

Honestly, I'm not sure if there's a good way to make sense of this, but I like the curiosity and creativity in this debate.

Finally, Huy Dinh asked a pretty neat question-- what's the value of p, such that pi in the Lp metric is equal to p?

And Steve's Mathy Stuff helpfully provided a succinct response-- 3.30524.

Cool.

[MUSIC PLAYING]