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)

3
votes
1answer
91 views

How to guess a binary code with feedback

Suppose I want to guess a binary code, where the quality of my guess is provided by an evaluation function. I imagine a safe, where the user enters a binary code by flipping $N$ switches. After ...
1
vote
0answers
205 views

Mutual Information of Correlated Bivariate Uniform Distribution

We have correlated bivariate uniform distribution, where X and Y have a correlation coefficient $\rho$ and they uniformly distributed in the following rectangle. What is the mutual information of $X$ ...
3
votes
1answer
157 views

Intuition about the relation of combinations and entropy

It is not difficult to show that $${n \choose \lambda n} \leq 2^{H(\lambda)n}$$ where $H$ is the binary entropy function: $$H(\alpha) = -\alpha \lg \alpha - (1-\alpha)\lg (1-\alpha)$$ I was ...
11
votes
3answers
510 views

Has error correction been “solved”?

I recently came across Dan Piponi's blog post An End to Coding Theory and it left me very confused. The relevant portion is: But in the sixties Robert Gallager looked at generating random sparse ...
9
votes
2answers
724 views

In what sense is the Jeffreys prior invariant?

I've been trying to understand the motivation for the use of the Jeffreys prior in Bayesian statistics. Most texts I've read online make some comment to the effect that the Jeffreys prior is ...
3
votes
2answers
87 views

Calculate sums of logs in precision

I am encountering a situation where I cannot calculate exact sum of a seris of logorithms in calculating entropy. Suppose we have a series of numbers $p_i$ and we want to calculate $\sum_ilog(p_i)$, ...
2
votes
1answer
94 views

Quantify the gain of information of a new information.

Information theory is not at all my field of expertise, so maybe my question will be a bit naive. As said in title, I would like to quantify the gain of information of a new information. For ...
6
votes
4answers
311 views

Is probability objective?

As we know, probability is a measure of events. However, is it an objectively attribute of events, or just an illusion in ones' mind? For example, suppose that there is an empty black box with an ...
1
vote
1answer
441 views

Variations of the Hamming code.

What types of basic variations of the Hamming code are there and what are their objectives? I was taught the following version: $$ L = n + k $$ $$ n \geq \log_2M $$ $$ k \ge \log_2(n+k+1) $$ where ...
1
vote
1answer
372 views

How do i calculate the probability of erroneous transmission?

In information theory, how do I calculate the probability of an erroneous transmission? Let's take for instance a binary symmetric channel with an error probability $ 1-d=0.25 $ and send codewords of ...
5
votes
3answers
872 views

Inverse of binary entropy function for $0 \le x \le \frac{1}{2}$

I'm trying to find the inverse of $H_2(x) = -x \log_2 x - (1-x) \log_2 (1-x)$[1] subject to $0 \le x \le \frac{1}{2}$. This is for a computation, so an approximation is good enough. My approach was ...
4
votes
0answers
263 views

Universal Correlation measure — ranking correlations

I have time series data of experimental observations for two related processes. I want to measure correlation for use in further analysis. Correlation of the series changes over time and across ...
2
votes
2answers
72 views

Given $\forall x \in \mathbb{R} \: h(p^t(x))=th(p(x))$, how to get $h(p(x)) \propto \ln p(x)$?

The whole question is in the title. $p(x)$ is a probability distribution, and $h$ is continuous and monotonic in $p(x)$. The purpose is to motivate that the "degree of surpise", or the "amount of ...
3
votes
1answer
187 views

Linearity of uncertainty

I've always used Shannon's entropy for measuring uncertainty, but I wonder why to use a logarithmic approach. Why shouldn't uncertainty be linear? For instance, consider the following pairs of ...
1
vote
2answers
71 views

Do equal distance distributions imply equivalence?

Let $A$ and $B$ be two binary $(n,M,d)$ codes. We define $a_i = \#\{(w_1,w_2) \in A^2:\:d(w_1,w_2) = i\}$, and same for $b_i$. If $a_i = b_i$ for all $i$, can one deduct that $A$ and $B$ are ...
1
vote
1answer
184 views

Simple trace distance problem

I am self studying a course on information theory and came with the following question: $A$ and $B$ represent two possibly different probability distributions representing two different independent ...
2
votes
1answer
75 views

How to incrementally reveal information

Please give a protocol to incrementally reveal information. A politician wishes to make a yes/no announcement with out shocking the economy. They set a date 100 days in the future, and every day ...
2
votes
0answers
162 views

rényi entropy as a derivative

