Can a Chess Piece Explain Markov Chains? | Infinite Series

Can a Chess Piece Explain Markov Chains? | Infinite Series


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

100 thoughts on “Can a Chess Piece Explain Markov Chains? | Infinite Series

  1. 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?

  2. 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 🙂

  3. 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

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

  5. 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 ?

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

  7. 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.

  8. 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.

  9. 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?

  10. 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?

  11. 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

  12. 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.

  13. 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.

  14. 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)

  15. 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

  16. 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.

  17. 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…

  18. 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.

  19. 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)

  20. 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 fun

  21. 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.

  22. 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?

  23. 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.

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

  25. 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.

  26. 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.

  27. 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

  28. 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?

  29. 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.

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

  31. 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?

  32. 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.

  33. 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

  34. 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)

  35. 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.

  36. 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?).

  37. 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.

  38. 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.

  39. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *