0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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) $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .