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
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
82 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
84 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
107 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
44 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
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
125 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
246 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
106 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 ...
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) ...
0
votes
0answers
25 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
21 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 ...
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: ...
2
votes
1answer
49 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
51 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
96 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
49 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 ...
1
vote
1answer
71 views

Entropy of union of multisets

Assigning a random variable to some multiset: Assume that $S$ is a multiset. We can think of $S$ as independent sampling from some random variable. For instance, $S = \{H, H, T, T, T\}$ can be thought ...
0
votes
1answer
52 views

Relative entropy for joint distribution of length n

In the converse proof in information theory, using Fano's inequality, at the end we would have a term like $I(X^n;Y^n)\leq nI(X;Y)$ I was wondering can we prove something like this for relative ...
0
votes
1answer
63 views

Mutual information between Gaussian source and transmitted output: entropies do not add up

I have a Gaussian source $X \sim N(\mu, \Sigma)$, and under squared error fidelity choice $E[(X-Y)'(X-Y)]$, my optimal output $Y$ differs from $X$ by independent error $Z$, where $Z \sim N(\eta, ...
1
vote
1answer
38 views

Markov processes in paper “Recent Contributions to The Mathematical Theory of Communication”

I was reading the well-known paper by Warren Weaver, "Recent Contributions to The Mathematical Theory of Communication", I stumpled upon the following sentence(p. 5)" A system which produces a ...
0
votes
1answer
45 views

Proof of Jointy Typical Sequences using Chebyshev's Inequality

My lecturer went through the topic of "Jointly Typical Sequences" in my Information Theory course, and one of the properties/lemma was that $P((X^n, Y^n) \in A^{(n)}_e) \to 1$ as $n \to \infty$, where ...
1
vote
1answer
30 views

Prove for entropy of a binomial distribution

I am trying to prove the following identity for a Binomial $(n,p)$ random variable $X$, $$ H(X)= n h_2(p) + \mathbb{E}{n \choose X} $$ I've started with the definition of entropy but I am unable to ...
13
votes
2answers
121 views

can't swing the proof for this inequality

Let $p+p'=1$ and $q+q'=1$. If $\log(p/q)>\log(q'/p')$ then $(p+q)\log(p/q)>(p'+q')\log(q'/p')$. This looks deceptively simple to prove, but it's not. I couldn't crack it using Jensen's ...
6
votes
2answers
116 views

Sum of uniform random variables on simplex

Let $X,X'$ be two independent uniform random variables on $n$-dimensional simplex $\Delta_n= \{(x_1,\ldots,x_n):x_i \geq 0, \sum x_i \leq 1\}$. I am trying to find the probability distribution of ...
4
votes
2answers
80 views

Convert string to another string over a smaller alphabet, and vice versa.

I'm trying to find the most suitable algorithm to convert a string $\alpha$ over the alphabet $\Sigma$ of size $| \Sigma | = n$ to string $\beta$ over the alphabet $\Omega$ of size $| \Omega | = n-1$, ...
0
votes
0answers
23 views

Optimal length close to Entropy plus 1

For a fixed $\epsilon> 0$, one need to find a probability distribution $\bf{p}=(p_1,p_2,\ldots,p_n)$ and an optimal code (prefix-free) for this distribution such that the average length ...
0
votes
1answer
25 views

Log base change problem, Multivariate Gaussian differential entropy proof

I am working through a proof in this document http://ee.tamu.edu/~georghiades/courses/ftp647/Chapter7.pdf for Theorem 3 (The entropy of a multivariate Gaussian distribution): Let X = (X1, X2, · · ...
5
votes
2answers
110 views

An elementary proof for a bound on $x \log x$

During one of our information theory classes, the Professor used the following bound to prove a result. For any $x,y \in (0,1)$, $x \neq y$, show that $$|x \log(x) - y \log(y) | \leq |x-y|\log ...
0
votes
0answers
27 views

Mutual Information in a commuication-chain

Consider three communication-partners $A$,$B$ and $C$ that are commuicating in a chain, like $A\rightarrow B\rightarrow C$. So, $A$ talks to $B$ and $B$ talks to $C$. The channels are noisy. Now, ...
0
votes
1answer
26 views

Mutual information: Indirect

Maybe this is a very trivial question but my own answer to it is rather based on intuition only. Consider two random variables A and B. Their mutual information is I_AB. Now, I want to obtain ...
0
votes
0answers
38 views

a problem involving binary entropy function

let $\alpha<1/2$ such that $2^{H(\alpha)}\le 2^{1-\epsilon}$,when $H$ is binary entropy function. how can i prove that then we have: $2^{n(1-\epsilon)}\ge \sum\limits_{i\le \alpha n } {n \choose ...
0
votes
0answers
41 views

Calculating the Shannon information of drawing equal no. of cards

One card is drawn each from a $k$ deck of 52 cards where $k$ is a multiple of $52$. I need to prove that information of an outcome where each card appears the same number of times tends to ...
4
votes
0answers
96 views

Divergence based robust inference

The term 'divergence' means a function $D$ which takes two probability distributions $g,f$ as input and puts out a non-negative real number $D(g,f)$. I have learnt that the inference based on ...
0
votes
1answer
83 views

Explain Kraft McMillan inequality and how it is applied.

I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me. We would like to encode a sequence of ...
5
votes
0answers
69 views

Solving a Matrix DE involving the KL divergence

If we let $U_\mu$ be a vector field that associates a direction vector $U_\mu(\pi)$ with each $\pi \in $ unit simplex. Each such vector field is associated with a system of ODEs: $$ \pi'(u) = ...
1
vote
2answers
37 views

What's theoretical maximum information compression rate?

Let's say I've got a random bit sequence s and a reversible function f(s), for which the following statement ...
1
vote
1answer
268 views

Calculating Shannon Entropy for DNA sequence?

I'm following the formula on http://www.shannonentropy.netmark.pl/calculate to calculate the Shannon Entropy of a string of nucleotides [nt]. Since their are 4 nt, ...