# Calculating the Shannon entropy

Recall that the Shannon entropy of a random variables X taking values in a finite set S is given by $$H[X] = −\sum_{x∈S}Pr[X = x] \log_2 Pr[X = x].$$ (We set $$\log_2 0 = 0.)$$ For a pair of random variables $$(X, Y )$$ taking values in the finite set S × T, we write

$$H[X | Y = y] = −\sum_{x∈S}Pr[X = x | Y = y] \log_2 Pr[X = x | Y = y]$$ and

$$H[X | Y ] = −\sum_{y∈T}Pr[Y = y]H[X | Y = y].$$

Now, consider an 1024 × 1024 chess board. Suppose 1024 rooks are placed one after another randomly at distinct locations on a 1024 × 1024 chess board so that no rook attacks another: that is, the i-th rook (i = 1, 2, . . . , 1024) is placed at a location chosen uniformly from among the available possibilities so that it does not attack any of the previously placed rooks. Let $$R_i$$ be the row number of the i-th rook and $$C_i$$ its column number. What is $$H[R_{513}, C_{513} | R_1, R_2, . . . , R_{512}]$$?

Using the above formula, we get

$$H[R_{513}, C_{513} | R_1, R_2, . . . , R_{512}]=−\sum_{y∈T}Pr[R_1, R_2, . . . , R_{512} = y]H[R_{513}, C_{513} | R_1, R_2, . . . , R_{512} = y]$$

No idea how to proceed form here/interpret what this means. Can someone help?

## 1 Answer

You can start by first tackling the easier $$H(R_2,C_2|R_1)$$. First write (using fundamental properties of joint entropy)

\begin{aligned} H(R_2,C_2|R_1) &= H(R_2|R_1)+H(C_2|R_1,R_2)\newline & = H(R_2|R_1)+H(C_2) \end{aligned} because $$R_1, R_2$$ do not impose any restriction in the selection of $$C_2$$.

Now, $$H(R_2|R_1)=\sum_{r=1}^N\frac{1}{N}H(R_2|R_1=r)=\log_2(N-1)$$, where $$N=1024$$. Also, $$H(C_2)=H(C_1)+H(C_2|C_1)-H(C_1|C_2)$$ (show it). $$H(C_1|C_2)$$ and $$H(C_2|C_1)$$ are computed similarly to $$H(R_2|R_1)$$ and are easily shown to be equal, therefore, $$H(C_2)=H(C_1)=\log_2(N)$$ and

$$H(R_2,C_2|R_1) = \log_2(N-1)+\log_2(N)$$