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
36 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
86 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
676 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
37 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
42 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
59 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
213 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
58 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
58 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
37 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 ...
14
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
56 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
43 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
26 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
43 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
17 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
41 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 ...
4
votes
1answer
88 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
59 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
100 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
38 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
18 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
62 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
64 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
403 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
36 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
293 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
32 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
52 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
1k 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
79 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
45 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
54 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
525 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
68 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 ...
2
votes
1answer
38 views

Is it true that $H(X|Y)=H(Y|X)$?

I have some difficulties with the question whether $H(X|Y)=H(Y|X)$? From my knowledge $I(X;Y)=H(X)-H(X|Y) = H(Y)-H(Y|X)$ so $H(X|Y)=H(Y|X)$ only when $H(X)=H(Y)$ The question is whether it's ...
0
votes
1answer
37 views

Connection between Boltzmann entropy and Kolmogorov entropy

what is the connectivity between Boltzmann's entropy expression and Shannon's entropy expression? mentions a realtionship between Shannon entropy and Bolltzmann entropy. Is there a ...
0
votes
0answers
141 views

Proof of Mrs. Gerber's Lemma Using Convexity and Jensen's Inequality

Can anyone give a proof of the Mrs. Gerber’s Lemma for the scalar case: $$ \ H^{-1}(H(Y|U)) \ge H^{-1}(H(X|U))*p $$ where $$ \ a*b = a(1-b) + b(1-a) $$ $$ \ X\ ,\ Y $$ are binary random ...
2
votes
0answers
39 views

Kullback–Leibler divergence with elements that are $0$

I have a problem that I need to calculate Kullback–Leibler divergence, but the problem is that I have some elements that are $0$. Is there a way that I'm able to deal with situations like that? I know ...
0
votes
3answers
113 views

Calculating probability in a Markov Chain

Suppose I have this Markov chain: And suppose that: $P_{AA} = 0.70$ $P_{AB} = 0.30$ $P_{BA} = 0.50$ $P_{BB} = 0.50$ I realize that $P_{AA} + P_{AB} = P_{BA} + P_{BB}$ but when I simulate I'm ...
4
votes
0answers
84 views

Dividing a deck of cards using only imagination

The idea came up from a discussion I had with my friends. Suppose we want to play a game using a deck of cards, and we can't use any physical materials. If we are intelligent enough, we can remember ...
1
vote
0answers
105 views

Continous wavelet transform and shannon Entropy.

Note: I have asked the same question on signal processing forum,but didn't get any answer. so it might be more like a math or physics question. Hope you don't consider it as cross-post. I am trying to ...
2
votes
0answers
53 views

Information Entropy Applied to Complexity Theory

I was just wondering whether or not information entropy has significant applications to complexity theory. I ask because of a simple example I thought of. It comes from a riddle. Suppose you had 8 ...
1
vote
1answer
50 views

locally linearize a CDF

I have a sequence of discrete CDF's that converge to continuous CDF. Assume we call it $F_n(x)$. If say at some point, say $R$, $F_n$ is differentiable, then we can write $F_n(R+\xi) \approx ...
0
votes
1answer
29 views

KL-divergence with zero probability?

Suppose $P(X=1)=P(X=2)=1/2$ and $P(Y=1)=1$. Then $$D(Y||X)=\log\left(\frac{1}{1/2}\right)+0\cdot\log\left(\frac{0}{1/2}\right).$$ If we consider ...
0
votes
1answer
37 views

information content of a quadratic surd

how much information is required to construct the equation: $$ X^2 - 2=0 \; ? $$ suppose, in a spirit of seasonal festivity, we squander a few further bits, and pamper ourselves with the additional ...
3
votes
3answers
159 views

Estimating the entropy

Given a discrete random variable $X$, I would like to estimate the entropy of $Y=f(X)$ by sampling. I can sample uniformly from $X$. The samples are just random vectors of length $n$ where the entries ...
2
votes
0answers
41 views

Upper bound of mutual information in a Markov chain

Consider binary random variables $X$ and $V$ with marginal distributions $p$ and $\pi$ respectively and also the conditional distribution $p(X=x\mid V=v)=q(x\mid v)$, where $x\in\{-b,b\}$ and ...
1
vote
0answers
93 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...