The science of compressing and communicating information. It is a branch of applied mathematics and electrical engineering. Though originally the focus was on digital communications and computing, it now finds wide use in biology, physics and other sciences.

learn more… | top users | synonyms (1)

1
vote
0answers
30 views
+50

Quantizer Functions

Let $Y \sim P_Y$ with variance $P^{\alpha_1}$ $P>1$. Assume $n \sim P_n$ with variance $P^{\alpha_2}$ for any $\alpha_2 \le \alpha_1$. Let $\mathcal{Y}$ be the set over which the random variables $...
3
votes
0answers
25 views

Suggestions for Constructing a Random Variables from Correlated Observations

Let $\mathcal{X} \neq \phi $ be a finite set. Let $P_{XY_1Y_2}$ be a fixed joint distribution over $\mathcal{X}\times\mathcal{X}\times\mathcal{X}\ $ and that a random sample $(X,Y_1,Y_2 )$ is drawn ...
2
votes
2answers
27 views

How does changing the log base affect the intepretation of information entropy

Entropy of random variable is defined as: $$H(X)= \sum_{i=1}^n p_i \log_2(p_i)$$ Which as far as I understand can be interpreted as how many yes/no questions one would have to ask on average, to ...
0
votes
0answers
9 views

resource for derivation showing the computing of mutual information for normal random variables

If I have 2 correlated normal random variables, and they are not be jointly normally distributed, is there a closed form answer for their mutual information? I've seen that if two normal random ...
2
votes
2answers
52 views

information measure for matrix that is analogous to rank

Is there a measure for matrix that is analogous to rank of the matrix, but it is continuous on matrix elements? Say, we could say the information in identity matrix $I_n$ is $n$, and when the off-...
0
votes
0answers
5 views

Convex conjugate of average Fisher information measure

