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)

2
votes
0answers
52 views

Shannon-Fano analysis, Binary-search-like

Prove that the codewords of the Shannon-Fano code satisfy $l_i \leq \left \lceil \log _2 \frac1{p_i}\right \rceil$. Elementary wording: given positive numbers in descending order $p_1,...,p_n$, ...
0
votes
0answers
16 views

Few questions regarding applications of conditional entopy

I have the idea of entropy and conditional probability etc and having few conditional entropy related questions: 1. What does actually conditional entropy $H(Y|X)$ mean? How can we explain this term ...
0
votes
1answer
33 views

Mutual information decrease with coarse-graining

Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$. Is it true that: If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus ...
5
votes
1answer
61 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
5
votes
1answer
172 views

Entropy of the induced transformation

I need help with this problem: Let $(X,\mathcal{B},\mu,T)$ be a ergodic dynamical system in the probability space $(X,\mathcal{B},\mu)$. Let $A \in \mathcal{B}$ with $\mu(A)>0$. We define the ...
2
votes
1answer
77 views

Is there a combinatorial explanation for this identity related to Kraft's inequality?

Kraft's inequality involves the quantity: $$\sum_{x \in X} \frac 1 {b^{\ell(x)}} \tag 1$$ Where we are considering a code mapping symbols in the alphabet $X$ to strings in an alphabet of $b$ ...
0
votes
3answers
977 views

Similarity between two probability distribution

I am not sure how to put the question. I am not even sure if this question makes sense at all. I know that the similarity of two discrete (or continuous) distributions can be quantified by ...
0
votes
1answer
49 views

A question on Markov chain

Suppose for two random variables $X$ and $Y$ we have $X\perp\!\!\!\perp Y$ and also assume that three random variables $X$, $Y$ and $Z$ form the following Markov chain: $X\to Z\to Y$. Do these two ...
0
votes
1answer
78 views

Entropy of sum is sum of entropies

Having $X$ and $Y$ discrete random variables above finite set. Z is defined as $Z=X+Y$ when does the following happen: $$H(Z)=H(X)+H(Y)$$
2
votes
0answers
62 views

Good low-rate, short-length block codes

I am highly unsure whether this question is appropriate for this site (as it is at no point a math problem), yet searching in the stackexchange universe for similar topics showed the most hits on ...
1
vote
0answers
48 views

What is the “true” entropy of a binary string?

Consider an infinite binary string $\sigma$ and define its entropy $$H_1 = -(p_0 \log_2 p_0 + p_1 \log_2 p_1)$$ with $p_i = \lim_{N\rightarrow \infty} N(i)/N$, $N(i)$ the number of $i$'s among the ...
3
votes
0answers
26 views

Entropy of Group Action by Knowing Finiteness of Unidimensional Subaction

I've been trying to solve the following problem " Considering a measurable dinamical system $(X, \mathcal{B}, \mu, \mathcal{T})$ where $\mathcal{T}$ is an action of a semigroup $G = N^d$ on $X$ for ...
0
votes
0answers
50 views

Problem with calculating probability of symbols

I've a $100 \times 100$ binary matrix it`s constructed with this probability table : i want to apply extended Huffman on this matrix my idea is to compress each column individually . - so starting ...
2
votes
0answers
46 views

Is there an information theory for continuous time signals?

Information theory books talk about entropy and mutual information of discrete time processes, such as a sequence of symbols sent with a symbol period $T_s$ and there received sequence. Can we talk ...
-6
votes
2answers
119 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory [closed]

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
3
votes
0answers
70 views

Doubts in Bayes' Theorem

I meet one problem on the probability and statistic theory. "Assume given the probability spaces $(X,S,\mu_i)$, $i=1,2$, and the probability space $(X,S,\lambda)$. And there exsit functions ...
1
vote
1answer
121 views

Mutual Information in an Binary Erasure Channel

Imagine a Binary Erasure Channel as depicted on Wikipedia. One equation describing the mutual information is following: $$\begin{array}{rcl} I(x;y) &=& H(x) - H(x|y) \\ &=& ...
0
votes
1answer
46 views

Calculating Entropy of Dependent Random Variables

So basically I'm trying to answer the following exam problem: I'm half struggling on H(Z | X) and H(X | Z) and mainly just need confirmation. I know that H(Z | X) = -SUM P(Z|X)P(X)logP(Z|X) ...
0
votes
1answer
51 views

Subadditivity of Entropy

