Hcfyk

Why was Germany not as successful as other Europeans in establishing overseas colonies?

Was there a Viking Exchange as well as a Columbian one?

What are the potential pitfalls when using metals as a currency?

What does the "ep" capability mean?

How to make a pipeline wait for end-of-file or stop after an error?

The Defining Moment

Map of water taps to fill bottles

Phrase for the opposite of "foolproof"

How to write a column outside the braces in a matrix?

How do I reattach a shelf to the wall when it ripped out of the wall?

Why isn't the definition of absolute value applied when squaring a radical containing a variable?

How to get a plain text file version of a CP/M .BAS (M-BASIC) program?

Don’t seats that recline flat defeat the purpose of having seatbelts?

Why does nature favour the Laplacian?

Is there a way to get a compiler for the original B programming language?

Why do games have consumables?

How can I place the product on a social media post better?

Is this homebrew Wind Wave spell balanced?

Minor Revision with suggestion of an alternative proof by reviewer

How did Captain America manage to do this?

Do I have to worry about players making “bad” choices on level up?

Question about かな　and だろう

Interpret a multiple linear regression when Y is log transformed

What is Niska's accent?

Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?

Measuring entropy for a table (e.g., SQL results)Information of a stream of bitsCan a transcendental number like $e$ or $pi$ be compressed as not algorithmically random?How to compare conditional entropy and mutual information?Why the alphabet of the digital information is composed of 2 elements?One-shot Private Randomness ExtractorFind minimum conditional entropyHigher order empirical entropy is not the entropy of the empirical distribution?Conceptual overview: Self-information, Mutual information, uncertainty, entropyHow realistic is the i.i.d assumption in the definition of Shannon's entropy?

3

$begingroup$

Suppose we have a function $f$,

$$
C = f(A,B),
$$

where $A$, $B$ and $C$ are random variables.

I notice that when the random variables are binary ($0, 1$) and $f$ is the XOR operation, we have the following identity:

$$
H(C|A) = H(B),
$$

where $H(B)$ is the entropy of $B$ and $H(C|A)$ is the conditional entropy of $C$ given $A$.

Obviously this is not true for a general $f$. What I am interested to know is, is there a set of conditions on $f$ and $A,B,C$, under which the identity above holds.

information-theory

share|cite|improve this question

edited Apr 1 at 5:51

hklel

asked Mar 28 at 7:20

hklelhklel

1255

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The function needs to be injective with respect to its second argument.
  $endgroup$
  – Yuval Filmus
  Mar 28 at 8:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YuvalFilmus Ah that makes sense! I didn't know the term "injective". Do you want to elaborate a bit and write an answer so I can upvote it?
  $endgroup$
  – hklel
  Mar 28 at 8:11
  

  
  
  
  

add a comment | 

3

$begingroup$

Suppose we have a function $f$,

$$
C = f(A,B),
$$

where $A$, $B$ and $C$ are random variables.

I notice that when the random variables are binary ($0, 1$) and $f$ is the XOR operation, we have the following identity:

$$
H(C|A) = H(B),
$$

where $H(B)$ is the entropy of $B$ and $H(C|A)$ is the conditional entropy of $C$ given $A$.

Obviously this is not true for a general $f$. What I am interested to know is, is there a set of conditions on $f$ and $A,B,C$, under which the identity above holds.

information-theory

share|cite|improve this question

edited Apr 1 at 5:51

hklel

asked Mar 28 at 7:20

hklelhklel

1255

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  The function needs to be injective with respect to its second argument.
  $endgroup$
  – Yuval Filmus
  Mar 28 at 8:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @YuvalFilmus Ah that makes sense! I didn't know the term "injective". Do you want to elaborate a bit and write an answer so I can upvote it?
  $endgroup$
  – hklel
  Mar 28 at 8:11
  

  
  
  
  

add a comment | 

$begingroup$

Suppose we have a function $f$,

$$
C = f(A,B),
$$

where $A$, $B$ and $C$ are random variables.

I notice that when the random variables are binary ($0, 1$) and $f$ is the XOR operation, we have the following identity:

$$
H(C|A) = H(B),
$$

