5
$\begingroup$

Suppose we have an $n$ by $n$ chessboard and each square can be in two states: "on" or "off". At time $t=0$ all bits are off. Every second one square is selected at random uniformly out of the $n^2$ squares and the corresponding bit is flipped. How to define entropy of "on" bits in this process and show that it increases? This came out of a model of a gas in a container, where we divide the container using a grid. Each grid point is "on" or "off" iff there is a gas molecule in the corresponding square. It should increase on average right? Seems to me it could be related to the variance of the "on" squares but I am no expert in the field, any hints?

Thanks in advance!

$\endgroup$
4
  • 1
    $\begingroup$ This is relevant. In that form, it is only applicable to a $1$-dimensional random variable. I'm not sure how to generalize to multiple dimensions. $\endgroup$
    – Guy
    May 31, 2017 at 18:53
  • $\begingroup$ Why a chessboard? Why not an $n\times n$ grid? Am I missing something? $\endgroup$
    – Shaun
    May 31, 2017 at 18:53
  • $\begingroup$ I don't think so. I've seen chessboard being used to mean grid before, and while it does seem odd, I've gotten used to it. $\endgroup$
    – Guy
    May 31, 2017 at 18:54
  • $\begingroup$ I think one issue here is that you want some measure of how mixed the bits are, as well as how many are on and off, which is perhaps a different question than just entropy. To that end, this may help. $\endgroup$
    – RideTheWavelet
    May 31, 2017 at 18:59

1 Answer 1

Reset to default
2
$\begingroup$

A simple measure is just the number of configurations of the on bits. If $n$ bits are on there are $64 \choose n$ configurations they can be in, so you can say the entropy is $\log {64 \choose n}$. Initially $n$ increases rapidly because the chance you turn off an on bit is small. As $n$ approaches $32$ you will approach maximum entropy. There doesn't seem to be anything in the problem that involves the particular pattern of bits, so I wouldn't do anything more complicated.

$\endgroup$
1
  • $\begingroup$ Thanks! simpler than I thought.. $\endgroup$
    – plus1
    Jun 16, 2017 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.