What is a possible convex conjugate of the function $\rho \mapsto \int (\nabla \log \rho(x))^2 \rho(x) dx$? (Suppose $\rho$ is a sufficiently integrable probability density function on a $d$-...
1
vote
1answer
27 views

Question about the Shannon Entropy formula

I have a basic question about the Shannon Entropy formula. In fact it's so dumb that I didn't dare ask it in the class because I don't understand the text books. Here's the formula: $$H(X) = -\...
7
votes
2answers
3k views

What is the motivation of the Kullback-Leibler Divergence?

The Kullback-Leibler Divergence is defined as $$K(f:g) = \int \left(\log \frac{f(x)}{g(x)} \right) \ dF(x)$$ It measures the distance between two distributions $f$ and $g$. Why would this be better ...
14
votes
4answers
779 views

Has error correction been “solved”?

I recently came across Dan Piponi's blog post An End to Coding Theory and it left me very confused. The relevant portion is: But in the sixties Robert Gallager looked at generating random sparse ...
0
votes
0answers
19 views

Constraints on Mutual Information Independence Test

Suppose all variables are binary for the sake of simplicity. There is a theorem about mutual information (MI) and a distribution $\chi^2$. Given a data set D with N data points, if the hypothesis ...
0
votes
1answer
20 views

p(a,c) vs p(a∧c)

In this paper: https://www.aclweb.org/anthology/J/J16/J16-2006.pdf, the author breaks the Pointwise Mutual Information of a phrase up into several components: They use the ...
0
votes
0answers
17 views

Decomposition of Shannon conditional mutual information as seen on Wikipedia [Solved]

I am looking for a proof for a formula seen on Wikipedia: \begin{align} I(X;Y|Z) & = H(Z|X) + H(X) + H(Z|Y) + H(Y) - H(Z|X,Y) - H(X,Y) - H(Z) \\ {} & = I(X;Y) + H(Z|X) + H(Z|Y) - H(Z|X,Y) - H(...
2
votes
2answers
93 views

Understanding Conditional Mutual Information

Recently I'm working on conditional mutual information and I'm trying to prove the following property: I(X;Y|Z,W)<=I(X;Y|Z) The property seems obvious to me: ...
1
vote
0answers
62 views

Difference of Entropy of two-dimensional Gaussians

I encountered a putative contradiction. Assume we have two 2-dim. Gaussian variables $z_1 = (x_1, y_1)$ and $z_2 = (x_2, y_2)$ with all components being independent, normal distributed variables: $x_1,...
0
votes
1answer
37 views

Decomposition of Random Variable (Information)?

I am wondering whether the following idea or something similar appears in a field such as statistics or information theory(?). Take a random variable $Y$ which takes value $1$ or $2$ with equal ...
1
vote
3answers
82 views

Representing pairwise-independent but not independent occurrences with venn diagram

For $A,B$ and $ C $ partially pairwise independent occurrences (i.e. $I(A;B)=0$, $I(A;C)=0$ ), it is not true to say that $I(A;B,C)=0$, since $I(A;B,C)=I(A;B)+I(A;B|C)$ [<-this is not correct, see ...
1
vote
1answer
18 views

Proof and physical meaning of $I(X;Y) \leq \min \{ \log| \mathcal X |, \log| \mathcal Y | \}$

The inequality holds, $$I(X;Y) \leq \min \{ \log| \mathcal X |, \log| \mathcal Y | \}$$ where $I(X;Y)$ is the mutual information. I know that $H(X) \leq \log| \mathcal X| $ is an upper bound on ...
0
votes
1answer
21 views

Information Channel Capacity

1) Suppose a Noiseless Binary Channel, who's input is reproduced exactly at the output. Let X be the transmitter and Y the receiver (i.e (X=0----->Y=0 and X=1-----> Y= 1)) I understand intuitively ...
0
votes
0answers
66 views

Help me understand the proof for Shannon's Theorem 4 (regarding number of sequences of various probabilities) in the original paper

I'm reading Shannon's 1948 paper where I encountered Theorem 4: $$ \lim \limits_{N \to \infty} \frac {\log n(q)} N = H $$ In Appendix 3 after proving Theorem 3, Shannon proves Theorem 4 by saying: ...
0
votes
0answers
34 views

mutual information and combinatorics

\begin{align} &\mathrm{H}\left(\frac{1}{2^{k}}\right) \\[3mm]&\ \!\!\!\!\!\!\!\!\!\! - {1 \over 2^{k}}\left\{% {k \choose 0}\mathrm{H}\left(\left[1 - \epsilon\right]^{\,k}\right) + {k \choose ...
2
votes
1answer
552 views

How come that HSL can contain more information than RGB?

I have noticed weird thing when working with HSL - unlike RGB, it has some blind spots where certain value just does not matter. I'm sure we were taught about this when I had Linear algebra lectures ...
2
votes
3answers
79 views

Splitting a file into $m$ pieces of size $1/n$, such that any $n$ pieces allow you to recover the file?

Let's say we have a file (which we could define as a finite sequence of 0's and 1's (or any other two symbols)). For $m > n$, can you create $m$ pieces (which are themselves files), each $\frac 1n$...
1
vote
0answers
38 views

Common Estimates Suggestions

Consider two Markov Chains $X-Y_1-Z_1$ and $X-Y_2-Z_2$ defined on same alphabet space $\mathcal{X}$, such that $Z_1= g_1(Y_1)$ and $Z_2=g_2(Y_2)$ for some functions $g_1,g_2$. Assume further that ...
0
votes
2answers
40 views

Minimum distance for large codes

The minimum distance is easy to compute, and so determine the error correcting/detection capabilities of a code, by enumerating all possible pairs of codewords and computing the hamming distance ...
1
vote
0answers
44 views

KL Divergence between the sums of random variables.

The relative entropy or Kullback–Leibler distance between two probability density functions $g(x)$ and $f(x)$ is defined as $$D(g\|f) = \int_{x} g(x)\log\frac{g(x)}{f(x)} dx .$$ We have two random ...
0
votes
0answers
40 views

Explaining something in Kraft-McMilan inequality proof

I was asked to present the Kraft-McMillan inequality, but I have trouble in understanding why in the following segment of the proof: there is a $$k\ge0 $$such that: $$ a^{-l_1}+a^{-l_2}+.....+(k+1)a^{...
2
votes
2answers
187 views

Formula for proportion of entropy

Let's say we have a probability distribution having 20 distinct outcomes. Then for that distribution the entropy is calculated is $2.5$ while the maximal possible entropy here is then of course $-\ln(\...
0
votes
0answers
29 views

How to use the log-sum inequality to prove convexity of KL-divergence?

I'm trying to read up on information theory, and found the following: http://homes.cs.washington.edu/~anuprao/pubs/CSE533Autumn2010/lecture3.pdf Which states that the convexity of KL-divergence can ...
0
votes
0answers
33 views

Is there a name for the property of a code where symbol “space” is left unused?

For example, say I have the symbols A, B, C and D. If I encode these as A = 1, B = 01, C = 001 and D = 0001 (for a very simple example), I have a very simple prefix code. However, I know straight ...
0
votes
1answer
41 views

Help in proving inequalities in information theory-Kraft-McMillan

I was given a task of proving some inequalities that are related to Kraft-McMillan's inequalities, and i have been scratching my head for quite some time trying to prove it: $$ F(x)= \frac{1}{1-Q(x) }...
1
vote
1answer
21 views

Deriving the Power Spectral Density of a Maximum Entropy Process

In Elements of Information Theory, Chapter 12, Section 6 Burg's Theorem is derived: Presented with the first $p$ values of the autocovariance function $R(k) = E[X_i X_{i+k}]$ a stochastic process ...
1
vote
0answers
17 views

Cumulants of square of Poisson distribution

I'm writing up a derivation of an expression for mutual information between weakly interacting Poisson processes. I'm running into an expression that looks like this: $$\log\mathbb{E}\left[e^{\...
0
votes
0answers
16 views

How can I show that any integrable Passband or Baseband signal is also a finite energy signal?

I have supposed that, as the definition of a baseband/passband signal says, the function x(t) is integrable, continuous and bounded due to the fact that it forms a Fourier Transform pair with x'(f) (...
0
votes
1answer
23 views

MLE in introductory probabilistic information theory

Consider sending a bit that is either $\{0,1\}$ through a noisy symmetric channel, such that for a given input $x$ and a given (potentially noisy) output $y$, $\forall i,j \in \{0,1\}. P(y = i | x = j)...
0
votes
2answers
71 views

Campbell's Source coding

In the usual Shannon's source coding problem one chooses code words that minimize $E[L]:=\sum_i p_il_i$ over all $L=(l_1,l_2, \dots), l_i\ge 0$ such that $\sum_i e^{-l_i}\le 1$ (Kraft inequality), ...
2
votes
1answer
25 views

Significance of Convex Sets for I-Projection

I have been reviewing the literature on information theoretic methods in statistics, and in particular, the method of I-projections. Given a discrete, finite alphabet $\mathcal{X}$, let $\prod$ denote ...
2
votes
1answer
47 views

why can't sort 12 elements in 29 comparisons

The information theoretic lower bound for sorting 12 elements is using 29 comparisons, but actually we can't sort them in less than 30 comparisons. My problem is that why we can't reach the ...
3
votes
2answers
100 views

Is conditional entropy ever taken to be a random variable?

In probability theory, the conditional expectation $E(X|Y)$ and variance $V(X|Y)$ er usually taken to be random variables, st. the value of $E(X|Y)$ depends on what value $Y$ ends up taking. I've ...
4
votes
0answers
126 views

How to keep up when converting between bases?

Here is a schematized binary channel that neatly conveys a decimal number. $ \require{begingroup}\begingroup \def\T {{ \cal T }} \def \Ti {{ \T \raise5mu{ \text- \scriptsize 1 } }} \def\Bx #1{{ ~ ...
2
votes
1answer
82 views

Concavity of Shanon's information

It is known fact for random variables $(X,Y) \sim p(x,y)=p(x)p(y|x)$ the mutual information is concave function of $p(x)$ for fixed $p(y|x)$. I have two confusions in interpreting the above fact: 1) ...
5
votes
3answers
84 views

Greater/lesser search with one false answer allowed

It is well known that you can determine the values of $n\geq 2$ bits using $k$ yes/no questions about the bits (for example, "is $x_1 \oplus x_3 = 1$?), even if one (but not more) of the answers ...
0
votes
1answer
33 views

Does the following function define a distance metric?

For real numeric vectors of length $N$, let $a_n \succ b_n$ be one if true and zero if false. The distance between $A$ and $B$ is $$\sum_1^N a_n \succ b_n$$ Note that this is very similar to the ...
1
vote
2answers
50 views

Proof of Cyclic Redundancy Check validity

I'm looking to understand the use of a Cyclic Redundancy Check, in combination with the mathematics behind it. So far I have 1) For any message $$M(x)\cdot x^n = Q(x)G(x) + R(x)$$ Where $Q(x)$ is ...
8
votes
4answers
116 views

Guess the number despite false answer

This is the Guess-The-Number game with a twist! Variant 1 Take any positive integer $n$. The game-master chooses an $n$-bit integer $x$. The player makes queries one by one, each of the ...
1
vote
1answer
36 views

Conceptual Question : Relationship between entropy and a technique for source coding

I want to encode the messages to a sequence of 1s and 0s (subsequently called "bits"). This is called "source coding". Shannon's source coding theory states that the entropy of a source that emits a ...
0
votes
0answers
14 views

Specific examples of Side Information?

I'm starting to apply information theory to gambling. There is something called Side information (see details in [1]), which I understand is additional information about the outs of the game. It could ...
0
votes
1answer
23 views

Proving some inequalities related to Information Theory

I've been working on some inequalities related to the information theory section of my decision theory course, and I could use some help on some of the derivations for one of the inequalities. As a ...
0
votes
0answers
21 views

Kullback-Leibner divergence true distribution

I have an image with an object which I treat as 2-dimensional Gaussian random vector with mean equal to the center of the object surrounded by, roughly, 3-sigma ellipsoid. On the other hand I feed the ...
3
votes
3answers
418 views

Do Gödel numbers have a practical use?

Is there any example of Gödel numbers being actually used in practice? If so for what purpose?
1
vote
2answers
861 views

what is the mutual information of three variables?

mutual information of tow variables is $\displaystyle\sum\sum p(x,y)\ln\frac{p(x,y)}{p(x)p(y)}$ what is the mutual information of three variables? is it $\displaystyle\sum\sum\sum p(x,y,z)\ln\frac{p(...