where $H(B)$ is the entropy of $B$ and $H(C|A)$ is the conditional entropy of $C$ given $A$.

Obviously this is not true for a general $f$. What I am interested to know is, is there a set of conditions on $f$ and $A,B,C$, under which the identity above holds.

information-theory

share|cite|improve this question

edited Apr 1 at 5:51

hklel

asked Mar 28 at 7:20

hklelhklel

1255

$endgroup$

share|cite|improve this question

edited Apr 1 at 5:51

hklel

asked Mar 28 at 7:20

hklelhklel

1255

share|cite|improve this question

edited Apr 1 at 5:51

hklel

asked Mar 28 at 7:20

hklelhklel

1255

asked Mar 28 at 7:20

hklelhklel

1255

asked Mar 28 at 7:20

hklelhklel

1255

2 Answers
2

active

oldest

votes

4

$begingroup$

The following answer assumes that $A,B$ are independent, and that $A,B$ have full support on their respective domains (the latter is without loss of generality). For the general case, see the other answer.

Let's write your equation in a slightly different way:
$$
H(B) = H(f(A,B)|A) = operatorname*mathbbE_a sim A H(f(a,B)).
$$
Clearly $H(f(a,B)) leq H(B)$, with equality if and only if $f(a,b_1) neq f(a,b_2)$ whenever $b_1 neq b_2$. We deduce that $H(B) = H(f(A,B)|A)$ if and only if $f$ is injective in its second argument, i.e., for all $a$ and $b_1 neq b_2$, we have $f(a,b_1) neq f(a,b_2)$.

share|cite|improve this answer

edited Mar 28 at 10:12

answered Mar 28 at 8:28

Yuval FilmusYuval Filmus

197k15187350

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  $H(f(A,B)|A)=mathbbE_aH(f(a,B)|A=a)$, and $H(f(a,B)|A=a)$ is different from $H(f(a,B))$ since $A$ and $B$ may be dependent.
  $endgroup$
  – xskxzr
  Mar 28 at 8:45
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  The conclusion that $f$ is injective in the second argument is only correct if $Pr(A=a)>0$ and $Pr(B=b)>0$ for all $(a,b)inoperatornamedom(f)$.
  $endgroup$
  – Emil Jeřábek
  Mar 28 at 10:03
  
  

  
  
  
  

add a comment | 

8

$begingroup$

Note

beginalign
0&=H(C|A,B)\
&=H(A,B,C)-H(A,B)\
&=H(B|A,C)+H(C|A)+H(A)-H(A,B)quadtext(chain rule)\
&=H(B|A,C)+H(C|A)-H(B|A),
endalign

so $H(C|A)=H(B)$ is equivalently $H(B|A,C)+H(B)-H(B|A)=0$. Also note $H(B|A,C)ge 0$ and $H(B)ge H(B|A)$, your condition is equivalently $H(B|A,C)=0wedge H(B)=H(B|A)$.

For a human-readable explanation, $H(B|A,C)=0$ means $B$ is determined by $A$ and $C$, that is, for any fixed $a$ in the support of $A$, $f(a,b)$ as a function of $b$ with domain $bmid mathrmPrA=a, B=b>0$ is an injection. $H(B)=H(B|A)$ means $A$ and $B$ are independent of each other.

share|cite|improve this answer

edited Mar 28 at 10:34

answered Mar 28 at 8:38

xskxzrxskxzr

4,36621033

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  The conclusion that $f$ is injective in the second argument is only correct if $Pr(A=a)>0$ and $Pr(B=b)>0$ for all $(a,b)inoperatornamedom(f)$.
  $endgroup$
  – Emil Jeřábek
  Mar 28 at 10:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @EmilJeřábek Thanks, fixed.
  $endgroup$
  – xskxzr
  Mar 28 at 10:34
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106156%2funder-what-conditions-does-the-function-c-fa-b-satisfy-hca-hb%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

The following answer assumes that $A,B$ are independent, and that $A,B$ have full support on their respective domains (the latter is without loss of generality). For the general case, see the other answer.

