0
$\begingroup$

Would you please help me to understand the conditional entropy in this example which I got stuck in?

The example Considers 4 uniformly popular binary vectors, for example; {f1,f2,f3,f4} each with entropy F bits. So H(f1)=H(f2)=H(f3)=H(f4)=F bitS. It is assumed that pairs {f1,f2} and {f3,f4} are independent, while correlations exist between f1 and f2, and between f3 and f4.

Now they mentioned that "Specifically, H(f1|f2) = H(f2|f1) = F/4 and H(f3|f4) = H(f4|f3) = F/4." My question is how the answer is F/4?and why it seems it is so obvious?

I understand that since these vectors are uniformly popular so the probability of picking each of them is 1/4. and since pairs {f1,f2} and {f3,f4} are independent so the probability of picking each pair is 1/2. So I think the conditional entropy H(f1|f2) = H(f2|f1) for example, should be F/2, not F/4. Could somebody please help me to understand the answer? why it is F/4?

$\endgroup$
  • 1
    $\begingroup$ Welcome to MSE. I'm not sure what "uniformly popular binary vectors" means (and Google finds no other occurrence of those four words together in the whole Internet). Could you clarify? $\endgroup$ – leonbloy May 17 at 15:08
  • $\begingroup$ Thank you for your answer. In this example, it means we have 4 binary vectors (files) and the probability of picking each of these vectors (files) is 1/4 ( they are uniformly selected). (Assume that we have 4 files and users want to request for one of these files, since these files have the same popularity, the probability that each of these files is requested by each user is 1/4) $\endgroup$ – Bonnie May 17 at 15:21
  • 1
    $\begingroup$ Sorry, I cannot make sense of this. $\endgroup$ – leonbloy May 17 at 15:29
  • $\begingroup$ This doesn't make sense unless you know how $f_1$ and $f_2$ are related (i.e., the joint distribution), and similarly for $f_3, f_4$. Are you certain that they're not giving you more information somewhere? If definitely not, are you sure they aren't just describing the setting - i.e., they are telling you what the conditional entropies are as a given? Linking the source of these statements would likely help resolve this. $\endgroup$ – stochasticboy321 May 17 at 20:11
  • $\begingroup$ @ stochasticboy321 They mentioned that "we assume the joint distribution of the files, denoted by Pf, is not necessarily the product of the file marginal distributions". and regards the correlation they mentioned that"For a given threshold δ≤1 and file size F, we say file f1 is δ-correlated with file f2 if H(f1 ,f2 ) ≤ (1 + δ)F bits." These are the only extra information that they provide. Because of the word " specifically" in their paper, It seems to me that this should be so obvious and it is related to the uniform popularity of the files! but I don't understand it how? $\endgroup$ – Bonnie May 18 at 15:40

Your Answer

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

Browse other questions tagged or ask your own question.