[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]

How about this problem: You have two knights of the same color on the board, let's say on b1 and g1. The chance of each knight moving is 50%. One knight cannot move to a square occupied by the other knight. What is the average number of moves it would take for both knights to be on their original squares simultaneously?

Another way to solve this would be through a system of equations.

If we denote the average amount of moves it would take to return to B2 from B2 itself as u_b2, we would have

u_b2 = 1 + (u_a3 + u_c3 + u_d2)/3.

For A1 we would have u_a1 = 1 + (u_b3 + u_c2)/2 and so on.

For squares that can reach B2, we don't get a u_b2 contribution.

For A3 we get u_a3 = 1 + (u_b5 + u_c4 +u_c2)/4.

We end up with a system of 64 equations and 64 unknowns. Then we can solve for u_b2 🙂

First challenge answer: 168 moves

Second challenge answer: 64 moves

Background Music really makes Maths interesting!

done! I subscribed!

isn't it also possible for random chance to allow for a infinite amount of moves without ever going back to it's start? but then you can counter this with the fact that a infinite amount of time should allow every possibility, I'm guessing that you must throw out infinity for this to work, but i could be wrong

I love the genre choices

i liked just because of ska

Would you use this to create the most efficient search pattern, say in the game Battleship?

Damn, that voice though!

This show is like the PBS math version of Slavoj Zizek

Cool… it looks like this is how one would figure out the most visited squares in Monopoly too. 😀

Weirdly, I want to play mine sweeper now.

Very good explanation about markov chains. You can make a video about hidden markov chains^^

Can someone explain to me the stationary distribution like why is the stationary distribution 2/3 for Kpop and 1/3 for ska in the second example ?

this mathematician is a deadly combination of beauty and brains!!!!! thanks for making it interesting and easier.😂😂😂😂

The rook is actually easier. It can always access 14 fields with its next move on an otherwise empty board. So it has 1/64 probabilty on each square and an expected time till next return to the same square of 64 moves.

Your Chanel is amazing, loved the work. I will encourage all of my friends to subscribe it.

the best response to the queens gambit is the slav defense everyone knows that.

So it is 80 for a bishop starting from one of A1 if I didn't misscalculated

Ah, Markov chains! I learned about them as a computer science concept many decades ago, but I hadn't learned about them as a way of predicting expected values in games until 2 years ago (almost exactly), when I was pondering "How many moves does the average game of the infuriating preschool boardgame Hi-Ho Cherry-O! last?" (it was hard to figure out with simple E(v) calculations, because of the variable value of the "lose all your cherries" spin.) Turns out the answer is approximately 15.8 rounds.

I'm sorry, I couldn't get beyond the notion that a radio station would play exclusively k-pop and ska. Does anybody know if there is a proof for this conjecture?

kpop… lolz

Wouldn't it make sense, therefore, to divide 336 by the number associated with each square

What is the average number of hops it would take a randomly moving knight to return to its starting point in an infinite chess board?

This channel is amazing! Have been binging on it all weekend. Having learnt all these topics back in college, this serves as a brilliant refresher. Love the fact that it goes into much more detailed explanation of the topics. I have seen it being applicable directly to my work.

P.S. I think I have a crush on you too! So that helps in coming back for the videos. You are so smart <3

eat a sandwich

rook will take 64 moves on average.

I wonder if you can use eigenvalues for the rook problem to create a kind of "heat map" of probability.

Damn, she's beautiful.

168,64

On average – I like every second video of yours, on average.

No, chess pieces can't talk.

video endsu always blow my mind.

marry me… i get u almost.

knight: 168 hops

rook: 64 hops

Worse radio station ever

Is it that hard to explain something so intuitives. Its simple statistic

I love you.

How do you determine the stationary distribution. I can't answer the large number of radios question since I don't understand how to determine the fraction initially.

starting from an arbitrary position on board, how can we determine if knight cover all positions on board without repeating any position ?

Challenge anyone to solve this problem.

168 steps?

now lets try to calculate the the average number of moves with a filled board, considering both players make complete random moves, but applying the chess rules :o)

come here after watching pawn sacrifice and reading nntaleb's tweets

