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)

0
votes
0answers
8 views

Prove the convergence of the Shannon entropies

For any two $[0,1]$-valued independent random variables $X$ and $Y$, I have that: $$ H\left( \lfloor m(X+Y)\rfloor \right) - H\left(\lfloor mX \rfloor + \lfloor mY \rfloor \right) \xrightarrow{m ...
0
votes
1answer
34 views

When can conditional mutual information be decomposed as a sum?

More specifically: What are the necessary conditions to be able to write the following? $$I(X;Y|Z) = \sum_z p(z) \cdot I(X;Y|Z=z)$$ Isn't this always possible, since I can always write $p(x,y,z) = ...
3
votes
2answers
93 views

Origin of the notation for statistical divergence

The unusual notation $D(P||Q)$ seems to be universally used for statistical divergences (e.g. KL divergence). What is the origin of this notation, and do the double bars (pipe symbols) have any ...
0
votes
0answers
15 views

Slepian-Wolf Region for independent binary symmetric sources

How to compute and plot the Slepian-Wolf region for the source $P_{XY}(·)$ where $Y = X · Z$, $P_X$ and $P_Z$ are independent binary symmetric sources, and “·” denotes multiplication modulo-2.
0
votes
0answers
25 views

Rate Distortion function for vector gaussian sources

Let us consider a Gaussian source with output $\bar{X} = [X_1, X_2, ..., X_M]$ where $X_m$ are independent gaussian random variables and $X_m$ has the variance $N_m$. Suppose the per-source-letter ...
1
vote
0answers
33 views

Conditionally independent versions of a random variable

I have been going through some research papers related to information theory. Very often, I have come across this concept of independent versions and conditionally independent versions of a given ...
3
votes
2answers
156 views

Convergence to normal distribution

Consider the probability distribution of the simple symmetric walk. That is the random variable $X_i$ equals $c$ or $-c$ with equal probability and all $X_i$ are independent and $c\geq1$. We are ...
0
votes
0answers
56 views

A weighted measure of international diversity

Suppose that you are a company manager and you are looking for a statistical measure that defines the international reputation of your company. So, you collect data on your clients and the countries ...
1
vote
1answer
55 views

Prove the equivalence between two definitions of graph entropy

I am trying to prove that the following two definitions are equivalent. Let $G=(V,E)$ be a graph. Let $\mathcal{A}$ denote the collection of all maximal independent sets of the graph, and ...
0
votes
0answers
29 views

Approximating the set of 2-typical sequences

I have been trying to find an upper bound for the set of 2-typical sequences; here is how far I got - I would appreciate any further help very much: Let $x^n=x_1,x_2,\ldots, x_n$ be a sequence from a ...
1
vote
0answers
43 views

Entropy and the probability to guess

Let $X$ be a discrete random variable and suppose that we choose a random value $X=x_1$. Let $A$ be an event such that $H[ X \mid A] = k$, where $$H[X \mid A] = - \sum_{x} P[X =x \mid A] \log_2( P[X ...
1
vote
0answers
28 views

limit of a sequence zero?

Let two points $a,b\in\mathbb{S}^{2}$, where $\mathbb{S}^{2}$ is the two-dimensional simplex in $R^{3}$ with $\sum{}x_{i}=1$ for all $x\in\mathbb{S}^{2}$. $x_{1},x_{2},x_{3}$ are the coordinates of ...
1
vote
1answer
37 views

Find the capacity of the channel with uniform noise

A Discrete Memoryless Channel (DMC) has the following relation between input $X$ and the output $Y$: $$ Y=X+Z, $$ where $X$ lies in the interval $\left(-0.5,0.5\right)$ and $Z$ has uniform ...
0
votes
1answer
67 views

Typical sequences and entropy

The book "Probability, Random Processes, and Statistical Analysis" (written by Hisashi Kobayashi and Brian L. Mark and William Turin), talks about the role of entropy in characterising typical ...
0
votes
1answer
48 views

Entropy of a character in a String

Taking into account the Shannon entropy, I was wondering that, if we have a String like $1122344444455$ , is this possible to find out the entropy of digit $4$ in this String? In other words, I would ...
3
votes
1answer
53 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
22 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 < ...
6
votes
1answer
115 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
31 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
58 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
19 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
22 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
73 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
47 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
99 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
109 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
70 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
73 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
39 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
80 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 ...