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 ^^
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.
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?
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
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!
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!
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.
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.
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.
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!!!
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 !
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 ;)
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!
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
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
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!
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
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.
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.
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
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!
It can! This is a pretty famous old problem, called a knight's tour. The wikipedia article (en.wikipedia.org/wiki/Knight's_tour) has a good overview and history section. You can also try to do a knight's tour on other size chessboards and non-square ones -- it's sometimes possible and sometimes not.
And now I'd like to know with what probability knight makes a closed knight's tour or in other words what is the ratio of Hamiltonian cycles to paths/cycles with the length of 64.
Assumption 1 hop per sec if knight starts from A1 it will take 168 sec if Rook starts from A1 then it will take 112 sec in the case of rook, we have 2 moves per corner so 4 set of 2 moves 3 moves along the edge so 24 set 3 moves and at rest square, it will have 4 moves hope it was helpful In case, If I am wrong please correct me Thank you
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)
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.
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.
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!
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.
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.
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)
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.
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!!!
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.
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.
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.
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
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 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.
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.
The movements of the rooks are completely symmetric, in the sense that, in every given path, you could swap some rows and columns and it would still be a valid path. Thus, the stationary distribution has to be uniform across the board, so for it to sum 1 it's 1/64 on every cell: thus it takes an average of 64 moves
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.
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.
The other way to estimate this is to use a sampling method. i.e. you start from a state, count the number moves it took you to get back to start state. Perform this sampling till you reach ergodicity. With this can easily calculate the mean to get the expected number of steps.
I did this for every piece to see which one would take the longest to get back to its starting point and what square it would start on. 1st place goes to the knight starting in the corner with 168 moves 2nd was the king starting in the corner with 127 moves 3rd was the knight starting on the four spaces adjacent to the corners with 112 moves also with 112 moves is a pawn on the top or bottom row(I let the pawn be able to move forward and backwards in the scenario but does not go side-to-side or diagonal)
You might want to check what topics does the course cover, it might not mainly focus on Markov chains. (But other parts of probability theory are also a lot of fun!)
I believe it covers markov chains and other random processes. I remember seeing my friend who took the course last year working on this chess board problem. Gonna be so fun!
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.
What will be the average number of steps would take for a knight to return to its starting point in a 3-dimensional chess? or multi-dimensional? Does stationary distribution apply to higher dimensions?
Correct me if I'm wrong with this assumption, I found out that in 3 dimensional chess the possible steps of a knight to move next is thrice the possible steps it took in a regular chess. I think it's because there are 3 planes to consider.
Your assumption is wrong. A knight in a corner square of the lowest of the 8 boards has 6 instead of 2, but things go wrong pretty fast. A knight in the middle of a normal board has 8 moves. On a 3D board, he has 16 moves. The 8 original plus 1 up, 2 over in 4 directions and 2 up 1 over in 4 directions. A knight in any of the central 216 cubes will have 24 possible moves, 3 times more than a knight on an analogous central square, but the ratio is far from consistent.
Steve's Mathy Stuff yeah you are right. I generalize stuff too quickly. Here's my another approach Since there are 3 planes (which I named P, Q and R), each of the planes have same value as the original chess. I assign plane P as the yz plane, Q as xz plane and R as xy plane. For any starting point K, the value of that K will be the sum of values corresponding to each of the planes P, Q and R. For example the starting point of a knight in 3d chess is at K(1,0,1), the possible steps of a knight will be P(0,1) + Q(1,1) + R(1,0) = 3+4+3=10, referring to the values of the chess. So there are 10 possible steps a knight moves in its starting point at K(1,0,1). Now for the average time to return to starting point K(1,0,1), the reciprocal of the stationary distribution at K(1,0,1), in which the sum of all values in the cube is 8064, is 806.4
Full details of my approach here: i.imgur.com/fz5XVGh.jpg and for detailed solution (in excel): 1drv.ms/x/s!AnRu5ib36UbThl1v6WY9ZSU460en Value for K(1,0,1) is in yellow
Well, at 5:40 what you have calculated is not the chance of returning to k-pop from a k-pop, just the waiting time for a random song being k-pop... If you listen to k-pop you get the average waiting time: 2/3 + SUM[n * 1/3^2 * 2/3^(n-2)], n = 2 to infinity = 1.5 (you can either achieve it in one song, this has the probability of 2/3, or you can have two switches between the two genres with both of them having the probability of 1/3 and n - 2 times a switch from ska to ska, where n is the number of song changes). Am I wrong?
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.
Awesome video once again! im a little wasted but i think i know the answer to the rook problem, Rook can move on every square to 14 possible squares so 64 squares times 14 moves is 896 896 divided by 14 is 64 average moves. my explanation sucks but im glad i can do this drunk without a calculator :') Keep it up tim
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!
This was a very nice way to introduce markov chains and it reminded me about random walks in lattices, or planes with integer coordinates, as the wikipedia article formulates it. Keeping the chess perspective, the probability of a king returning to its starting point if the board is infinitely large, is one. However, in a three-dimensional lattice, the probability for the king to ever return to its starting square is only 0.34. en.wikipedia.org/wiki/Random_walk#Higher_dimensions and mathworld.wolfram.com/PolyasRandomWalkConstants.html But what about the knight, what is the probability that a knight ever returns to its starting square if the board is infinitely large (and two-dimensional)? BTW. Love your videos!
If I understand things correctly, the knight from the corner should take an average of 168 moves to get back to the same corner. A rook can move to 14 other squares from any square on the board. If you put 14 rooks at every square that is 896 rooks, and each square has 1/64th of the rooks. The rook then starting at any square, has an average of 64 moves before it returns to the original square.
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 RUclips 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
Thank you for doing this without dumbing things down
Can a chess piece explain Markov chains? No, but PBS Infinite series can explain Markov chains with chess and radio stations.
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.
Starting on their original squares:
King = 84
Queen = 69
Bishop = 40
Knight = 112
Rook = 64
Nice
Nice
Nice
Nice
Omg, these videos are amazing!!! They explore actually interesting topics, rather than boring old basic math. Please keep up the good work!!
Came back to this channel after 5 years, from some chess content that I'm really into nowadays. One of the best channels on RUclips
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!
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!
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!
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.
I feel alive each time I watch an episode from this awesome channel !!!
You are alive
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.
Can't get over how amazing this channel is. Seriously thank you.
The production value is crazy good on these, all of the diagrams are very well done. I wish they were still making them.
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.
Where does the 2/3 and 1/3 come from when you changed the probabilities of the radios?
These videos are so great! I wonder what the next topic will be! Maybe something with integrals?
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.
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!!!
Loved this video! Haven't seen any of the older ones... let the binge begin.
Just watched every episode (so far)!!! New favorite channel!!!!!!!!
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 !
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 ;)
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!
The important question is, what is Kelsey's FIDE rating?
this mathematician is a deadly combination of beauty and brains!!!!! thanks for making it interesting and easier.😂😂😂😂
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
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 love your delivery, you are the best host in all the PBS series (nothing to do with me being a mathematician hahahahah)
Very comprehensive explanation, thanks! Great channel!
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!
These videos are soo great! I wish they came out more often!
Love these videos! I feel like I've learned more from PBS Digital Studios than my university. Keep up the great work!
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
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
Fantastic video! Very powerful information explained in an accessible way
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?
Kelsey is really elegant.
...btw, plz, make more videos on hyper dimensional geometry :D
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
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!!
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!
Can the knight cover every square on the board exactly once? If so, from how many starting positions?
It can! This is a pretty famous old problem, called a knight's tour. The wikipedia article (en.wikipedia.org/wiki/Knight's_tour) has a good overview and history section. You can also try to do a knight's tour on other size chessboards and non-square ones -- it's sometimes possible and sometimes not.
The Knight's tour is a great puzzle! I love them, check them out.
It can do it from any starting positions
And now I'd like to know with what probability knight makes a closed knight's tour or in other words what is the ratio of Hamiltonian cycles to paths/cycles with the length of 64.
i.e. is the knight transition function Hamiltonian on the state-space of the 8 X 8 board?
Great channel. Hope to see more content you pick good subjects. I also hope more people get to know about it !
6:30 Where do the 2/3 and 1/3 come from, how are those calculated from the transition probabilities?
Assumption 1 hop per sec
if knight starts from A1 it will take 168 sec
if Rook starts from A1 then it will take 112 sec
in the case of rook, we have 2 moves per corner so 4 set of 2 moves
3 moves along the edge so 24 set 3 moves
and at rest square, it will have 4 moves
hope it was helpful
In case, If I am wrong please correct me
Thank you
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?
Man I still sad this series ended like other RUclips series it actually does a good job at explains it.
Really cool video with a deep explanation, thanks!
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)
Love your explanation.... You are an angel... Great job and God Bless you
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.
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.
Awesome channel. Hope there will be more challenges.
Knight - 168 hops, Rook - 1/(14/896) = 64 hops.
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!
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.
Excellent video! Thanks for all the hard work.
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.
Wow, two really good videos in a row from this presenter. That's a sub!
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)
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.
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!!!
Nice to see that math channels get more and more popular :)
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.
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.
PBS, bring this channel back!
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.
Cool like a chill! Keep up the great content!!
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
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.
Hello from Germany :D here are my answers:
Knight on corner: 1/(2/336) = 168
Rook on corner: 1/(14/(14*8*8)) = 64
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).
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.
The movements of the rooks are completely symmetric, in the sense that, in every given path, you could swap some rows and columns and it would still be a valid path. Thus, the stationary distribution has to be uniform across the board, so for it to sum 1 it's 1/64 on every cell: thus it takes an average of 64 moves
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.
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!
I'm a simple man. I hear a mathematician swear, I upvote.
The other way to estimate this is to use a sampling method. i.e. you start from a state, count the number moves it took you to get back to start state. Perform this sampling till you reach ergodicity. With this can easily calculate the mean to get the expected number of steps.
Awesome show! Keep the explanations coming!
I did this for every piece to see which one would take the longest to get back to its starting point and what square it would start on.
1st place goes to the knight starting in the corner with 168 moves
2nd was the king starting in the corner with 127 moves
3rd was the knight starting on the four spaces adjacent to the corners with 112 moves also with 112 moves is a pawn on the top or bottom row(I let the pawn be able to move forward and backwards in the scenario but does not go side-to-side or diagonal)
This emboldens me to take stochastic processes this semester. Great video, thank you!
You might want to check what topics does the course cover, it might not mainly focus on Markov chains. (But other parts of probability theory are also a lot of fun!)
I believe it covers markov chains and other random processes. I remember seeing my friend who took the course last year working on this chess board problem. Gonna be so fun!
It probably will be! :-)
How do I calculate the stationary distribution at any state (x)?
amazing videos! Love the intro sound.
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.
On average - I like every second video of yours, on average.
Your Chanel is amazing, loved the work. I will encourage all of my friends to subscribe it.
What will be the average number of steps would take for a knight to return to its starting point in a 3-dimensional chess? or multi-dimensional? Does stationary distribution apply to higher dimensions?
Correct me if I'm wrong with this assumption, I found out that in 3 dimensional chess the possible steps of a knight to move next is thrice the possible steps it took in a regular chess. I think it's because there are 3 planes to consider.
So the possible steps a knight will take to return to its starting point in a 3 dimensional chess is the same as in a regular chess.
Your assumption is wrong. A knight in a corner square of the lowest of the 8 boards has 6 instead of 2, but things go wrong pretty fast. A knight in the middle of a normal board has 8 moves. On a 3D board, he has 16 moves. The 8 original plus 1 up, 2 over in 4 directions and 2 up 1 over in 4 directions. A knight in any of the central 216 cubes will have 24 possible moves, 3 times more than a knight on an analogous central square, but the ratio is far from consistent.
Steve's Mathy Stuff yeah you are right. I generalize stuff too quickly. Here's my another approach
Since there are 3 planes (which I named P, Q and R), each of the planes have same value as the original chess. I assign plane P as the yz plane, Q as xz plane and R as xy plane.
For any starting point K, the value of that K will be the sum of values corresponding to each of the planes P, Q and R.
For example the starting point of a knight in 3d chess is at K(1,0,1), the possible steps of a knight will be P(0,1) + Q(1,1) + R(1,0) = 3+4+3=10, referring to the values of the chess. So there are 10 possible steps a knight moves in its starting point at K(1,0,1).
Now for the average time to return to starting point K(1,0,1), the reciprocal of the stationary distribution at K(1,0,1), in which the sum of all values in the cube is 8064, is 806.4
Full details of my approach here: i.imgur.com/fz5XVGh.jpg
and for detailed solution (in excel): 1drv.ms/x/s!AnRu5ib36UbThl1v6WY9ZSU460en
Value for K(1,0,1) is in yellow
Well, at 5:40 what you have calculated is not the chance of returning to k-pop from a k-pop, just the waiting time for a random song being k-pop... If you listen to k-pop you get the average waiting time:
2/3 + SUM[n * 1/3^2 * 2/3^(n-2)], n = 2 to infinity = 1.5
(you can either achieve it in one song, this has the probability of 2/3, or you can have two switches between the two genres with both of them having the probability of 1/3 and n - 2 times a switch from ska to ska, where n is the number of song changes). Am I wrong?
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.
My new favorite channel
Very good explanation about markov chains. You can make a video about hidden markov chains^^
Awesome video once again!
im a little wasted but i think i know the answer to the rook problem,
Rook can move on every square to 14 possible squares
so 64 squares times 14 moves is 896
896 divided by 14 is 64 average moves.
my explanation sucks but im glad i can do this drunk without a calculator :')
Keep it up tim
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!
This was a very nice way to introduce markov chains and it reminded me about random walks in lattices, or planes with integer coordinates, as the wikipedia article formulates it. Keeping the chess perspective, the probability of a king returning to its starting point if the board is infinitely large, is one. However, in a three-dimensional lattice, the probability for the king to ever return to its starting square is only 0.34.
en.wikipedia.org/wiki/Random_walk#Higher_dimensions
and
mathworld.wolfram.com/PolyasRandomWalkConstants.html
But what about the knight, what is the probability that a knight ever returns to its starting square if the board is infinitely large (and two-dimensional)?
BTW. Love your videos!
If I understand things correctly, the knight from the corner should take an average of 168 moves to get back to the same corner.
A rook can move to 14 other squares from any square on the board. If you put 14 rooks at every square that is 896 rooks, and each square has 1/64th of the rooks. The rook then starting at any square, has an average of 64 moves before it returns to the original square.