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)

14
votes
0answers
342 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
7
votes
0answers
248 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)|$ ...
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) = ...
5
votes
0answers
191 views

Convergence of mutual information

Let $P_n (x,y)$ be a sequence of (cumulative) probability distributions defined on $\mathcal{X}\times \mathcal{Y}$ (of arbitrary cardinality), that weakly converges to $P(x,y)$: $$ P_n (x,y) ...
5
votes
0answers
214 views

Explanation of Radon-Nikodym derivates wrt to probabilities

I am currently working in communications, where a lot of work is done via probability calculations (densities and such). As I am not a mathematician, I do have a quite hard time understanding one ...
4
votes
0answers
135 views

How to prove this inequality (already verified by numerical simulation)?

I have a conjecture which has been verified extensively by simulation. The conjecture is as follows: $\forall t \in [0, 1], \alpha \in [0,1]$, and positive real sequences $\{p\}_{i:1,\dots,n}, $, ...
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 ...
4
votes
0answers
107 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 ...
4
votes
0answers
283 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 ...
4
votes
0answers
83 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 ...
4
votes
0answers
437 views

Inequalities involving the probability density function and variance

I am wondering whether anyone knows of any any inequalities involving the probability density function of an unknown distribution (as opposed to the cumulative distribution function) and its known ...
3
votes
0answers
62 views

Differential entropy of the product of Gaussian random variables

Given two independent Gaussian random variables $X \sim \mathcal{N}(\mu_x,\sigma_x^2)$ and $Y \sim \mathcal{N}(\mu_y,\sigma_y^2)$. We look at the product distribution of these two random variables ...
3
votes
0answers
70 views

Decomposition of mutual information for conditionally independent variables

I have a question regarding the mutual information of conditionally independent random variables (observations). Given $p(x,y|z) = p(x|z)p(y|z)$ where $z$ corresponds to a latent variable, I was ...
3
votes
0answers
85 views

Weak continuity of K-L divergence function

If $P_n$ and $Q_n$ are two pmf's of a discrete set (say $A$) with common support and $P_n \to P$ and $Q_n \to Q$ where the convergence is pointwise here (even weak would be fine here I guess), then $$ ...
3
votes
0answers
83 views

Confidence Interval of Information Entropy?

Information entropy, $IE$, is defined as: $$IE = \sum_{i} p_i log\frac{1}{p_i}$$ Where $p_i$ is the probability of event $i$ (and we are summing over all possible events). Let's say I have data ...
3
votes
0answers
91 views

Proving or disproving concavity of a function

I want to prove that the following function is concave (as a part of another proof). $$f(p) = \max_{\begin{matrix}x,y\\0\le x \le 1\\0\le y \le 1 \\ x * y = p\end{matrix}} \lambda h(x) + ...
3
votes
0answers
122 views

