0
$\begingroup$

Let us consider two sets $A$ and $B$. Suppose there exists a bijection $\phi:A\to B$ so that any $b\in B$ uniquely determines an element $a = \phi^{-1}(b)\in A$. In this sense, we can claim that the set $B$ gives us the `full information' of $A$ since every element in $A$ can be characterized by the element in $B$.

My question is, how can we interpret this bijection between two sets using information theory? How should we define probability distributions on $A$ and $B$ and use information theory to say `there is a bijection between $A$ and $B$'?

$\endgroup$
0
$\begingroup$

Saying that $X$ is a random variable and $Y=f(x)$ where $f$ is a (measurable) bijection is equivalent to say that the conditional entropies are equal to zero, $H(Y|X)=H(X|Y)=0$, this also implies that the mutual information is equal to their entropies $I(X,Y)=H(X)=H(Y)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hi Giovanni, thanks for the reply! In my question, I can define arbitrary random variables $X$ and $Y$ on the sets $A$ and $B$, respectively. Is there a specific way to determine the injection of the `deterministic' elements in $A$ and $B$? $\endgroup$ – mw19930312 Jul 16 at 20:30
  • $\begingroup$ I don't understand what you mean by 'determine the injection'. However, if there is a uniform distribution over $A$ and if $f$ is injective (deterministic) map to $B$. If $f$ is injective then for a uniform random variable $X$ over the set $A$, $H(X)=\log |A| =\log |f(X)|$. which should be equal to $|B|$. $\endgroup$ – lebesgue Jul 16 at 20:39
  • $\begingroup$ @lebesgue Thanks for the discussion. Maybe I should be more specific. Suppose we have r.v.s $X$ and $Y = f(x)$ where $f$ is a bijection. Then shall we say there also exists a bijection between the event spaces associated with these two r.v.s? $\endgroup$ – mw19930312 Jul 17 at 16:54

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.