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
1answer
23 views

Compressing bitchains

Let there be a bit-chain consisting of $n$ characters with the following rules: The probabilities of the first character being $0$ and $1$ are $1/2$. From then on the probabilities are $p$ when the ...
0
votes
0answers
22 views

Lower bound on conditional entropy over multiple random variables

I am trying to compute the best subset of features for a given random variable $X_i$ from the set of given $n$ random variables. For that I am using conditional entropy to determine the best subset, ...
1
vote
0answers
23 views

Data processing inequality for four variable markov chain

I came across this result in one of my lectures and I've been trying to prove it: If $U \rightarrow X \rightarrow Y \rightarrow Z$, then $$ I \left( U; Z\right) \leq I \left(X;Y\right). $$ Can ...
0
votes
0answers
41 views

How many samples of a sequence do I need to determine whether there is a pattern?

The question title doesn't make a lot of sense but I'll try to explain. I have a source of random finite integer sequences that I know always satisfies the constraint that each positive integer is ...
1
vote
1answer
32 views

Correcting multivariate distribution by additional info about its marginal

Assume that I have a posterior distribution $p(\theta_1, \theta_2|X)$ and I obtain an additional information in the form of a marginal density $q(\theta_1|Y)$ that is of the same type as $p(\theta_1|X)...
1
vote
2answers
74 views

Channel Capacity 0 or $\infty$

I have stumbled across the following, weird situation: Consider a noiseless channel $Y = X$ where $X$ and $Y$ denote in- and output, respectively. The only restriction placed on $X$ is to be in the ...
2
votes
1answer
55 views

What is the concentration result of the entropy?

Let $X_1, X_2, \ldots, X_n$ be i.i.d. binary variables with $Pr(X_i=1)=p$ and $Pr(X_i=0)=1-p$. The famous result about $p$ is $$Pr\left(\left|\frac{1}{n}\sum_{i=1}^n X_i-p\right|>\epsilon\right)\...
1
vote
1answer
47 views

Encoding the answers to questions somewhere in a binary tree

I have a sequence of binary questions $(U_1,\dots, U_N)$ with some distribution. I know the answer to $n\leq N$ (mod-)adjacent questions, and want to convey this knowledge with as few bits as possible....
2
votes
0answers
76 views

information theory literature beyond Cover and Thomas

Can you recommend me some literature for information theory that goes beyond the book of Cover and Thomas? I know that this is a very broad question and therefore I would be happy about any suggestion ...
0
votes
0answers
18 views

Is it possible to break a system into two BSCs to find the total capacity of a system?

I have been trying to solve this problem in manor of ways but I cannot seem to find a satisfactory solution. I have tried the basic way of calculating capacity through self information but I was ...
0
votes
0answers
49 views

equation behind Variational Inference and Expectation Maximization as a constraint

Preamble: I am reading http://arxiv.org/abs/1312.6114 and realized I do not completely understand the basic equation behind the variational technique. I went to rehash with McKay's and Barber's ...
0
votes
0answers
38 views

Lower Bounding postive fractions-Mutual Information