Let $x=(x_i)$ be a probability measure on $\{1,\ldots,n\}$. Suppose $1<p<\infty$. The Rényi entropy of $x$ is $$ H^p(x)=\frac{1}{1-p}\log \sum_{i} x_i^p. $$ Does there exist a formula for ...
0
votes
1answer
142 views

How to match a discrete distribution to a continuous distribution in information theoretic sense?

Let $$ S \sim N(\mu, \sigma^2) $$ be a normally distributed random variable with known $\mu$ and $\sigma^2$. Suppose, we observe $$ X = \begin{cases} T & \text{if $S \ge 0$}, \\ -T & ...
0
votes
1answer
137 views

Meaning of the term single letter formula

It is common in information theory to look for single letter formulas or to dismiss a result as suboptimal if no single letter formulas are available. Could someone clarify the meaning of what is a ...
1
vote
2answers
182 views

Entropy expression optimization with Langrange multipliers

I have recently encountered variants of the following expression: \begin{equation} S = H(a,b,c,d)-H(a+b,c+d) \end{equation} where $H$ is the Shannon entropy function, that is $H(X)=\sum_{x\in X}-x\log ...
1
vote
1answer
89 views

Variational distance basic properties

The variational distance between two probability distributions $X$ and $Y$ taking values on the same alphabet $\mathcal A$ is defined as \begin{equation} \delta (X,Y)=1/2\sum_{a\in A} ...
1
vote
1answer
64 views

Types and Typical sequences

Joint types can often be given in terms of the type of x and a stochastic matrix \begin{equation} V:X\rightarrow Y \end{equation}such that $ P_{x,y}(a,b)=P_{x}(a)V(b|a)$ for every $a\in X$ , $b\in Y$. ...
3
votes
2answers
260 views

What is the mutual information $I(X;X)$?

$X$ is a random variable with normal distribution, assume $Y=X$, what is the mutual information $I(X;Y)$? I guess that $h(Y|X)=0$ since when $X$ is known, $Y$ is completely known, so ...
1
vote
1answer
129 views

A Measure for Number of Unique N-Tuples

Suppose I have a multiset of numbers. I'm interested in the number of unique n-tuples that can exist using the numbers from this multiset. Now of course a closed form is of interest here, but what I'm ...
6
votes
2answers
1k views

What is the trellis diagram for a linear block code?

For the convolutional codes there is so-called trellis diagram, for which the definition is rather clear for me, however in mathematical sense is not. I have heard that it can be defined for linear ...
1
vote
1answer
185 views

Maximally entropy preserving irreversible functions. (CS related)

The topic/problem is related to hashing for data structures used in programming, but I seek formal treatment. I hope that by studying the problem I will be enlightened of the fundamental limitations ...
1
vote
1answer
284 views

Explicit examples of smooth entropy computation

Smooth classic entropies generalize the standard notions of entropy. This smoothing stands for a minimization/maximization over all events $\Omega$ such that $p(\Omega)\geq 1-\varepsilon$ for a given ...
4
votes
2answers
196 views

Are there simple examples of capacity-achieving block codes for discrete memoryless channels?

The title pretty much says it all, but I am particularly interested in the case where the number of input and output symbols are equal and the transition matrix defining the DMC is nondegenerate. I am ...
1
vote
1answer
299 views

Conditional entropy of bigrams, trigrams, and their reverses

Conditional entropy can be expressed in terms of entropy as H(Y|X) = H(X,Y) - H(X). Given a sequence $\{x _{1}, x _{2},... x _{n}\}$, the bigrams are $\{(x _{i}, x _{i+1})\}$, and the trigrams are ...
0
votes
3answers
99 views

Capacity of a discrete channel in the telegraphy case

I'm reading Shannon's article A Mathematical Theory of Communication, and I'm stuck at the telegraphy case example, on page 4. Shannon writes a formula involving $N(t)$, the number of sequences of ...
6
votes
2answers
1k views

Proof of Pinsker's inequality.

