The Chessboard High Five Problem
Just another day, when I was browsing through my Instagram feed, my friend sent me this interesting yet not so difficult problem involving understanding of basic probability, counting and bit of time to pause the temptation to scroll the rest of your Instagram feed.
So, the problem went like this..
Imagine you have a regular 8 x 8 chessboard, with 64 people standing on each of the 64 squares. At the same time every person turns to face one of their neighbors with equal chances i.e. say the person near the center of the chessboard can face any direction with 1/4 probability, a person at the top of the chessboard (but not the corners) has probability 1/3 to face any of its neighbors, similarly all others. Now, if two people are facing each other they give each other a high five. Find the expected number of high fives.
The keys to most expectation finding problem are:
i. Clearly defining the random variable (r.v.) whose expectation needs to be found.
ii. Writing that r.v. in terms of sum of smaller problems, which in most cases are symmetric or has some systematic pattern or form.
iii. Leverage the power of Indicator r.v. as they are bridge between expectation and probability.
iv. Exploiting linearity of expectation wherever possible.
We will go about mathematically framing the problem, trust me it’s not difficult and you can go about mathematically putting down any problem in this form specially for probability.
Let X be a r.v. which stands for the number of high fives on our chessboard. Fine, we now have a hold of the r.v. whose expectation needs to be found. Now, at a first glance it might feel like we know nothing about probability distribution of X, indeed that’s the case and finding the probability distribution will no doubt be much more involved and lengthy. But wait, we have a savior to come to our rescue. The point (iv) — Linearity of Expectation. To use it, we want to break the problem into smaller pieces which are much easier.
Observe, it is much easier to focus on horizontal high fives and vertical high fives one at a time. Thus, we may start by writing
Arguably, the two terms on the right hand side are easier to handle compared to X on its own. We now turn towards using point (iii) i.e. taking advantage of Indicator r.v.s. (a fancy counting tool, very useful in probability). We will count the number of horizontal and vertical high fives using indicators as shown below. Where I_i takes value 1 if there is a high five between the two squares shown in the diagram below otherwise 0. Similarly, J_i (vertical equivalent of I_i).
The following diagram would make things bit clearer.
Hence, now as the final step, we club all we have and take expectation and calculate the relevant probabilities below,
In the last step, I took expectation and by symmetry the expectation of the number of horizontal high fives will be the same as the expectation of the number of vertical high fives.
As we are dealing with only horizontal high fives, we notice that the 6 rows except the first and last row will have identical expectation (by symmetry) and the first and last row will have identical expectation (by symmetry).
As Expectation of Indicator is probability of the indicator taking value 1. This is the reason why I said it bridges expectation and probability.
We know the probabilities of each person facing a particular direction. So, the probability that two persons facing are each other is simply the product of the probability of one person facing in a particular direction (say right) and another person in that pair facing the opposite direction (i.e. left). Let’s walk through few of the probabilities below, I_7 = 1 if the person in the top right corner faces left and the person to the left of him faces right. The probability of them facing each other is 1/2 * 1/3. Similarly, we can work out the others.
Plug all these values in and we get,
Is my answer correct? The following is a simulation of the above setup and from Strong Law of Large Numbers the sample mean of the number of high fives seen over large number of games will converse almost surely to the expectation.
import random
center_choices = [-2, -1, 1, 2] # -2 means faces up, -1 means faces left, 2 means faces down, 1 means faces right
corner_choices_tl = [1, 2] # top left corner
corner_choices_tr = [-1, 2] # top right corner
corner_choices_bl = [1, -2] # bottom left corner
corner_choices_br = [-1, -2] # bottom right corner
top_choices = [-1, 2, 1] # top side (except corners)
left_choices = [-2, 1, 2] # left side (except corners)
right_choices = [-2, -1, 2] # right side (except corners)
bottom_choices = [-1, -2, 1] # bottom side (except corners)
def numHighFives(): # returns the number of high fives everytime for a new configuration
chessboard = [[random.choice(corner_choices_tl), *random.choices(top_choices, k=6), random.choice(corner_choices_tr)]]
for _ in range(6):
chessboard.append([random.choice(left_choices), *random.choices(center_choices, k=6), random.choice(right_choices)])
chessboard.append([random.choice(corner_choices_bl), *random.choices(bottom_choices, k=6), random.choice(corner_choices_br)])
high_fives = 0
for i in range(8):
for j in range(8):
if (i-1 >= 0):
if (chessboard[i-1][j] == 2 and chessboard[i][j] == -2):
high_fives += 1
if (j-1 >= 0):
if (chessboard[i][j-1] == 1 and chessboard[i][j] == -1):
high_fives += 1
return high_fives
N = 1000
print(f"Average Number of High Fives in {N} random configurations: {sum([numHighFives() for _ in range(N)]) / N}") # Looking at N games and taking averageThe output of the above simulation is
Average Number of High Fives in 1000 random configurations: 9.306I hope you enjoyed going through the solution. Finally, its time to get back to scrolling rest of my Instagram feed :P