Kpop!

Superb video! Thank you.

Awesome channel! You have a new sub!

Highly recommended video on the Markov chain, I thought I was stuck during my stochastic signals course and yet this video has just explain what my lecturer did for the past 3 hrs

I'm a simple man. I hear a mathematician swear, I upvote.

at 6:25 how does the average time decreases to 3/2 songs as the probability of kpop has increased? It doesn't makes sense.

pretty

Can someone please tell me what radio station that is? Cause that's my kinda shit! So oddly specific. I might have to start my own…

To elaborate on the stationary distribution, it's not that easy to extend the logic of multiple knights on one space to the radio example. But it is easy to see that it holds.

In the example where K-Pop is more popular, you can think of 6 radio channels that operate under that transition function. Four will be turned to K-Pop and two will be turned to Ska. When the song changes, 1/4 of all K-Pop channels (which is one) will switch to Ska while 1/2 of the Ska channels (one again) will switch to K-Pop. This distribution is thus stable and stationary.

How to get to that distribution in the first place is generally not trivial, but pretty easy in this case. You can think of the distribution as thus:

k portion of these radio channels will be turned to K-Pop.

s portion of these radio channels will be turned to Ska.

Obviously, s+k = 1 because the sum of all probabilities in the distribution must be 100%.

Now, when the song changes, 1/4 of the time, a K-Pop station will switch to Ska, so that's k * 1/4. 1/2 of the time, a Ska station will stay with Ska, so s * 1/2.

And here's the important bit: After this switcheroo, the distribution has to be the same, so:

k * 1/4 + s * 1/2 = s

k * 1/4 = s * 1/2

k/2 = s

Now, putting that into s+k = 1 gives us:

s + k = 1

k/2 + k = 1

3/2 * k = 1

k = 2/3

Additionally:

s = k/2

s = (2/3)/2

s = 1/3

And this will work every time with any Markov chain. If you have more states, the system of equations becomes more complex, but it's the exact same idea.

If each step has a random, exponentially distributed time length (instead of all steps being counted as one time unit like in this video) the time taken to arrive to a certain state is given by something called a phase-type distribution. These distributions have some interesting properties, e.g. "The set of phase-type distributions is dense in the field of all positive-valued distributions, that is, it can be used to approximate any positive-valued distribution" (Wikipedia)

do we

~~need~~to know how to do anything in chess or is it actually healthier, & more logical to simply allow it to be a game? played for funCan't get over how amazing this channel is. Seriously thank you.

168 moves on average for the knight placed in the corner

64 moves on average for a rook placed anywhere

Got me wondering about the min and max hops for a chess board full of knights, with one open spot, for every knight to occupy every spot at least once. No hop backs.

How do these numbers relate to the Markov chain and random walk problems.

Er… when a radio station probability of playing song A is 1/3 and playing song B is 2/3, how does listening it a long time changes the probability of hearing song A to 1/2 and hearing song B to 1/2 on THE SAME radio station?

rooks are simple, they can move 14 places no-matter where they are in the board, meaning they spend equal time in each square. 1/64 means 64 moves on average to get back.

can we figure out a standard deviation from the mean of 112? I think that would be super neat.

is the markov probability transition function always the same or can it depend on external factors

excellent

LOL is that a real girl? Looks like a shemale to me

Sooo, for a real world problem: Ask a grandmaster. For a made up fantasy problem, ask a mathematician. Just like in the real world!

Wow, this makes so much sense! I think this is the best way to explain Markov Chains. But 6:30 confused me as the derivation wasn't clear.

It will be 64 for the rook

K-Ska!

Looking at the chess board, we see 1/168. So 168.

A rook always goes to any 14 pieces, so the equal distribution is 1/64. It's 64.

Good video but the oddly specific genre picks urked me for whatever reason

Rook, queen and bishop: 64, but that is true regardless of the spot on the board. Though they each have a different number of spaces to which they can jump, that number is invariant across the board. The rook always has fourteen, the bishop always seven, and the queen always 21. Because of the invariant nature of the movement options, the variable ends up cancelling out. In fact, it can be proven fairly simply that if a piece has the ability to cross the entire board either diagonally, vertically, horizontally, or all three, on any square board with side lengths N, then the average number of hops a randomly hopping piece will take to return will always be N^2 pieces.