EDIT: Let $X,Y$ be random variables over some probability space with joint distribution $P$. Then the mutual information between two random variables is defined as $I(X;Y):=\sum\limits_{(x,y)\in\...
2
votes
1answer
117 views

What are differences and relationship between shannon entropy and fisher information?

When I first got into information theory, information was measured or based on shannon entropy or in other words, most books I read before were talked about shannon entropy. Today someone told me ...
4
votes
1answer
114 views

An exercise about superdense coding

My question is second part of exercise 2.70 page 98 of the book Quantum Computation and Quantum Information written by Michael A. Nielsen and Isaac L. Chuang. Assume Bob and Alice share each one ...
3
votes
0answers
74 views

Decomposition of mutual information for conditionally independent variables

I have a question regarding the mutual information of conditionally independent random variables (observations). Given $p(x,y|z) = p(x|z)p(y|z)$ where $z$ corresponds to a latent variable, I was ...
1
vote
1answer
37 views

Specific conditional entropy $H(X|Y=y)$ is not bounded by $H(X)$?

Suppose that $P(Y=y)>0$ so that $$ H(X|Y=y)=-\sum_{x} p(x|y) \log_{2} p(x|y) $$ makes sense. I've assumed for a long time that $H(X|Y=y)\le H(X)$, but then it seems that the wiki article claims ...
1
vote
0answers
79 views

Mutual information of independent fair binary random variables

Let random variables $X,Y$ independent fair random variables that take the values 0 and 1 with equal probability and $Z=X+Y$. So, $I(X;Y)=0$ and I am trying to find their conditional mutual ...
1
vote
0answers
42 views

Numerically robust computation of the mutual information

Given the numerical distributions $p(x,y), p(x|y), p(y|x)$, what is the most numerically robust way of computing $I(X;Y)$? Should one use the formula for $I(X;Y)$ directly? Or should we use either of ...
2
votes
1answer
35 views

In order to be injective over some subset of its domain, must a linear operator have codomain with dimension at least as large as that of that subset?

In structured signal recovery problems, one typically considers a subset $\mathcal{S} \subset \mathcal{U}$ containing elements which are parsimonious, in terms of intrinsic dimensionality, in ...
0
votes
0answers
34 views

How to solve following equation for Gaussian R.V?

Let $y$ is a Gaussian Random variable, how to get the following result? $ln[\frac {P(y_1 ,y_2 |x=1)} {P(y_1 ,y_2 |x=-1)}]$ $= ln[\frac{1+exp(v_1 +v_2)}{exp(v_1)+exp(v_2)}]$ Where $v_i = 2y_i/\sigma^...
1
vote
0answers
17 views

Prove that mutual information between integer and fractional parts goes to zero

For a random variable $X$ with a density function $f(x),$ I want to prove that the following holds: $$ \lim_{n \rightarrow \infty}I(\lfloor nX\rfloor;\{nX\})=0 $$ where $\lfloor x \rfloor, \{x\}$ ...
0
votes
1answer
30 views

Result regarding mutual information of bounded random variable

I have a random variable $X$ which takes values in $[0,1].$ Thus $X$ can be written as $$ X=0.X_1X_2...X_k..... $$ where $(X_1,X_2,...,X_k)$ denotes the random vector corresponding to first $k$-bits ...
0
votes
0answers
25 views

I choose $n$ words from $k$ randoms words from a dictionary with $t$ words. How much entropy is this password?

Let's say I have a dictionary of $t$ words. I randomly select a set of $k<t$ words (no duplicates). Next, I deterministically choose $n<k$ words from those $k$ words (say, pick the first $n$ ...
0
votes
0answers
45 views

Prove that every output has non-zero probability

I am trying to solve the following question from McKay: Prove that no output $y$ is unused by an optimal input distribution that achieves capacity, unless it is unreachable, that is, has $ p(y \mid ...
2
votes
1answer
91 views

Encrypt/Compress a 17 digit number to a smalller 9(or less) digit number.

I have a unsigned long integer(8 bytes) which is guaranteed to be of 17 digits and i want it to store in int(4 bytes) which is of 9 digits at max. Basically i want to encrypt or compress the number so ...
1
vote
3answers
38 views

Prove that $-(p_1+p_2)\log{p_1+p_2} \leq -p_1 \log{p_1} - p_2 \log{p_2}$ provided that $ p_1,p_2 > 0$

WTS: $$-(p_1+p_2)\log{(p_1+p_2)} \leq -p_1 \log{p_1} - p_2 \log{p_2} \> \> \forall \> \> p_1,p_2 > 0$$ Any hints on this? I've tried to set it up as a proof by contradiction, and ...
1
vote
1answer
86 views

Parallel gaussian channel and water-filling

I need help with one of the problems in the Cover and Thomas book "Elements of Information Theory". The question is about two parallel gaussian channels, with input $X_i$, output $Y_i$ and noise $Z_i$...
0
votes
1answer
129 views

Empirical Kullback-Leibler divergence of two time series

I have an two vectors (time series) with the same length (1200 elements) $x$ and $y$. Further both time series are stationary. I don't know the theoretical distribution of $x$ and $y$. I would like to ...
1
vote
0answers
19 views

Number of symbol delay in decoder

There is a coding table like this: 0 for A 01 for B 011 for C 1110 for D. I know this coding is uniquely decodable but not instantaneous since it's not a prefix code. For recognizing ...
0
votes
1answer
45 views

Why is the mutual information nonzero for two independent variables

Suppose we have two independent variables X and Y. Intuitively the mutual information, I(X,Y), between the two should be zero, as knowing one tells us nothing about the other. The math behind this ...
0
votes
1answer
29 views

permutations of binary sequences

What is the proof that there are $2^n$ distinct binary codes of length n I know this progression also applies to the decimal ($10^n$) and hex ($16^n$) systems but how can this be shown?
0
votes
0answers
29 views

partial states or partial probability?

I am trying to figure out an alternative way of representing a state probability space, to make certain ideas clearer (that I don't need to discuss here). Let's say I have a system of two elements, A ...
1
vote
1answer
132 views

Colored Noise Channel Capacity Derivation in Elements of Information Theory (Cover & Thomas)

On page 277 in Elements of Information Theory, Second Edition by Cover & Thomas the derivation of the information capacity of a colored (Gaussian) noise channel is performed. While the math is ...
0
votes
0answers
15 views

How can the maximum complexity of a binary series be proven

In an article in the scientific American (https://www.cs.auckland.ac.nz/~chaitin/sciamer.html), Chaitin mentions a way to determine the maximum complexity of the minimal program of a sequence of ones ...
1
vote
0answers
33 views

Mutual information between 2 sequences of random variables?

How would I go about expanding $I(X_1,...,X_n;Y_1,...,Y_n)$? The chain rule exists for a single case, i.e.: $I(X_1,...,X_n;Y)=\sum^n_{i=1} I(X_i;Y|X_{i-1},...,X_1)$, but I'm having doubts if this can ...
7
votes
0answers
254 views

Relation between Shannon Entropy and Total Variation distance

Let $p_1(\cdot), p_2(\cdot)$ be two discrete distributions on $\mathbb{Z}.$ Total variation distance is defined as $d_{TV}(p_1,p_2)= \frac{1}{2} \displaystyle \sum_{k \in \mathbb{Z}}|p_1(k)-p_2(k)|$ ...
2
votes
1answer
52 views

Proof of Central Limit Theorem via MaxEnt principle

Let $X_i$'s be i.i.d. with mean $0$ and variance $\sigma^2$. After reading Jaynes' book: Probability the Logic of Science, I decided to try out and actually prove CLT via the following steps: a) ...
2
votes
2answers
107 views

Is it possible to code with less bits than calculated by Shannon's source coding theorem?

In information theory, Shannon's source coding theorem establishes the limits to possible data compression, and the operational meaning of the Shannon entropy. Consider that we have data generated by ...
1
vote
0answers
20 views

Algorithm to determine a set of source symbols in Communication System

There are many algorithms (like Huffman, Arithmetic) which exploit the redundancy in the source message stream and compress the source symbols before sending it over (noisy/noiseless) channel to the ...
0
votes
0answers
9 views

To invert a matrix for a specific problem

I am reading the book Computational Statistics, and got a problem from formula (4.43), which is derived from (4.30), (4.41), (4.42) (4.30) is $I_X(\theta)=I_{X,Z}(\theta)-I_{Z\mid X}(\theta)$, where $...
0
votes
1answer
45 views

Conditional joint information of two random variables $X,Y$ given $Z$

For 3 random variables I am trying to prove the following: \begin{eqnarray*} I(X;Y|Z)&\triangleq& H(X|Z)-H(X|Y,Z)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1) \\&=&E_{p(x,y,z)}\bigg[log_2\frac{...
0
votes
0answers
26 views

Binary Symmetric Channel with Feedback

Suppose that feedback is used on a binary symmetric channel with parameter p. Each time a Y is received, it becomes the next transmission. Thus $X_1$ is Bern(1/2), $X_2$ = $Y_1$; $X_3$ = $Y_2$,..., $...
0
votes
0answers
36 views

mutual information entropy problem

In mutual information we have: if $x$ and $y$ are independent then $p(x,y)=p(x)p(y)$ and then $I(X;Y)=0$. Do If $I (X;Y) = 0$ when $x$ and $y$ are not necessarily independent?
0
votes
0answers
22 views

Entropy of Quantized random variables

Let $X,Y$ be two i.i.d real-valued random variables with density function $f_{}(.).$ Let $\langle X\rangle_n, \langle Y \rangle_n$ be quantized versions of $X,Y$ respectively, i.e $\langle X \rangle_n=...
0
votes
0answers
29 views

Interaction information within markov chains

There is a signal $X$ for which we have $2$ noisy observations, $(Y_1,Y_2)$. These observations are individually further degraded into variables $(W_1,W_2),$ giving a Markov structure: $X\...
2
votes
1answer
50 views

Error correction code in $F_8$ correcting $n$ errors

Suppose we're working with $F_8=\{0,1,2,3,4,5,6,7\}$ and each of message has length of $n$. Is it possible to construct an error correction code such that it corrects $n$ errors, and each error is off ...
0
votes
1answer
52 views

Mutual Information

Given $X_1$ and $X_2$ are independent, we have \begin{align} I(X_1,X_2;Y_1,Y_2) & = I(X_1;Y_1,Y_2) + I(X_2;Y_1,Y_2\mid X_1) \\[1ex] & = I(X_1;Y_1) + I(X_1;Y_2\mid Y_1) + I(X_2;Y_2\mid X_1) + ...
0
votes
1answer
97 views

Minimum and Maximum Capacity of a channel

There is this question in the Cover and Thomas book "Elements of Information Theory". Noise alphabets: Consider the channel Y = X + Z where X = {0, 1, 2, 3} and Z is uniformly distributed over ...
0
votes
0answers
50 views

Conditional joint entropy of two random variables

I am trying to prove the formula that gives the joint entropy of the random variables $X$ and $Y$ given $Z$ which is: $$H(X,Y|Z) = H(X|Z) + H(Y|X,Z)$$ based on the definition of conditional entropy ...
1
vote
0answers
65 views

Best way to compress a noisy observation

Say we have a discrete signal $X\in \mathcal{X}$, and a noisy observation $Y\in\mathcal{Y}$. We wish to encode $Y$ into some encoding $U$ with rate $R$. That is, $H(U)=R>0$. And we want $U$ to have ...