Mutual Information for Gaussian Process (and also Fano's Inequality)

According to this presentation: Bounding Gaussian Process Information Gain we have a closed-form expression for the information gain as follows: $$ I\left(\vec{y} \mid f\right) = \frac{1}{2} \log\det ...
3
votes
0answers
36 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 ...
3
votes
0answers
94 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 ...
3
votes
0answers
70 views

Prove that communication protocol complexity less than $n\epsilon$

Alice and Bob get as an input words $x$ and $y$, which consist of $0$ and $1$. Length of $x$ is $n$ and length of $y$ is $2n$. They want to know if the word $x$ is subword of word $y$. For example, ...
3
votes
0answers
196 views

Joint distribution between a uniform random variable and a function which is “almost” independent from it

Motivation Let $f(\cdot)$ be a (possibly randomized) function, such that for any random variable $X$ (taking values from a finite set $D$), $X$ and $f(X)$ are statistically independent. Let $U, U_1, ...
3
votes
0answers
109 views

Reference for a transformation

Has the (Lebesgue-)ergodic transformation $T: \{0,1\}^{\mathbb{N}} \to \{0,1\}^{\mathbb{N}}$ defined by $T(x(0)x(1)x(2)\cdots) = x(1)x(3)x(5)\cdots$ been well-studied? If so, where? Does it have a ...
3
votes
0answers
78 views

Is there a conditional version of the asymptotic equipartition property?

Let $X_i$ be independent random variables with $\operatorname{Pr}(X_i = x) = p_x$, and let $F_n$ be the empirical frequency distribution of $X_1, \ldots, X_n$: that is, $(F_n)_x$ For any frequency ...
3
votes
0answers
96 views

Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
3
votes
0answers
344 views

Intuition for Fisher information metric

In statistical maniolds $S=\{p_\theta\}$,$\theta=(\theta_1,\dots,\theta_n)$, the Riemaanian metric usually defined is the Fisher information metric $$g_{ij}(\partial_i,\partial_j)=\int \partial_i(\log ...
3
votes
0answers
550 views

Can I map entropy values to a common range so that they are comparable?

I am using the standard Shannon entropy formula for calculating the entropy of a system at different states. The system has a different number of possible outcomes at each state, in other words the ...
2
votes
0answers
21 views

Showing that for a family of subsets of $[n]$ enough elements appear in high frequencies

Let $\mathcal{F} \subseteq 2^{[n]}$ a familiy of subsets. Assume that the following applies: For every $A \subseteq [n]$ , such that $|A|\leq \alpha n$ ($\alpha > 0$ is given), there's a subset ...
2
votes
0answers
15 views

Entanglement breaking channels

I can't get the proof of Theorem 2 of this. So we have a superoperator as $\Phi\in End(H_B)$ defined using a POVM $\{R_i\}_{i=1}^k$ meaning, every $R_i$ is a positive operator and ...
2
votes
0answers
74 views

information theory literature beyond Cover and Thomas

Can you recommend me some literature for information theory that goes beyond the book of Cover and Thomas? I know that this is a very broad question and therefore I would be happy about any suggestion ...
2
votes
0answers
32 views

Departure from uniformity in a continuous (time) distribution

I know how to quantify the departure from uniformity ( or a uniform distribution) for discrete distributions. Assume you have a distribution set of P: ...
2
votes
0answers
52 views

Is Gaussian $(X_1, X_2)$ optimal for $h(a_1X_1+ a_2X_2+Z_1) - \mu \, h( b_1X_1+b_2X_2+ Z_2)$?

Let \begin{align} W &= h(X_1+Z_1) - \mu \, h( X_2+ Z_2) \quad (1) \end{align} where $h(\cdot)$ is the differential entropy function, $\mu\ge 1 $ is a scalar, and $Z_1$ and $Z_2$ are ...
2
votes
0answers
85 views

Quantum Teleportation - how to prove the general case?

I've taken a course of quantum information theory and although I can compute a quantum teleportation in an explicit case where I'm given a quantum entanglement shared by Alice and Bob (normally ...
2
votes
0answers
13 views

Help me construct a bijection $g: \left(1..n\right)^m \to \left(1..n\right)^m$, with influence of each component of $x$ in each component of $g(x)$

Let $x \in \left(0..n-1\right)^m$. I want to construct a bijection $g$ : $\left(0..n-1\right)^m \to \left(0..n-1\right)^m$ such that if we know $m'$ components of $g(x)$ and $m-m'$ components of $x$, ...
2
votes
0answers
29 views

Kolmogorov complexity inequality

Prove, that KP (x) ≤ KS (x) + log KS(x) + 2 log log KS (x) + O(1). Please tell me in which direction to think.
2
votes
0answers
40 views

Fisher Expected Information for a Gaussian Process model

Suppose I have a two dimensional Gaussian process model (GP), defined by a squared exponential correlation function s.t: $$R(x_{i},x_{j}) = \exp\left(-\frac{|x_{i} - x_{j}|^2}{2}\right).$$ I am ...
2
votes
0answers
96 views

What is the variance of self-information (or surprisal)?

The self-information of an outcome $x_i$, or surprisal, is defined as: $$ I(x_i)=-\log P(x_i), $$ where $P$ means probability. This way, the Shannon entropy can be seen as the "average" or "expected" ...
2
votes
0answers
83 views

How to Calculate Values from Incoming Messages? - Evidence Propagation in Bayesian Network

I'm currently trying to wrap my head around evidence propagation in bayesian network (simple tree propagation) but I'm having trouble finding information about the process. As an example, let's take ...
2
votes
0answers
41 views

Doubt in derivation of a proof in Information Theory

In my class we were trying to derive Shanon's Source Theorem, first by proving the equivalent form in a weaker version. The question is -Consider a biased coin with probability of heads $p \geq ...
2
votes
0answers
48 views

Error correcting codes for asymmetric channels

Most work in error correction coding theory (Hamming, Cyclic, BCH, Reed-Solomon, Turbo Codes, LDPC...) deals with linear codes. Now, a linear code binary code is a good fit (only?) for a symmetric ...
2
votes
0answers
197 views

How to deconstruct Shannon Joint Entropy $H(X,Y,Z)$ equation for semi-related variables?

Background The purpose of this is to produce a shuffle correction for Transfer Entropy estimation: $$\operatorname{TE}_{x\to y}=H(X_{t+\tau})-H(X_\tau)-H(X_{t+\tau},Y_t,X_t)+H(X_t,Y_t)$$ In order ...
2
votes
0answers
58 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$, ...
2
votes
0answers
109 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 ...
2
votes
0answers
77 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 ...
2
votes
0answers
56 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
0answers
59 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 ...
2
votes
0answers
33 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 ...
2
votes
0answers
139 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
0answers
64 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 ...
2
votes
0answers
134 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 ...
2
votes
0answers
71 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 ...