Flip flop
A token is placed at one of 9 positions in a 3 × 3 grid according to a probability distribution P . After a token is placed into one of the positions of the grid, it is then moved uniformly at random to one of the horizontally, vertically, or diagonally adjacent positions. For each position on the board, the probability that the token is in that position after being moved is also given by the distribution P .
If two tokens are placed into the grid according to the distribution P and then moved, the probability that the set of occupied positions is the same before and after the tokens are moved can be expressed as b a where a and b are coprime positive integers. What is the value of a + b ?
The answer is 41.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
How does "symmetry" tell you that the 4 edge positions have the same probability and the 4 corner positions have the same probability?
Log in to reply
Unless I have missed something, the only features of the board that constrain the problem are the structure of transitions out of (and into) each location, and the demand that P is invariant under random hops to adjacent positions.
The structure of the transitions out of (and into) the locations is the same for all pieces that are in a corner and for all pieces that are on an edge (and the middle piece obviously has unique connectivity), and every spot on the board has the same P invariance under hops. That is the argument for the equivalence of all corners and all edges as well as the uniqueness of the middle spot.
Truer to the path taken, my first approach was writing down the transition matrix in full, seeing that the corner and edge variables have perfectly interchangeable roles in the equations, cursing my stupidity, excusing myself for it being almost bedtime, and then realizing on top of the symmetry feature, the system admits a unique solution.
Log in to reply
Why isn't it possible that there is an asymmetric probability distribution that still follows the problem's statement?
I'm pretty sure that the symmetric solution above is indeed the only solution, but the symmetric argument doesn't rule out the possibility of multiple solutions.
...Of course, unless you invoke something like "our system of 9 linear equations in 9 variables are linearly independent, and so it has to have a unique solution; an asymmetrical solution allows more than one solution and hence can be ruled out".
Log in to reply
@Ivan Koswara – The multiple arguments question is equivalent to "Are there multiple eigenvectors with all positive entries that satisfy T ⋅ x s s = x s s ?" where x s s is a nine entry vector describing the occupation probabilities of each square (equivalent to P ) and T is a matrix describing the transition probabilities from one square to another. Obviously any steady state distribution x s s must satisfy this equation if it is invariant under nearest neighbor hops.
We can apply the Perron-Frobenius theorem to show that there is only one such vector with all positive entries.
@Ivan Koswara – Does that argument actually work?
Log in to reply
@Matt McNabb – It works, but the argument is a little messy.
First, we take the system of equations. It would be somewhere along this line:
a = 5 b + 5 d + 8 e
b = 3 a + 3 c + 5 d + 8 e + 5 f
...and so on...
Where a , b , c , d , e , f , g , h , i are the probabilities of the token being on the top-left, top-middle, top-right, middle-left, middle-middle, ..., bottom-right position respectively.
We also have a + b + … + i = 1 .
Among the first 9 equations, one is reducible from the other (their sum is a + b + … + i = a + b + … + i , so one is useless); we assume that the remaining 8 are linearly independent from each other. Also, the last equation is also linearly independent from all the previous ones. The previous sentences haven't been proven but they seem likely; a laborious work can be done to prove it. So now we have a system of 9 linear equations in 9 variables.
We can use some basic linear algebra (in particular, the fact that a linearly independent matrix always has a unique inverse) to prove that a system of n linear equations in n variables that are linearly independent has exactly one solution. Thus our system of equations have exactly one solution.
Now observe that if ( a , b , c , d , e , f , g , h , i ) is a solution, then ( c , f , i , b , e , h , a , d , g ) is also a solution (the board rotated 90 degrees counterclockwise). So we need to have a = c , b = f , c = i , … , i = g , otherwise the system has multiple solutions. This reduces to all probabilities of corner squares being equal, and similarly with edge squares.
So. Bashy. Took me forever to solve this.
But, where do you count the possibility that they are placed on the same square? I actually understood they have to be placed on the same square and then moved randomly, both ending up in adjacent square. Oddly, I got the same solution, 1/40.
In P edg = P mid/8+2P crn/3 it is not accounted for the case when a token is moved from one edge piece to the other edge piece, +2P edg/5 for two adjacent edges
There are 20 possible transitions, all invertible. It follows that all of them will have an equal probability of being used. Two tokens will exchange places iff they use a pair of transitions that is an inverse pair. So, fixing the transition that Token 1 takes, there is exactly a 4 0 1 chance that Token 2 takes the inverse transition, and our final answer is 1 + 4 0 = 4 1 .
Did you mean 40 possible transitions? I assume that by "transitions" you mean "ordered pairs of adjacent squares" .
Why does it follow that each one has an equal probability of being used? (It turns out that this is true for the distribution that Josh Silverman worked out, but so far nobody has shown that there are no other possible distributions).
The probability distribution of the board can be visualized as
The probabilities for all four edge spaces are equal by symmetry. Similarly, the corner spaces all have equal probability.
We know that a space is just as likely to be occupied before moving as it is after moving. This gives us three relations that uniquely determine the distribution.
Consider a single corner piece: It can be moved into from the middle piece or from either of its adjacent edge pieces, this means that P c r n = 8 P m i d + 5 2 P e d g e because the middle piece has 8 choices of where to move and the edge pieces each have 5 choices of where to move.
Similarly, for an edge piece, we have
P e d g e = 8 P m i d + 3 2 P c r n
For the middle we have
P m i d = 3 4 P c r n + 5 4 P e d g e
Finally, the probabilities must sum to unity
P m i d + 4 P c r n + 4 P e d g e = 1
This system is solved by ( P m i d , P e d g e , P c r n ) = ( 5 1 , 8 1 , 4 0 3 )
Now, the only setups for which the board can remain unchanged under the random move are those in which the board was placed with two tokens on adjacent squares. For example, one token could be placed on the middle square with the second token on a corner.
The probability that the occupation is placed in an adjacent setup and that it remains the same occupation after the random move is given by P c r n P ( c r n → m i d ) P m i d P ( m i d → c r n ) = 4 0 3 × 3 1 × 5 1 × 8 1 = 4 0 2 1 = 1 6 0 0 1
In fact, this is true for every pair of adjacent squares; there is detailed balance along every border between squares.
All that remains is to count the number of arrangements that feature adjacent squares. This is equal to the total number of destinations for tokens starting on each of the nine squares, i.e. 3 + 3 + 3 + 3 , 5 + 5 + 5 + 5 , and 8 for the corner, edge, and middle pieces respectively, making a total of 40 arrangements where occupation-invariance is possible.
The probability is thus given by P i n v a r i a n c e = 4 0 2 4 0 = 4 0 1 .