I was given the following problem in a technical interview:
Suppose you have a normal 8x8 chessboard, and crickets are placed on every single square. The crickets begin to hop from square to square at random. Every cricket hops to every square on the board with equal probability, and there is no limit to how many crickets fit on a single square.
Here is the question: We let them hop for a little bit, and then take a picture of the board. How many squares do we expect to find empty?
At first, I thought this would be easy. The crickets hop completely independent of one another, so it should just be some riff on the regular binomial distribution. When you try to work it out, though, you realize that the events we're logging are not independent, since whether a given cricket lands on an empty square depends on where the crickets before him have landed.
Every attempt I make to solve this ends up involving variants of the partition function. I haven't been able to get a good answer. I'm wondering if anyone sees an obvious solution, or a non-obvious one. I'm also interested in how this problem looks if you start making the chessboard get bigger, up to size infinity.
Isn't this precisely a binomial distribution, because we have 64 crickets and place each randomly on one of 64 squares? (The starting arrangement and the intermediate hops are irrelevant.) The probability is thus $0.364987$.