We can generalize even further to demonstrate that a piece has the board crossing ability on a cubic chess board which has M dimensions with side length N, in any direction such that all tiles are connected by an edge or vertex, then the piece will return to it's starting position an average of N^M hops. While I can't show the math easily in my head, the proof is in the fact that with that board crossing ability, your piece can always move to N-1 spaces in all valid directions for that piece. So for example, the equivalent of a queen on a cubic chess board could move N-1 spaces in the vertical, horizontal, lateral, and on the 45 degree diagonal of all three axes, regardless of its position on the board

I love you

Markov chains are really cool

What about the ''chessboard metric''? The diagonal of a square is equal to its side (8*8 board, corner to corner is 8 squares). Is it invalid as you can't generalise beyond45deg?

This video taught me more about markov chains in 10mins than my professor did in the first few weeks of lectures. That said Vasudevan is the worst lecturer ever, so I guess that isn't saying much.

PBS, bring this channel back!

Spends the video explaining the mundane details one logical step after another, then throws in the solution without an explanation.

https://youtu.be/OZQlZ3kIgOI

The Rook has the same number of squares to go to no matter where he stands witch is 14 so the average number of steps would be (14*64)/14 for each square right?

5:40 Start of the solution.

I do not understand how you got 2/3 for K pop and 1/3 for Spa. I would appreciate more details. Sometime, you just state some concepts or numbers without any explanation.

The corner knight is 168 using the fractions provided

As for a rook, its mobility is the same no matter where it is on a chessboard so each square has the same amount of ways to get to it and leave from it. therefore, 64 moves

Extremely brilliant!! Thank you so much!

Excellence

So Markov uses rules in randomness a certain version of entropy

beauty and the brain at eh same time… nice video and explanation … 🙂

I love this, I love your jumper, I love how you move your hands, I love how you explain stuff so seemingly casual, I want to be like you, but it seems so faaaar… 🙁

like I'm 20… I have no idea what to do after my degree… (cries)

Thank you for your video, and many of your videos helping to explain math to us who are not as gifted with #… I should point out, that the knight does not move two up in one over. It moves up by 1 and then attacks the next rows square perpendicular to the left or right. So technically, by chess a ticket, it moves two, not three squares.

And what's so weird about Ska?

What the hell is ska?

Awesome explanation!

Imagine trying this with queens

Suddenly I was transported back to my high school math class. I spent a lot of time staring at the clock. Now I remember why. -Blah, blah, blah, (Her hair looks weird) blah, blah, blah, (She kind of looks like an anime character) blah, blah, blah (7 minute and 41 second left?! Oh, cr*p!). Pause video and read comments. (Hmm, everyone else here seems smarter than me. Okay I'm bored now. What else can I look at?).

The rook is simple once you draw out there is (n – 1) vertical possibilities and (n – 1) horizontal, giving u 2 * (n – 1) possibilities or 2 * (8 – 1) = 14. So then A = { {0, 1/14, … 1/14}, {1/14, 0, 1/14, … 1/14}, … {1/14, … 0, 1/14}, {1/14, … 1/14, 0} }. This gives u a steady state transition vector of <1/64, 1/64, … 1/64> so for every starting position, the average time to return is 64 moves by the theorem :).

Survival Mode: Solve the average moves til return for every piece from every starting position and make heat maps for each piece.

real question, can u marry with me ?

168. I created a simulaton and get 169,348 (1000 knights)

First 168, second 64.

Made me more confused😅

it would take 168 jumps for the one in the corner.

Hmmm, the argument presented for coming up with the stationary distribution for the knight's chessboard suggests a much more general statement. Which is that, given a Markov Chain where each state has an equal chance to transition to its neighboring states, and the edges go both ways(as in, if X can transition to Y, then Y can transition to X) the stationary distribution at any state is its degree divided by the total number of edges in the graph. Neat.

11:29 "As p varies from 1 to infinity, pi will take on all values between 3 and 4." From a little research that seems to be false. They vary between the traditional 3.14… and 4.