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!
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
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.
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!
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 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.
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.
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
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 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.
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.
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.
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
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 ;)
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.
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.
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
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.
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 !
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.
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 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.
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
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!
The Rook takes an average of 64 steps. Each square has an equal amount of possible steps of 14. Giving each a state a stationary distribution of 14/(8*8*14).
For your questions: 1. Looking at the diagram from before, By computing 2/336, the stationary distribution at state (x) is 1/168. Therefore, it will take 168 moves on average. 2. A rook on any square will have fourteen possible squares, so each of the 64 squares will have the same stationary distribution value of 1/64. Therefore, the average number of moves for the rook is 64.
1) 168 - the probability is 2/336 = 1/168, so because of the theorem, the average is 168 steps 2) 64 - every place can get to 14 other places and 14 others can get to it, so the distribution is exactly even - 1/64, and 1/(1/64) = 64
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.
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
For the rook, no matter where on our chessboard our rook is, it can move to any one of 14 squares at random, with uniform probability density; therefore we can expect 64 rook moves no matter where our rook starts.
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 at corner 336/2*60 min Rook at corner(or at any other position) 14*64/14*60 min For any one of the two bishops 7*32/7*60 min as it can cover only the dark or light squares.
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!
I think we can do this technique in a vastly more general setting than in the video (I mean for more kind of chess pieces and more chess table shapes). If the Markov chain looks as follows: For every arrow present, its reversed version is also present. From every state, the weight of every arrow that is going out of this state is the same. Then you can just do the same technique as in the video, you number the states by the arrows going out of there and you divide it by the total number of arrows (if we assume for the sake of simplicity that every state can be reached from every other state) and you get the expected time for the first return. Observe that this works for all kind of (chess?) pieces that have moving rules such that if they move somewhere, they can immediately return from that place. And this also works for all kinds of chessboards (even disconnected ones!) you only need that from any square, you can eventually get to any other square with your weird chess piece. This video is a nice buildup for a video about random walks on the integers, and random walks on the integers "on the plane" and "in 3d space" which might culminate in the sentence: A drunk person will eventually find his home, but a drunk bird might not. :-)
If anybody was wondering what it works out to when the knight's starting position is *also* randomized (which was my first impression of what the problem was before it was explained a little bit more), it works out to 75.25.
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 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.
it would take 168 moves on average for a knight placed in the corner to return to the same position (1 divided by 1/168) it would take 64 moves on average for the rook to return to the initial position. Each step the rook can move to 14 different positions. Hence, each field has 14 assigned. This makes 8 * 8 * 14 = 896 in total leaving 14 / 896 = 1/64. Following the same procedure, the rook returns on average in 1 divided by 1/64 = 64 moves.
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)
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
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!
For each piece in their classic starting positions in chess, The rook would take 64 moves (average) to return to its original position. The knight takes, of course, 112 moves. Each bishop would take 43.14 moves The king would take 91.2 moves The queen would take 30.38 moves. I did not calculate the pawn. But if it is strictly a pawn, it will never return to its original position. If we allow it to change pieces once it reaches the back, it could return to its original position.
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.
Concerning the Rook question... everyone's probably checking to see what happens when it has an equal chance of each space... I've decided to skew the odds and see what happens. A Rook on any given space is more likely to move to a closer space according to the rules below: - The closest space to the CurrentState has a 7! weight - The second closest space to the CurrentState has a 6! weight - The third closest space to the CurrentState has a 5! weight - etc. Calculate the weight of all possibilities from a single CurrentState to calculate the odds of any movement. If my calculations are correct, the average number of moves for a Rook starting on a corner to return to that same corner is 109.1013... . On the other hand, a Rook starting on a center square would take only 54.7451... moves. Of course... that's only IF my calculations are correct. I mostly wanted to pose such a puzzle.
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!
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.
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)
Rook, queen and bishop: 64, but that is true regardless of the spot on the board. Though they each have a different number of spaces to which they can jump, that number is invariant across the board. The rook always has fourteen, the bishop always seven, and the queen always 21. Because of the invariant nature of the movement options, the variable ends up cancelling out. In fact, it can be proven fairly simply that if a piece has the ability to cross the entire board either diagonally, vertically, horizontally, or all three, on any square board with side lengths N, then the average number of hops a randomly hopping piece will take to return will always be N^2 pieces. We can generalize even further to demonstrate that a piece has the board crossing ability on a cubic chess board which has M dimensions with side length N, in any direction such that all tiles are connected by an edge or vertex, then the piece will return to it's starting position an average of N^M hops. While I can't show the math easily in my head, the proof is in the fact that with that board crossing ability, your piece can always move to N-1 spaces in all valid directions for that piece. So for example, the equivalent of a queen on a cubic chess board could move N-1 spaces in the vertical, horizontal, lateral, and on the 45 degree diagonal of all three axes, regardless of its position on the board
I mean, I know it's branding, but dividing 336 by 2 is hardly a challenge :) The rook challenge is more interesting, though, because no matter where it is on the board, rooks always have the same number of legal moves (seven other squares in its rank, plus seven other in its file). In fact, the rook is the only chess piece with this property. There are 64 squares on the board, so it'll take 64 moves for the rook to return, no arithmetic required.
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.
I have a feeling if you do this a lot of times and graph the times on a graph, it will look Ziphian. When a knight is close, there's a chance it will go right back to where it started. If it goes away though, it may take a lot longer to get back.
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
Thank you for doing this without dumbing things down
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
Can a chess piece explain Markov chains? No, but PBS Infinite series can explain Markov chains with chess and radio stations.
Starting on their original squares:
King = 84
Queen = 69
Bishop = 40
Knight = 112
Rook = 64
Nice
Nice
Nice
Nice
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.
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 TH-cam
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'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!
I feel alive each time I watch an episode from this awesome channel !!!
You are alive
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.
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!
Can't get over how amazing this channel is. Seriously thank you.
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 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.
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!
The important question is, what is Kelsey's FIDE rating?
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?
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!
Loved this video! Haven't seen any of the older ones... let the binge begin.
Where does the 2/3 and 1/3 come from when you changed the probabilities of the radios?
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?
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.
Just watched every episode (so far)!!! New favorite channel!!!!!!!!
Very comprehensive explanation, thanks! Great channel!
Hello from Germany :D here are my answers:
Knight on corner: 1/(2/336) = 168
Rook on corner: 1/(14/(14*8*8)) = 64
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
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.😂😂😂😂
Kelsey is really elegant.
...btw, plz, make more videos on hyper dimensional geometry :D
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.
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).
Man I still sad this series ended like other TH-cam series it actually does a good job at explains it.
Love these videos! I feel like I've learned more from PBS Digital Studios than my university. Keep up the great work!
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.
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 your delivery, you are the best host in all the PBS series (nothing to do with me being a mathematician hahahahah)
These videos are so great! I wonder what the next topic will be! Maybe something with integrals?
These videos are soo great! I wish they came out more often!
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 ;)
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?
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.
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
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.
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 !
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!
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 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.
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
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!
The Rook takes an average of 64 steps. Each square has an equal amount of possible steps of 14. Giving each a state a stationary distribution of 14/(8*8*14).
For your questions:
1. Looking at the diagram from before, By computing 2/336, the stationary distribution at state (x) is 1/168. Therefore, it will take 168 moves on average.
2. A rook on any square will have fourteen possible squares, so each of the 64 squares will have the same stationary distribution value of 1/64. Therefore, the average number of moves for the rook is 64.
1) 168 - the probability is 2/336 = 1/168, so because of the theorem, the average is 168 steps
2) 64 - every place can get to 14 other places and 14 others can get to it, so the distribution is exactly even - 1/64, and 1/(1/64) = 64
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.
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
Excellent video! Thanks for all the hard work.
For the rook, no matter where on our chessboard our rook is, it can move to any one of 14 squares at random, with uniform probability density; therefore we can expect 64 rook moves no matter where our rook starts.
On average - I like every second video of yours, on average.
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
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!!
Knight at corner 336/2*60 min
Rook at corner(or at any other position) 14*64/14*60 min
For any one of the two bishops 7*32/7*60 min as it can cover only the dark or light squares.
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!
I think we can do this technique in a vastly more general setting than in the video (I mean for more kind of chess pieces and more chess table shapes).
If the Markov chain looks as follows: For every arrow present, its reversed version is also present. From every state, the weight of every arrow that is going out of this state is the same. Then you can just do the same technique as in the video, you number the states by the arrows going out of there and you divide it by the total number of arrows (if we assume for the sake of simplicity that every state can be reached from every other state) and you get the expected time for the first return.
Observe that this works for all kind of (chess?) pieces that have moving rules such that if they move somewhere, they can immediately return from that place. And this also works for all kinds of chessboards (even disconnected ones!) you only need that from any square, you can eventually get to any other square with your weird chess piece.
This video is a nice buildup for a video about random walks on the integers, and random walks on the integers "on the plane" and "in 3d space" which might culminate in the sentence: A drunk person will eventually find his home, but a drunk bird might not. :-)
I forgot to add, that these Markov chains (where this technique works) could be called "uniform choice Markov chains without one way roads".
If anybody was wondering what it works out to when the knight's starting position is *also* randomized (which was my first impression of what the problem was before it was explained a little bit more), it works out to 75.25.
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.
Knight from corner: 168 hops. (1/(1/168)). Rook from any position: 64 hops. (All locations have 14 possible moves, 14*8^2 = 896, 14/896 [or 14/(14*8^2)] = 1/64, 1/(1/64) = 64).
I'm a simple man. I hear a mathematician swear, I upvote.
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.
it would take 168 moves on average for a knight placed in the corner to return to the same position (1 divided by 1/168)
it would take 64 moves on average for the rook to return to the initial position. Each step the rook can move to 14 different positions. Hence, each field has 14 assigned. This makes 8 * 8 * 14 = 896 in total leaving 14 / 896 = 1/64. Following the same procedure, the rook returns on average in 1 divided by 1/64 = 64 moves.
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)
Nice to see that math channels get more and more popular :)
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
My new favorite channel
Wow, two really good videos in a row from this presenter. That's a sub!
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!
This was a much easier way of finding a probability distribution than my applied math class last semester
For each piece in their classic starting positions in chess,
The rook would take 64 moves (average) to return to its original position.
The knight takes, of course, 112 moves.
Each bishop would take 43.14 moves
The king would take 91.2 moves
The queen would take 30.38 moves.
I did not calculate the pawn. But if it is strictly a pawn, it will never return to its original position. If we allow it to change pieces once it reaches the back, it could return to its original position.
I think it's worth clarifying that "average" here means mean, not mode or median.
I've never seen anyone use “average” as anything other than “mean” unless explicitly stated, though.
People usually mean "mean" when they calculate it, but usually mean "median" when they are talking colloquially.
Wait, really?
Arturo Torres Sánchez When someone is talking about your average ______, they generally aren't asking you to take extreme values into account.
IamGrimalkin
It’s not worth clarifying. It’s super clear that average=mean. Basic math terminology
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.
168 for the knight and 64 for the rook. Great video btw
Fantastic video! Very powerful information explained in an accessible way
Concerning the Rook question... everyone's probably checking to see what happens when it has an equal chance of each space... I've decided to skew the odds and see what happens.
A Rook on any given space is more likely to move to a closer space according to the rules below:
- The closest space to the CurrentState has a 7! weight
- The second closest space to the CurrentState has a 6! weight
- The third closest space to the CurrentState has a 5! weight
- etc.
Calculate the weight of all possibilities from a single CurrentState to calculate the odds of any movement.
If my calculations are correct, the average number of moves for a Rook starting on a corner to return to that same corner is 109.1013... . On the other hand, a Rook starting on a center square would take only 54.7451... moves.
Of course... that's only IF my calculations are correct. I mostly wanted to pose such a puzzle.
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!
PBS, bring this channel back!
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.
Great channel. Hope to see more content you pick good subjects. I also hope more people get to know about it !
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)
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
amazing videos! Love the intro sound.
My suggestions are 50% math and 50% learning colors and shapes for toddlers. What is even happening?
I mean, I know it's branding, but dividing 336 by 2 is hardly a challenge :) The rook challenge is more interesting, though, because no matter where it is on the board, rooks always have the same number of legal moves (seven other squares in its rank, plus seven other in its file). In fact, the rook is the only chess piece with this property. There are 64 squares on the board, so it'll take 64 moves for the rook to return, no arithmetic required.
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.
I have a feeling if you do this a lot of times and graph the times on a graph, it will look Ziphian. When a knight is close, there's a chance it will go right back to where it started. If it goes away though, it may take a lot longer to get back.