How to prove the following known (Pinsker's) inequality? For two strictly positive sequences $(p_i)^n_{i=l}$ and $(q_i)^n_{i=l}$ with $\sum_{i=1}^np_i=\sum_{i=1}^nq_i=1$ one has ...
0
votes
2answers
587 views

Units of Shannon's information content

I'm familiar with information and coding theory, and do know that the units of Shannon information content (-log_2(P(A))) are "bits". Where "bit" is a "binary digit", or a "storage device that has two ...
0
votes
1answer
675 views

Information Theory - Shannon's “Self-Information” units

Shannon's "self-information" of the specific outcome "A" is given as: -log(Pr(A)), and the entropy is the expectation of the "self-information" of all the outcomes of the random variable. When the ...
2
votes
0answers
66 views

is there a computationally efficient formula for computing the mutual information between two continuous variables?

I need to compute the mutual information between two continuous variables. Below is an equation shown to compute the mutual information between a variable $X$ and $Y$. $I(X;Y) = \int_Y \int_X ...
2
votes
1answer
148 views

Does this quantity have a name in information theory?

The Kullback-Leibler divergence between two (discrete) probability distributions is defined as $$ D_{KL}(P\|Q) = \sum_i p_i \log \frac{p_i}{q_i}, $$ where $p_i$ is the probability that $P$ assigns ...
2
votes
1answer
242 views

Parameter estimation for a distribution by minimizing its conditional entropy

Let $X$ be a discrete random variable with Laplacian distribution with mean $0$ and scale $\lambda$, as $$ p(X) = \frac{1}{2\lambda} \exp\left(-\frac{|x|}{2\lambda}\right), \\ X \in ...
1
vote
1answer
474 views

Weighing Pool Balls where the number of balls is odd

As many of you might have seen before, here is the description of the classic weighing balls problem: One of twelve pool balls is a bit lighter or heavier (you do not know) than the others. ...
2
votes
2answers
100 views

Numbers which encode other numbers infinite times.

Let $g(x,n)$ be a function which chops off the first n digits of the binary decimal expansion of x. eg $g(0.1010111,2)=0.10111$ Is there a function $f(x)$ from the reals to the reals, such that for ...
4
votes
3answers
164 views

simulating a fair random process with an unfair one.

Let's say I have a stochastic process that outputs $1$ or $0$ with probability $p$ or $1-p$ respectively, $p\neq 1/2$. Let's assume this is a repeatable iid process. So I can generate $X_1,X_2\dots$ ...
0
votes
1answer
92 views

How to compute Shannon information?

Given a string of random symbols with yet a priori unknown distribution, what are the known algorithms to compute its Shannon entropy? $$H = - \sum_i \; p_i \log p_i$$ Is there an algorithm to ...
2
votes
1answer
132 views

Do ordered lists contain more information than unordered lists?

Suppose you have a set of 4 elements {A,B,C,D}, but without specifying their order. Now, if you want to specify which precedes which, that would mean you need to provide more information. But at the ...
4
votes
1answer
211 views

What is the general context for entropy (information theory)?

From Wikipedia: Let $X$ be a random variable with a probability density function $f$ whose support is a set $\mathbb{X}$. The differential entropy $h(f)$ is defined as $$ h(f) = ...
2
votes
2answers
171 views

Proving Asymptotic Equipartition Property for Gaussian r.v.'s using the Chernoff Bound

I just learned about Chernoff Bounds and am wondering if one can prove the Asymptotic Equipartition Property using them instead of the Weak Law of Large Numbers (which is the consequence of the ...
0
votes
2answers
1k views

calculate entropy of joint distribution

beforehand,i want to congrat coming new year guys,wish all you everything best in your life,now i have a little problem and please help me,i know definition of entropy which has a formula ...
6
votes
1answer
243 views

measure of information

We know that $l_i=\log \frac{1}{p_i}$ is the solution to the Shannon's source compression problem: $\arg \min_{\{l_i\}} \sum p_i l_i$ where the minimization is over all possible code length ...
1
vote
1answer
124 views

Find the maximum of this binary entropy look-alike function

Let $b,c \in (0,1)$ be such that $b+c<1.$ Define the following function for $p \in (0,1) :$ $$ I(p;b,c):=(b+c)[p \log\frac{1}{p}+(1-p)\log\frac{1}{1-p}]-cH(p;b,c)-bH(p;c,b)$$ where ...
1
vote
1answer
224 views

Finding channel capacity of a combined channel

Suppose I know the capacity of channel C1 and the capacity of another channel C2. Both are achieved by a uniform distribution. Both have a binary input. Now I have a random variable Z which takes ...
1
vote
2answers
2k views

What is the motivation of the Kullback-Leibler Divergence?

The Kullback-Leibler Divergence is defined as $$K(f:g) = \int \left(\log \frac{f(x)}{g(x)} \right) \ dF(x)$$ It measures the distance between two distributions $f$ and $g$. Why would this be better ...
6
votes
1answer
195 views

Lemma in Petersen's *Ergodic Theory*

I'm trying to understand the proof of Lemma 6.2.1 (p.260-261) in Petersen's Ergodic Theory. Specifically, I don't understand why $B_{n}^{A} \in \mathscr{B}(T^{-1}\alpha \vee \dots \vee T^{-n}\alpha)$ ...