Let's write your equation in a slightly different way:
$$
H(B) = H(f(A,B)|A) = operatorname*mathbbE_a sim A H(f(a,B)).
$$
Clearly $H(f(a,B)) leq H(B)$, with equality if and only if $f(a,b_1) neq f(a,b_2)$ whenever $b_1 neq b_2$. We deduce that $H(B) = H(f(A,B)|A)$ if and only if $f$ is injective in its second argument, i.e., for all $a$ and $b_1 neq b_2$, we have $f(a,b_1) neq f(a,b_2)$.

share|cite|improve this answer

edited Mar 28 at 10:12

answered Mar 28 at 8:28

Yuval FilmusYuval Filmus

197k15187350

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  $H(f(A,B)|A)=mathbbE_aH(f(a,B)|A=a)$, and $H(f(a,B)|A=a)$ is different from $H(f(a,B))$ since $A$ and $B$ may be dependent.
  $endgroup$
  – xskxzr
  Mar 28 at 8:45
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  The conclusion that $f$ is injective in the second argument is only correct if $Pr(A=a)>0$ and $Pr(B=b)>0$ for all $(a,b)inoperatornamedom(f)$.
  $endgroup$
  – Emil Jeřábek
  Mar 28 at 10:03
  
  

  
  
  
  

add a comment | 

4

$begingroup$

The following answer assumes that $A,B$ are independent, and that $A,B$ have full support on their respective domains (the latter is without loss of generality). For the general case, see the other answer.

Let's write your equation in a slightly different way:
$$
H(B) = H(f(A,B)|A) = operatorname*mathbbE_a sim A H(f(a,B)).
$$
Clearly $H(f(a,B)) leq H(B)$, with equality if and only if $f(a,b_1) neq f(a,b_2)$ whenever $b_1 neq b_2$. We deduce that $H(B) = H(f(A,B)|A)$ if and only if $f$ is injective in its second argument, i.e., for all $a$ and $b_1 neq b_2$, we have $f(a,b_1) neq f(a,b_2)$.

share|cite|improve this answer

edited Mar 28 at 10:12

answered Mar 28 at 8:28

Yuval FilmusYuval Filmus

197k15187350

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  $H(f(A,B)|A)=mathbbE_aH(f(a,B)|A=a)$, and $H(f(a,B)|A=a)$ is different from $H(f(a,B))$ since $A$ and $B$ may be dependent.
  $endgroup$
  – xskxzr
  Mar 28 at 8:45
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  The conclusion that $f$ is injective in the second argument is only correct if $Pr(A=a)>0$ and $Pr(B=b)>0$ for all $(a,b)inoperatornamedom(f)$.
  $endgroup$
  – Emil Jeřábek
  Mar 28 at 10:03
  
  

  
  
  
  

add a comment | 

$begingroup$

The following answer assumes that $A,B$ are independent, and that $A,B$ have full support on their respective domains (the latter is without loss of generality). For the general case, see the other answer.

Let's write your equation in a slightly different way:
$$
H(B) = H(f(A,B)|A) = operatorname*mathbbE_a sim A H(f(a,B)).
$$
Clearly $H(f(a,B)) leq H(B)$, with equality if and only if $f(a,b_1) neq f(a,b_2)$ whenever $b_1 neq b_2$. We deduce that $H(B) = H(f(A,B)|A)$ if and only if $f$ is injective in its second argument, i.e., for all $a$ and $b_1 neq b_2$, we have $f(a,b_1) neq f(a,b_2)$.

share|cite|improve this answer

edited Mar 28 at 10:12

answered Mar 28 at 8:28

Yuval FilmusYuval Filmus

197k15187350

$endgroup$

share|cite|improve this answer

edited Mar 28 at 10:12

answered Mar 28 at 8:28

Yuval FilmusYuval Filmus

197k15187350

answered Mar 28 at 8:28

Yuval FilmusYuval Filmus

197k15187350

answered Mar 28 at 8:28

Yuval FilmusYuval Filmus

197k15187350

8

$begingroup$

Note

beginalign
0&=H(C|A,B)\
&=H(A,B,C)-H(A,B)\
&=H(B|A,C)+H(C|A)+H(A)-H(A,B)quadtext(chain rule)\
&=H(B|A,C)+H(C|A)-H(B|A),
endalign

