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
0answers
6 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,...
1
vote
1answer
33 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
0answers
14 views

Are there different types of Shannon's entropy? [on hold]

The physical entropy (Boltzmann's) is excluded from this question. I ask this question in the purpose of getting more familiar with the concept of informational entropy. To me, it is more of a ...
0
votes
1answer
41 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
1answer
56 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
32 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
17 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
53 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 ...
4
votes
0answers
29 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
49 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
50 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
84 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
27 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
1answer
33 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 ...
0
votes
0answers
15 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
81 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
641 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
22 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
34 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
49 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
68 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
42 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
52 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
31 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 ...
13
votes
3answers
995 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
21 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
23 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
32 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
22 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 ...
0
votes
0answers
31 views

Graph theory: Adjacency reducing mapping

In $G(V,E)$, an adjacency-reducing mapping is a mapping from $V$ to $V$ such that if $u,v\in V$ not adjacency in $G$, then $p(v),p(u)$ not adjacent, where $p(\cdot)$ is the mapping. Assume $V'$ is ...
1
vote
0answers
14 views

Encoder based on large similar data

Let us say you (Alice) and another agent (Bob) share a large piece of data (say, the Gutenberg project collection of books, or the Linux kernel. You want to send a smaller but still large piece of ...
0
votes
1answer
24 views

How to calculate the probabilty of symbol in huffman code?

I have a question that I tried to solve but I always get stuck.. The following Huffman code for an alphabet consisting of five symbols A to E ...
3
votes
1answer
56 views

Shannon's MTC as 'information theory'

I'm a little confused as to whether or not this question belongs here or on http://cstheory.stackexchange.com/, so please, bear with me. I've been reading a few books on the concept of information, ...
1
vote
1answer
45 views

Jensen's inequality for countable probability space

One form of Jensen's inequality for the finite case, tells us that $$ \sum_{x \in X} p(x) \log q(x) \leq \log\sum_{x \in X} p(x) \cdot q(x) $$ For positive p(x), and $\sum_{x \in X} p(x) = 1$, ...
0
votes
2answers
70 views

Are marginal densities always greater than the corresponding joint density?

I.e. if $\mathbb P\left(x,y\right)$ is a joint density function, and $\mathbb P\left(y\right)$ is a marginal distribution is it always true that: $\mathbb P\left(x,y\right)\leq \mathbb ...
0
votes
1answer
27 views

Mutual information of discrete and continous stochastic variable

As part of a homework, I have a "quantizer" consisting of variables $X_{1}$ and $X_{2}$ which have the following joint distribution. $X_2$ is discrete and I can assume that all probabilities are ...
0
votes
0answers
13 views

Can small subsets of a large set be lossily compressed with one-sided error?

Because I'm allowing error, my question is not a duplicate of Compressing a short list of very large numbers?, although they are very similar. For large finite sets $U$ and non-negative integers $n$ ...
4
votes
1answer
47 views

Joint Probability from Marginal Probabilities

$X, Y_1, Y_2$ are random variables with (possibly) different finite alphabets. For given conditional probability mass functions $\mathbb{P}(Y_1|X)$ and $\mathbb{P}(Y_2|X)$, is it always possible to ...
0
votes
1answer
22 views

Normalized Mutual Information results in log(0) with non-overlapping clusters - how to deal with that?

I want to evaluate how well my flat soft clustering method works, compared to a gold standard. After some research I found that Normalized Mutual Information would most likely be a good measure, for ...
0
votes
1answer
52 views

Is there any software package to calculate the entropy, information content, mutual information, etc?

Provided a p.f. of a discrete random variable, or a joint p.f. for several random variable, is there any software package to calculate the entropy, joint entropy, information content, mutual ...
2
votes
0answers
28 views

Joint entropy maximization with a constraint

So I have 2 random variables X and Y, where X can take on values {0,1,2,3} and Y can take on values {0,1,2,3,4}. I need to maximize H(X,Y) subject to the constraint that P(X≠Y)=0.5. This also gives ...
5
votes
3answers
125 views

What does the -log[P(X)] mean in the calculation of entropy?

The entropy (self information) of a discrete random variable X is calculated as: $$ H(x)=E(-log[P(X)]) $$ What does the -log[P(X)] mean? It seems to be something like ""the self information of each ...
2
votes
0answers
31 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
0
votes
0answers
34 views

Hamming code with an additional parity bit

Suppose we use Hamming Code with additional parity bit (Aka Hamming code [8,4]). I was asked to complete the following: Given a codeword: Number of 1's is even, and there's (at least) an error ...
1
vote
0answers
299 views

Calculating minimum hamming distance of a code

We use hamming code of (7,4,3); Given 4 bits of information, we'll add 3 bits of parity, and one more parity bit for the 7-bits code. Given $x_3,x_5,x_6,x_7$ $x_1 = (x_3+x_5+x_7) \mod 2$ $x_2 = ...
1
vote
0answers
43 views

Using mutual information to estimate correlation between a continuous variable and a categorical variable

As for the title, the idea is to use mutual information, here and after MI, to estimate "correlation" (defined as "how much I know about A when I know B") between a continuous variable and a ...
2
votes
1answer
36 views

symmetry of additive channel's mutual information

Suppose we have an additive noise channel: $Y = X + Z$, where $Z$ is noise, independent of $X$. So we can write the mutual information as: $I(X;Y) = h(Y) - h(Y|X) = h(Y) - h(Z)$. We can also write ...
0
votes
1answer
36 views

Encoding a channel with Huffman Code

I have a random source which is with no memory and have this alphabet (A,B,C). Each symbol in the alphabet has a probability ( A = 0.5, B= 0.25, C = 0.25) It's given that each message including ...
2
votes
3answers
125 views

Is Standard Deviation the same as Entropy?

We know that standard deviation (SD) represents the level of dispersion of a distribution. Thus a distribution with only one value (e.g., 1,1,1,1) has SD equals to zero. Similarly, such a distribution ...
2
votes
0answers
38 views

Finding the mean and the variance of a martingale using concentration inequalities

I am trying to find the mean and the variance of a martingale defined as the maximized likelihood ratios over some finite parameter space. The way I want to do this is through Azuma's inequality (or ...