Can a Chess Piece Explain Markov Chains? | Infinite Series
ฝัง
- เผยแพร่เมื่อ 11 ม.ค. 2017
- Viewers like you help make PBS (Thank you 😃) . Support your local PBS Member Station here: to.pbs.org/donateinfi
In this episode probability mathematics and chess collide. What is the average number of steps it would take before a randomly moving knight returned to its starting square?
Tweet at us! @pbsinfinite
Facebook: pbsinfinite series
Email us! pbsinfiniteseries [at] gmail [dot] com
Previous Episode - When Pi is Not 3.14
• When Pi is Not 3.14 | ...
Mathematician Kelsey Houston-Edwards explains Markov Chains and how they can be used to determine the probability of random chess moves, as well as the likelihood your favorite music will pop up on the radio.
Sources include:
Probability: Theory and Examples
www.amazon.com/Probability-Ca...
Markov Chains
www.amazon.com/Markov-Cambrid...
Markov Chains and Mixing Times
pages.uoregon.edu/dlevin/MARKO...
Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux
Made by Kornhaber Brown (www.kornhaberbrown.com)
Comments answered by Kelsey:
Taylor Kinser
• When Pi is Not 3.14 | ...
Huy Dinh
• When Pi is Not 3.14 | ...
Funky Tom
• When Pi is Not 3.14 | ...
Steve’s Mathy Stuff
• When Pi is Not 3.14 | ...
im surprised how this series is touching on concepts that aren't as popular as topics for math videos on youtube. i was expecting it to just be another take on the same kind of topics seen on numberphile and the like, but it seems like it's really kinda doing it's own thing. really fascinating topics ^^
+
nathanisbored +
nathanisbored +
+
+Nirakh Tyagi +
I love how you guys actually get into some real mathematics in this series. It's not your usual TH-cam surface level stuff.
+Cyanide Cloud
I just hate number theory, so that rules out about half of Numberphile for me.
15 Things That Will SHOCK You About Markov Chains!!
or 5$ markov chains vs 500$ markov chains
And look at how much has changed in the last 6 years and more. Its a win
Can a chess piece explain Markov chains? No, but PBS Infinite series can explain Markov chains with chess and radio stations.
Thank you for doing this without dumbing things down
Starting on their original squares:
King = 84
Queen = 69
Bishop = 40
Knight = 112
Rook = 64
Nice
Nice
Nice
Nice
Re: The challenges
Knight in the corner:
1/(2/336) = 168, by the same logic presented in the video.
Rook:
First, we note that a rook has the same number of moves anywhere on the board (14), so the stationary distribution is 1/64 everywhere. From there, just take the reciprocal and find the answer to be 1/(1/64) = 64.
1/(14/14*64) = 64 , if anyone was wondering where the 14 disappeared like me.
I'm missing something here, though. With the Knight, it has a fixed move ie: two spaces in one direction then one space in either opposing direction (Or vice versa). The rook, however, can move as many spaces as it wants in any direction along rows or columns. Wouldn't the possible number of moves for the rook be far greater considering it could move along, say, the row by one space or two spaces or three spaces and so on? There was never any limit put on the rook to move each turn. It could, theoretically, go all the way from one corner to the other, then to the next, to the next, then back to the start. Do we have to place limitations on the rook as to how many spaces it moves each turn?
The calculation here are great but there is a small correction on the
"Knight in the corner:" it should be:
1/(1/(2/336)) = 1/(1/168) = 168
Hey man I need help @pete Manguson
we should consider move or movement direction
So 2.8 minutes
168 for the knight.
As the rook can move to the same number of squares from every square (14), the stationary distribution is 1/64, so the average number of moves is 64.
There are 8 columns and 8 rows on a chess board. It occupies one of each and moves horizontally or vertically. This leaves 7 squares each way, making 14.
Colin Jones pretty sure it can as it always has access to one row and one colum at any time, no more and no less. As the square its sitting doesnt count it has 7 from the colum and the row therefore it always has access to 14spaces....let me know if I am wrong tjo
That's what I said initially, and no matter the number, the fact that each square has the same SD, that number cancels out.
I agree. All squares are equal.
Colin Jones what the heck
I'm studying industrial engineering and am taking a stochastic process class so this was a nice surprise as we covered markov chains last week. However, we also used linear algebra to make the math easier and delved a lot deeper.
Nice! I bet there are a lot of awesome applications of stochastic processes to industrial engineering.
And yes, linear algebra underlies finite Markov chain theory. But since this problem would use a 64x64 matrix, it's actually easier to solve using the cited theorem and forgetting the matrix.
I'm so happy I found this channel. Only 8 uploads so far, yet they are already of such high quality! Your explainations are stellar, and the visuals make this higher mathematics stuff really accessible, even for someone who doesn't study it. To me this is absolutely fascinating, and I love it. It's gonna be exciting watching this channel grow!
Omg, these videos are amazing!!! They explore actually interesting topics, rather than boring old basic math. Please keep up the good work!!
Love your videos. Keep up the good work.
Thanks Zubmit! We plan to keep it up.
Yes, we need to expand edutainment more than ever.
Learning is cool! :D
69 thumbs!
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.
The important question is, what is Kelsey's FIDE rating?
The production value is crazy good on these, all of the diagrams are very well done. I wish they were still making them.
Wow! I think it's the best video explaining the usage of Markov Chain in a very playful way I've ever seen. What a amazing job you are doing here, guys!
Greetings from Brazil!
now if only this vid was uploaded yesterday before that horrible markov chain question on the exam i did this morning
Where does the 2/3 and 1/3 come from when you changed the probabilities of the radios?
Loved this video! Haven't seen any of the older ones... let the binge begin.
Can't get over how amazing this channel is. Seriously thank you.
The knight in the corner is not much of a challenge considering you've already done most of the work.
The rook will return in an average of 64 moves, an answer both boring and interesting because it's just the number of squares on the board and it doesn't matter where the rook starts.
A bishop starting in any edge square will take 40 moves on average to return to that square.
Everything was pretty integers, then the queen had to come along with an ugly 69.3... average if she starts in her usual square.
The queen just enjoys 69, why are you judging her?
I found a way to get her to comply with the Pythagorean ideal. If we don't let her move on diagonals of her own color, her average trip will be 84 moves if she starts on her own color and 56 moves if she starts on the opposite color. Integers are sacred.
U Wot M8
Technically, she enjoys 69 plus a third. Which is as ugly mathematically as it is... wait, what else were we talking about?
Very comprehensive explanation, thanks! Great channel!
Love these videos! I feel like I've learned more from PBS Digital Studios than my university. Keep up the great work!
Excellent work and content! Kudos to all involved.
As an aside, this video just hit me in that this would be an excellent way to intuitively explain the "probabilistic" nature of quantum mechanics and stuff like the many-worlds interpretation.
These videos are soo great! I wish they came out more often!
This is a nice video. So many more things need to be clear in my head before following this video without struggle that makes me wonder even more about the displayed topic. I am not a mathematician but this channel is so happy to watch... I was a fun since the very first video I saw. GREAT JOB!!!
this mathematician is a deadly combination of beauty and brains!!!!! thanks for making it interesting and easier.😂😂😂😂
I feel alive each time I watch an episode from this awesome channel !!!
You are alive
Came back to this channel after 5 years, from some chess content that I'm really into nowadays. One of the best channels on TH-cam
Just watched every episode (so far)!!! New favorite channel!!!!!!!!
Fantastic video! Very powerful information explained in an accessible way
Kpop and ska are quite specific genres just for an example. She must be a fan of them or something.
When she said two kinds of music, I expected them to be both kinds, as in the Blues Brothers movie.
Or she just read it from a script?
manifestasisanubari she is the scriptwriter
Oh! Didn't know that. :)
Maybe chosen at random?
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
These videos are so great! I wonder what the next topic will be! Maybe something with integrals?
I really enjoy these videos. They go into much more depth than most maths videos online, and the challenges are well set (I might give the rook's Markov chain a go, actually. Intuitively, I'd expect the probability distribution to be constant across all squares - so, one sixty-fourth ?). Well done !
Awesome show! Keep the explanations coming!
Really cool video with a deep explanation, thanks!
Excellent video! Thanks for all the hard work.
Extremely brilliant!! Thank you so much!
Math has always been a frustrating thing for me; Algebra for example, has for some reason always been a challenge, and beyond that, I've always struggled with formulas. This channel offers intuitive explanations to things that would otherwise be like trying to read in a language I don't speak, but sort of recognize the characters and symbols... I have a deep interest in the Sciences, especially Physics, of which you can only learn so much before you need math.
Thank you for making videos like these, and please continue to do so; I believe this channel and others like it provide valuable tools for understanding things that people like me (The mathematically challenged) can truly benefit from.
Also loved the crossover videos with PBS Space Time.
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
Great channel. Hope to see more content you pick good subjects. I also hope more people get to know about it !
Awesome explanation!
This is really informative. Great job!
Really great videos! Thank you!
I was just looking at Markov chains as part of a project for my psychology undergraduate! One popular model of neurons has them act as two-state Markov chains. However, I'm looking at that modelling on my own and wasn't really taught stochastic maths, so this is impeccably timed.
We were pretty psyched to see Markov Chains on this channel. We use them for loss prediction for loans at Banks (using them to quantify and then predict risk migrations). They're a powerful and convenient tool. They're also the first practical use of the most useless of Algebra II lessons from high school... Matrix Math ;)
I have never heard of Markov chains. All I knew was basic probability and little bit of state space in control systems. but this makes a lot of sense and I felt like I actually understood this. this is truly amazing.
Cool like a chill! Keep up the great content!!
I love your delivery, you are the best host in all the PBS series (nothing to do with me being a mathematician hahahahah)
truely informative. Thank you
Awesome series loving it!!
First question: Since stationary distribution of knight at state (corner) is 1/168, 168 seconds (2.8 minutes) or hops is the average time of a knight to return to state (corner).
Second question: For the rook, at all states including the corner, there is a 1/14 possibility of landing at a given state. Using this, let's assign 14 rooks per square. Then we get total population of 14x64 = 896, using that to get stationary distribution of 14/896 or 1/64. With the stationary distribution of rook at state (corner) of 1/64, 64 seconds or hops is the average time of a rook to return to state (corner).
Yay math! :D
Rooks take, on average, 64 moves to return to their starting position. I used the same logic as presented in the video! Great video by the way. I had heard of markov chains before, but this was still enlightening.
I'm so happy that PBS made a math channel!
Superb video! Thank you.
Wow, two really good videos in a row from this presenter. That's a sub!
Really good video. Great work!
Kelsey is really elegant.
...btw, plz, make more videos on hyper dimensional geometry :D
Love your explanation.... You are an angel... Great job and God Bless you
amazing videos! Love the intro sound.
Your Chanel is amazing, loved the work. I will encourage all of my friends to subscribe it.
really enjoy these videos, not sure whether I should be happy or sad that I got to focus more on the math than in the poison video :D
168 average hops for the knight in the corner. The rook, at least as I understand this, should have an equal distribution all over the board, which is 14 (according to the rules of chess as I understand them). The total number of rooks should be 896, 896/14 is 64. So I guess it should be 64 moves on average for the rook to get back to its starting position. It can be any starting position on the board.
Exactly. The rook is the only chess piece that always has the same mobility regardless which square it's on (ignoring other pieces, of course).
Wow! You can explain complex notions in way to make them accessible to a general audience. I don't know if you take suggestions for future episodes; if you do, I'd invite you to consider an episode on Hopcroft-Karp algorithm. Great stuff anyway, keep up the good work!
thanks for the video.. really liked it
For the rook:
on an empty board every square has the same set of moves(14).
the total number for computing the probability is 14*64, or 896.
1/(14/896) = 896/14, or 64.
On average it will take 64 moves.
As a side note, this number feels like a measure of the mobility of a particular piece and location.
I love this channel, keep it up!
I love the genre choices
My new favorite channel
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 studying this in university this semester!! With the great Giorgio Parisi! This is so cool: to see an application of what i studied in chess!!
excellent video!
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.
Thanks for your elaboration!
Well the corner knight would take on average 168 moves to return, since 1/(1/168) = 168. Now for the rook, since on each square the rook has the same number of squares it can go to for any starting square (14), it is quite easy to say that it must take on average 64 moves to return, since the stationary distribution is equal on all squares, therefore it must be 1/64. Cool video!
I'd like to ask if the channel or anyone could provide subtitles for the videos cuz I think that there's a lot of people including myself that'd be very benefited from it given the fact that english is not my first language (and of many people neither) and, specifically here in Brazil, there's literally no other place to find stuff like this, excluding some books of hard access. I'd be very grateful if possible and thank you for this amazing series!!!
Knights rarely return to their original squares because they're eaten . But the reversal of direction is a characteristic that can aid strategy and tactics in that it is not eaten and thereby retains some of its value.
Markov chains have also been applied to American football. By using Markov chains to analyze the expected value for the number of points scored given 1) a position on the field, 2) the number of yards until a 1st down, and 3) a choice between punting, kicking a field goal, or going for the 1st down, researchers have concluded that football coaches punt far too often.
One of many introductions to the subject: www.advancedfootballanalytics.com/index.php/home/research/game-strategy/120-4th-down-study
Knight in the corner would take on average 168 hops because the Stationary Distribution State is 1/168.
The distribution on rooks are even. No matter where you are on the board, you can always move to 14 other places for a total of 896 spots. That gives each Stationary Distribution State a value of 14/896 or 1/64. It would therefore take on average 64 moves to return to its original spot.
Just for fun I did the bishop. The distribution of a bishop depends on how far you are from the nearest edge.
If you wanted to show the number of moves each position can make-it's 7 where you are on the edge, 9 where you are one space from an edge, 11 where you are two spaces from an edge, and 13 where you are three spaces from the edge.
This gives you a total of 560. A bishop on the edge would have a stationary distribution state of 7/560 or 1/80. That means it would take on average 80 moves to return.
168 for the knight at the corner, 64 for the rook, also about 70 moves for the queen, 80 moves for the bishop, 84 moves for the king, and 0 moves for the pawn, as the pawn can only move forward.
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 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.
Man I still sad this series ended like other TH-cam series it actually does a good job at explains it.
Thanks! This might be in my stochastic exam question later!
The knigth will take 168 steps, on average, since P(Being in the corner | Stationary distribution)=168. The rook's stationary distribution is an U(64) (uniform in 64 posibilities), since all the points in the board have 14 posibilities to choose from, so in a chess board with 14 rooks in every cell you will, on average, stay in equilibrium. So, since the probability is the same for every cell, it must be 1/64. Using the theorem P(Being in the corner | Stationary distribution)=64
The rook should have totally uniform distribution due to the way it moves. Since the rook only moves EITHER horizontally or vertically, you can imagine you're altering one coordinate of it's 2D coordinate on the grid. For simplicity, we can argue that we write the coordinate as an ordered pair of integers from 0 to 7 as (horizontal, vertical) = (a,b), with (0,0) being the lower leftmost box. When moving the rook, you effectively change one coordinate, either a or b, to some different value in the range, while holding the others constant. If the rook moved 3 to the right, the new coordinate is (a+3,b), or if it moved two down, (a,b-2). Note that a vertical movement doesn't dependent on what the horizontal coordinate a is, so the motion is equivalent across all columns. Likewise, moving horizontally depends not on the b vertical coordinate, so all rows are equivalent. Well, combining those two fill the entire grid, so a rook on any in the grid has exactly the same number of squares it can move to if it were on any other square. The exact number is 14 possible moves on every square.
Following the proof, the total number of moves is 14 move/box * 64 boxes = 896 total. So the stationary distribution at each box is 14/896 = 1/64. Now we take the reciprocal of the distribution, and its 64, and since each box is identical in this sense, on average it'll 64 random moves to bring the rook back where it started.
Awesome channel! You have a new sub!
PBS, bring this channel back!
Awesome channel. Hope there will be more challenges.
Knight - 168 hops, Rook - 1/(14/896) = 64 hops.
Nice to see that math channels get more and more popular :)
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)
Knight: 168 moves (see video at 9:57)
Rook: starting from any state a rook can go to 14 other states. Therefore we place 14 rooks on every tile. The stationary Distribution then is 14/(14rooks*64states) = 1/64. Giving us an Average time to return to any given starting tile of 64 moves.
You'r the best. Make about the Ramanujan serie -1/12 pls!!
Knight in the corner: 168 moves, following the same logic as you did in the video.
Rook: No matter where the rook is on the board, it has exactly 14 possible moves. Since this number is the same for every state, the stationary distribution becomes 1/64 for every state. This makes the average number of moves 64.
Great video! I do simulations of quantum field theories (lattice quantum chromodynamics specifically) and Markov chains are at the core of generating field configurations. If the Markov chain generating field configurations aren't ergodic, we aren't really simulating physics.
Can anyone explain the process for finding the Stationary Distributions of the second radio station example?
It involves solving an eigen value problem. A more intuitive way would be as follows:
Based on the transition probabilities at 4:26, the overall probability of a kpop song will be,
Kpop = 2/3 kpop + 1/3 ska
Therefore, kpop = ska
Therefore, kpop/(kpop+ska) = 1/2
Similarly, for the other transition probabilities,
Kpop = 3/4 Kpop + 1/2 Ska
Therefore, Kpop = 2 Ska
Therefore, Kpop/(Kpop+Ska) = 2/(2+1) = 2/3
@@shihabkhan3218, thanks a lot, it really helped me understand the solution.
@@shubhamsaha7887 you're welcome bro
Particulars stations total actions/Combined action for both stations
Hello from Germany :D here are my answers:
Knight on corner: 1/(2/336) = 168
Rook on corner: 1/(14/(14*8*8)) = 64
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.
On average - I like every second video of yours, on average.
The knights 8x8 middle configuration square actually marks the area of its competitive advantage as it has more versatility in those cells in the square . Knights on the rim tough to win . But having done some notation I've found some interesting repetitive numerical sequences in the files for the Knights square. For example 123 44 321 a sort of count up count down sequence . Mabe that doesn't relate to Markov chains but it does show a kind of equilibrium. Somewhat palindromic for the palladin.
Awseome video ! very interrsting !
I would say 168 moves for the night in the corner
and 64 for the tower (every cases are equiprobable in the markov chain and there is 64 cases)
Random hops on average each chess piece needs in order to return to their original spots (where initially placed at the beginning of a chess game) with an (otherwise) blank board:
knight: 112
rook: 64
bishop: 80
king: 84
queen: 208/3 (69 and 1/3)
pawn: pawns can't move backwards :(
Also, the number of spaces a queen can move to from a given tile is the sum of the number of spaces a bishop and rook can make from the same tile. This make sense as the queen moves like a bishop and a rook!
The answer for the first question for every square was already given to us @10:38, just remove the "1/". 168.
The rook answer is nearly as simple but more interesting. Every square has 14 spots the rook can move to. So 14 * 64 squares divided by the 14 moves of the square in question. 14 * 64 / 14 = 64. It's interesting cause it will always equal the same number of squares the chessboard has, even if it's not a square board!