so $H(C|A)=H(B)$ is equivalently $H(B|A,C)+H(B)-H(B|A)=0$. Also note $H(B|A,C)ge 0$ and $H(B)ge H(B|A)$, your condition is equivalently $H(B|A,C)=0wedge H(B)=H(B|A)$.

For a human-readable explanation, $H(B|A,C)=0$ means $B$ is determined by $A$ and $C$, that is, for any fixed $a$ in the support of $A$, $f(a,b)$ as a function of $b$ with domain $bmid mathrmPrA=a, B=b>0$ is an injection. $H(B)=H(B|A)$ means $A$ and $B$ are independent of each other.

share|cite|improve this answer

edited Mar 28 at 10:34

answered Mar 28 at 8:38

xskxzrxskxzr

4,36621033

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  The conclusion that $f$ is injective in the second argument is only correct if $Pr(A=a)>0$ and $Pr(B=b)>0$ for all $(a,b)inoperatornamedom(f)$.
  $endgroup$
  – Emil Jeřábek
  Mar 28 at 10:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @EmilJeřábek Thanks, fixed.
  $endgroup$
  – xskxzr
  Mar 28 at 10:34
  

  
  
  
  

add a comment | 

8

$begingroup$

Note

beginalign
0&=H(C|A,B)\
&=H(A,B,C)-H(A,B)\
&=H(B|A,C)+H(C|A)+H(A)-H(A,B)quadtext(chain rule)\
&=H(B|A,C)+H(C|A)-H(B|A),
endalign

so $H(C|A)=H(B)$ is equivalently $H(B|A,C)+H(B)-H(B|A)=0$. Also note $H(B|A,C)ge 0$ and $H(B)ge H(B|A)$, your condition is equivalently $H(B|A,C)=0wedge H(B)=H(B|A)$.

For a human-readable explanation, $H(B|A,C)=0$ means $B$ is determined by $A$ and $C$, that is, for any fixed $a$ in the support of $A$, $f(a,b)$ as a function of $b$ with domain $bmid mathrmPrA=a, B=b>0$ is an injection. $H(B)=H(B|A)$ means $A$ and $B$ are independent of each other.

share|cite|improve this answer

edited Mar 28 at 10:34

answered Mar 28 at 8:38

xskxzrxskxzr

4,36621033

$endgroup$

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  The conclusion that $f$ is injective in the second argument is only correct if $Pr(A=a)>0$ and $Pr(B=b)>0$ for all $(a,b)inoperatornamedom(f)$.
  $endgroup$
  – Emil Jeřábek
  Mar 28 at 10:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @EmilJeřábek Thanks, fixed.
  $endgroup$
  – xskxzr
  Mar 28 at 10:34
  

  
  
  
  

add a comment | 

$begingroup$

Note

beginalign
0&=H(C|A,B)\
&=H(A,B,C)-H(A,B)\
&=H(B|A,C)+H(C|A)+H(A)-H(A,B)quadtext(chain rule)\
&=H(B|A,C)+H(C|A)-H(B|A),
endalign

so $H(C|A)=H(B)$ is equivalently $H(B|A,C)+H(B)-H(B|A)=0$. Also note $H(B|A,C)ge 0$ and $H(B)ge H(B|A)$, your condition is equivalently $H(B|A,C)=0wedge H(B)=H(B|A)$.

For a human-readable explanation, $H(B|A,C)=0$ means $B$ is determined by $A$ and $C$, that is, for any fixed $a$ in the support of $A$, $f(a,b)$ as a function of $b$ with domain $bmid mathrmPrA=a, B=b>0$ is an injection. $H(B)=H(B|A)$ means $A$ and $B$ are independent of each other.

share|cite|improve this answer

edited Mar 28 at 10:34

answered Mar 28 at 8:38

xskxzrxskxzr

4,36621033

$endgroup$

share|cite|improve this answer

edited Mar 28 at 10:34

answered Mar 28 at 8:38

xskxzrxskxzr

4,36621033

answered Mar 28 at 8:38

xskxzrxskxzr

4,36621033

answered Mar 28 at 8:38

xskxzrxskxzr

4,36621033