Tag Info

Hot answers tagged

3

There are multiple models of entropy that take into account correlation between the bits. The model you have is a first-order model according to http://www.data-compression.com/theory.html#entropy or Shannon's 1948 paper. A second- or third-order model would account for the fact that some two-letter or three-letter combinations are more likely than others.


2

There seems to be some misunderstandings in your question. First, when you speak of "the case where the bits are highly correlated" ... are you thinking of a source that produces always (or with high probability) such patterns ? Or are you thinking of particular realizations? In the second case, you must understand that the traditional definition of entropy ...


2

Formally, Birkhoff's ergodic theorem states that for an integrable function $f$, the time average equals the space average: $$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=0}^{n-1} f(T^i(x)) = \int_S f(x) d\mu(x).$$ Here, $(S,\mathcal{S})$ is a measurable space, $T : S \rightarrow S$ is an ergodic map for the measure $\mu$, and $f \in L^1$. Example 1 Suppose ...


2

It looks like they are just allocating the check bits between correction and detection. A code with distance $d$ can correct errors up to $\lfloor \frac {d-1}2\rfloor = c$ bits. This agrees with your expression when $d$ is even but is one half greater when $d$ is odd. You can detect $d-1$ bit errors, so they are saying you have $c$ bits for correction and ...


2

You can combine the "conditional chain rule" and the "chain rule" to extend the joint entropy from two to three variables in a variety of ways, as follows:- $$\begin{align}H(X,Y,Z) &= H(X|Y,Z) + \color{blue}{H(Y,Z)}\\&=\color{red}{H(X|Y,Z)} + \color{blue}{H(Y|Z)+H(Z)}\\&=\color{red}{H(X,Y|Z)-H(Y|Z)}+H(Y|Z)+H(Z)\\&=H(X,Y|Z)+H(Z)\end{align}$$


2

Exactly as ther other answer mentions, one can expand (recursively) the joint entropy of $n$ variables to the joint and conditional entropy of $n-1$ variables and so on. Similarly to the way the joint probability of $n$ variables can be reduced to the computation of the joint and conditional probability of $n-1$ variables (by the definition of conditional ...


1

You might want to read Cover & Thomas' Elements of Information Theory 2e first, particularly the channel capacity chapter. Basically, the set of length $n$ sequences which are $\epsilon$-jointly typical are those which have empirical entropies (i.e. $- \frac{\log p(x^n,y^n)}{n}$) are within $\epsilon$ of the true entropy $H(X,Y)$, and $x^n$ is ...


1

Can you prove $$I(U';V'|W) \leq I(U';V')\qquad(1)?$$ If yes, define the distribution $P_{(U'(z),V'(z))}$ as that of $P_{(X,Y|Z=z)},$ and the distribution $P_{(U'(z),V'(z)|W)}$ as that of $P_{(X,Y|Z=z,W)}.$ For each $z$ apply (1) in the form $$I(X;Y|Z=z,W)=I(U'(z);V'(z)|W)\leq I(U'(z);V'(z))=I(X;Y|Z=z). $$ Now take the leftmost term and the rightmost term ...


1

The inequality is wrong; the typical counterxample is $Y=X+Z$ ,where $X$ and $Z$ are independent, taking values $\{0,1\}$ with equal probability and the sum is modulo two (XOR); here $I(X;Y)=0$ and $I(X;Y|Z)=1$. In general, the mutual information between two variables can increase or decrease when conditioning on a third variable. The Venn diagrams applied ...


1

Assuming that the ranking is strict and linear, transmitting it amounts to transmitting a permutation $\sigma$ of $[n]=\{1,2,\ldots,n\}$. For $k,\ell\in[n]$ write $k\prec\ell$ if and only if $k$ precedes $\ell$ in $\sigma$. For each $k\in[n]$ let $$p(k)=|\{\ell\in[n]:\ell<k\text{ and }\ell\prec k\}|\;;$$ $0\le p(k)\le k-1$. The number $p(k)$ specifies ...


1

Now, my intuition was telling me that, because X and Y are roughly the same, then $I(X;Y)=I(Y;X)≈H(X)≈H(Y)$ That's wrong. If $X$ and $Y$ are independent (as it seems here), then $$I(X;Y)=H(X)-H(X|Y) = H(X)-H(X)=0$$ (which is consistent with the intuitive notion of mutual information: if $Y$ is independent from $X$, then $Y$ gives me no information about ...


1

Hint: $\begin{bmatrix} X_i \\ x_j \end{bmatrix} \sim N(\begin{bmatrix} \mu_i \\ \mu_j \end{bmatrix} , \begin{bmatrix} \Sigma_{ii} & \Sigma_{ij} \\ \Sigma_{ji} & \Sigma_{jj} \end{bmatrix})$. You should know how to calculate the distribution of $X_i | X_j$ (this is another Gaussian with a mean and covariance you can calculate. Then, using the entropy ...


1

The representation of joint-conditional entropies of two variables using Venn diagrams is just an illustration that happens to fit the relevant properties... for two variables. Some authors critize and discourage this representation because, though useful as mnemonic, it looks more meaningful than it really is, and it can be misleading in several ways: ...


1

In both of these cases, the data is highly compressible [...]. Is there some definition of entropy that takes this into account? You could be looking for the Kolmogorov Complexity. This is the shortest length to which a string can be compressed. It has connections with entropy.


1

If you want to minimise on $Q$, why don't you simply expand the term in the log and minimize the part that depends on $Q(y)$ with the constraint $\sum Q(y) = 1$. Result should be more convincing that playing with intuitive arguments (which may be true as well as misleading).



Only top voted, non community-wiki answers of a minimum length are eligible