We define $H(X) = -\sum_{x}p_{x}\log p_{x}$ and relative entropy as $H(p(x)||q(x)) = \sum_{x}p(x)\log \frac{p(x)}{q(x)} = -H(X)-\sum_{x}p(x)\log q(x).$ Now we have to prove that $H(X,Y,X) + H(Y) \leq ...
2
votes
2answers
46 views

Does X|Y = X formally, in the sense of RVs?

In Cover and Thomas' "Elements of Information Theory", the joint entropy $H(X,Y)$ is defined, but they state that this definition is nothing new if we consider that it is the entropy of a single ...
1
vote
0answers
38 views

Help understanding KL-Divergence

I will be doing a course in Information Theory soon and to get some early learning in I have been attempting a question with a joint probability mass function represented by the following table: In ...
2
votes
1answer
32 views

Are measures of information model specific?

Does an information measure for a signal do a better job if it assumes some things about the signal? For example: I have a digital stream of data, 0s and 1s coming at a clock rate $r$. What is the ...
0
votes
0answers
91 views

Maximizing variance of Hamming distance of a system

I have a system as shown below, where 4 registers have 8 bit input A,B,C,...
3
votes
2answers
101 views

Bounding second moment of entropy

Entropy is defined as $E(-\log(P(x))$. We know it is bounded by $\log(r)$ when $r$ is the size of alphabet. Defining the second moment as $E(\log^2(P(x))$, how to show it is bounded?
0
votes
1answer
57 views

How does the presenter in this video derive this formula?

I am watching this coursera video on entropy (in the information theory sense of the word). Right around the two minute mark the presenter shows two forms for H(p). The first (after the equals sign) ...
1
vote
2answers
141 views

Fano's inequality and error rate

The Wire-tap channel II (http://link.springer.com/chapter/10.1007%2F3-540-39757-4_5) article in proof of Theorem 1 uses Fano's inequality to estimate the entropy $H(S|\hat{S}) \leq K \cdot h(P_e)$ ...
0
votes
1answer
52 views

Conditional mutual information and Markov chain.

If we have the Markov chain $X \to Y \to Z$, or equivalently $$I(X;Z| Y)=0, \tag{1}$$ where $I(\cdot)$ denotes the mutual information. Does the Markov chain $X \to (Y,W) \to Z$ also hold? Or ...
0
votes
1answer
22 views

Loss of information while projecting multidimensional data

I'm interested in the evaluation of the loss of information after projecting multidimensional data. Since the dimensional reduction is a common tool to analyse data,a question about the loss of ...
2
votes
3answers
64 views

What's the name of the quantity $\mathbb{P}(A\cap B)/(\mathbb{P}(A)\mathbb{P}(B))\;$?

In a physics book, I've come across the quantity $$ \frac{\def\P{\mathbb{P}}\P(A\cap B)}{\P(A)\P(B)}\,, $$ where $A$ and $B$ are events. The author calls this quantity the correlation of $A$ and ...
5
votes
0answers
74 views

Looking for a a measure-theoretic treatment of “differential entropy”

If $X$ is a discrete random variable, its entropy $H(X)$ is usually defined as something along the lines of $-\sum \def\P{\mathbb{P}}\P(x) \log_2( \P(x))$, where the sum ranges over all the possible ...
3
votes
1answer
55 views

How much information is in the question “How much information is in this question?”?

I'm actually not sure where to pose this question, but we do have an Information Theory tag so this must be the place. The "simple" question is in the title: how do I know how many bits of information ...
2
votes
3answers
61 views

Why can we use entropy to measure the quality of a language model?

I am reading the < Foundations of Statistical Natural Language Processing >. It has the following statement about the relationship between information entropy and language model: ...The ...
1
vote
1answer
207 views

The golden ratio in statistics of literature

Let a book, for example, or a poem... It consists in words and letters and symbols like : ;,!... Let $W_b$=the number of words of the book. Let $L_b$=the number of letters of the book. The number ...
1
vote
1answer
32 views

information and coding theory weakly independent problem

$X$ is weakly independent of $Y$ if the rows of the transition matrix $\begin{bmatrix}p(x|y)\end{bmatrix}$ are linearly dependent. Show that if $X$ and $Y$ are independent, then $X$ is weakly ...
1
vote
2answers
77 views

Shannon Entropy Minimization

The Shannon Entropy for an observation is given by $ -x \log_2(x)$. Why is the maximum entropy achieved at $x = \frac{1}{e}$, and not at $x = 0$? Could someone provide a logical explanation that ...
1
vote
0answers
111 views

In the Stinespring dilation theorem, what is the minimum dimension for which a dilation Hilbert space of this form is guaranteed to exist?

This may look like a problem that could easily be looked up, but it's not quite as easy as it first appears, hence my asking. I'm going to phrase my question in terms of the "Schroedinger picture" ...
0
votes
1answer
91 views

An inequality about entropy

Suppose we have random variable $X=\{x_1,\cdots,x_n\}$ with probability mass function $p$. The entropy is defined by $$H(X)=\sum_{i=1}^np(x_i)\log_b(p(x_i)^{-1})$$ where $b$ is any integer $\geq ...
8
votes
2answers
700 views

How to make the encoding of symbols needs only 1.58496 bits/symbol as carried out in theory?

I'm reading the tutorial of Information Gain, and I see the following page: I know in the example above, I can encode this way: A 0 B 10 C 11 and then this ...
0
votes
1answer
43 views

Mutual information and Independence [closed]

Let X, Y, Z be 3 random variables such that X and Z are independent. then can I say that I(X;Y|Z) = I(X;Y). and why?
0
votes
1answer
45 views

For P0 close to P1 the relative entropy can be approximated by its series expansion,Why?

I am reading a article (An overview of distinguishing attacks on stream ciphers, Martin Hell · Thomas Johansson · Lennart Brynielsson) about Distinguishe Attacks. There is a approximate equation ...
1
vote
3answers
66 views

Does entropy $H(y)$ decrease as $H(x,y)$ decreases when $H(x)$ is fixed?

Can't find any proof in Shannon's 1948 paper. Can you provide one or disproof? Thank you. P.S. $H(x)$(or $H(y)$) is the entropy of messages produced by the discrete source $x$(or $y$). $H(x,y)$ is ...
1
vote
0answers
285 views

What do two number on top of each other in square brackets mean?

Im currently going through "Universal Portfolios with Side Information" by Cover and Ordentlich [96]. Near the end of the paper, they provide a formula for calculating weights of a Universal Portfolio ...
1
vote
1answer
84 views

When is a minimum distance decoder also a maximum likelihood decoder?

It is well known that if we have a binary symmetric channel with crossover probability $\epsilon<0.5$ and we send a word $x$ through it, the most likely word is the one with minimum hamming ...
1
vote
1answer
67 views

Parallel translation via $e$-connection

This question is concerned with Section 2.5. of Amari and Nagaoka's Information geometry book. Let me give some background first. Let $\mathcal{P}$ be the $n$-dimensional manifold of all (strictly ...
2
votes
1answer
46 views

Two Huffman trees for one corpus. How is it possible?

Consider this (simple) corpus: "abcdd". I understand how to build the right tree from this corpus, though I don't see how to get the left one. Moreover, isn't there a unique solution (tree) for ...
15
votes
3answers
1k views

How to tell if a code is lossless

Consider the following code mapping: $$a \mapsto 010, \quad b\mapsto 001, \quad c\mapsto 01$$ It's easy to see that the code isn't lossless by observing the code $01001$, which can be translated to ...
0
votes
2answers
105 views

Good examples of when conditioning decreases/increases mutual information

I'm looking for two intuitive examples of random variables X, Y and Z. One where $ I(X;Y|Z) > I(X;Y) $ and another set of X,Y and Z where $ I(X;Y|Z) < I(X;Y)$ According to wikipedia ...
0
votes
1answer
25 views

Show that the following holds;

Let $h(p) = -p \log p-(1-p)\log (1-p)$ denote the binary entropy of a Bernoulli distribution when the probability of observing a zero is $p$, where $\log$ denotes the logarithm to base 2. Show, using ...
0
votes
0answers
54 views

Show using Stirling's approx. that $\log\binom{n}{\gamma n} = nh(\gamma) -\frac{1}{2} \log n + O(1).$

Let $h(p) = -p \log p-(1-p)\log (1-p)$ denote the binary entropy of a Bernoulli distribution when the probability of observing a zero is $p$, where $\log$ denotes the logarithm to base 2. Show, using ...
1
vote
1answer
28 views

Information content of an unlabelled matrix

I'm trying to get an idea of the amount of information that is "stored" in an "unlabelled" matrix. I assume that the vector $(x,y,z)$ contains more information than the set $\{x,y,z\}$. But purposely ...