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)

3
votes
1answer
48 views

Kullback-Leibler divergence and mixture distributions

Let's say I have three probability densities, $h, g$, and $f$, where f is a weighted mixture of h and g, i.e., $$ f(x) = w\,h(x) + (1-w)\,g(x) $$ For simplicity, let's assume all densities share the ...
-1
votes
1answer
21 views

Kullback leiber Divergence Proof

Let us consider the distributions $P_1$, $P_2$, $Q_1$ and $Q_2$, then prove verify the following: $D(P_1 P_2 || Q_1 Q_2) = D(P_1 || Q_1) + D(P_2 || Q_2)$ where $D(P_i||Q_i)$ is the divergence of ...
1
vote
0answers
28 views

Solomon Golomb's infinite tree

Let us construct a tree G(M). It's constructed in the following manner: The left line maps into A(M), the right line get's us to spot k1. The left line from k1 maps to A(M), the right line to k2. ...
0
votes
1answer
90 views

Is it obvious that this integral converges given the following assumptions?

The integral is $\int\limits_{p(x) > 0}p^{-\lambda + 1}(x) \, \left| \ln p(x) \right|^k \, dx$. Assumptions: $\lambda > 0, k > 0$ $\int\limits_{p(x) > 0}p^{-\lambda + 1}(x) \, dx < ...
3
votes
0answers
49 views

How much life does it take to stack your deck? (Sorting problem)

There is a card in Magic the Gathering called Lim-Dul's Vault. While it is slightly more complicated than presented, the question I would like to consider is this: Pay 1 life. Look at the top 5 ...
0
votes
1answer
34 views

Chromatic number of a graph on a binary alphabet

given the graph defined in this post: A binary sequence graph i.e., Define a graph $H(n,2)$ as follows. Each vertex corresponds to a length nn binary sequence and two vertices are adjacent if and ...
0
votes
0answers
15 views

Equivocation Key as a monotone decreasing function of N

Can you help me with this question? "Prove that $H(K│CN)$, where $CN$ denotes a ciphertext of length $N$, is a monotone decreasing function of $N$." I tried solving the problem with typical sets but ...
0
votes
1answer
30 views

Reduction in uncertainty

" I(X;Y|Z) is interpreted as `` the reduction in uncertainty of X due to the knowledge of Y when Z is given." Would it make sense when talking in a geographical sense to say : When information flow ...
2
votes
1answer
49 views

why are these entropy inequalities similar

I have two inequalities for the Shannon entropy $H(y)=-\sum{}y_{i}\log{}y_{i}$, where the $y_{i}$ are the $n$ coordinates of a point in an $n-1$-dimensional simplex with $\sum{}y_{i}=1$ (think of $y$ ...
1
vote
1answer
57 views

Mutual information for a continuous uniform distribution

I'm trying to compute using matlab the mutual information for an $ \infty $-PAM input (the limit of a very dense PAM constellation) for a range of snr and I got stuck. I'm working with a real-valued ...
0
votes
1answer
22 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
17 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
20 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
40 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 ...
1
vote
2answers
72 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 ...
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 ...
2
votes
0answers
72 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
17 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
44 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 ...
2
votes
1answer
88 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
104 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
65 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
35 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
70 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
38 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
33 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 = ...
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
44 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
75 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
79 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 ...
0
votes
1answer
92 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
18 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
41 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
28 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
28 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
68 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
32 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
235 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
51 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
105 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 ...
0
votes
0answers
16 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 ...