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)

12
votes
0answers
302 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 ...
5
votes
0answers
207 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
51 views

Sum of uniform random variables on simplex

Let $X,X'$ be two independent uniform random variables on $n$-dimensional simplex $\Delta_n= \{(x_1,\ldots,x_n):x_i \geq 0, \sum x_i \leq 1\}$. I am trying to find the probability distribution of ...
5
votes
0answers
67 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
181 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
98 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 ...
4
votes
0answers
122 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
92 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
102 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
194 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
279 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
82 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
412 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
30 views

Asymmetric Multiple Error Correction

In some non-volatile memories, errors are only affect one logic state (just 1->0). Is there a coding technique which could correct k asymmetric errors? I know that the BCH code could correct k random ...
3
votes
0answers
46 views

How much life does it take to stack your deck? (Sorting problem)

There is a card in Magic the Gathering called Lim-Dul's Vault. While it is slightly more complicated than presented, the question I would like to consider is this: Pay 1 life. Look at the top 5 ...
3
votes
0answers
57 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
59 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
83 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
104 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
33 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
91 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
68 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
190 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
75 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
333 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
463 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
26 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 ...
2
votes
0answers
30 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
62 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 $$ ...
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
79 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
12 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
27 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
81 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
40 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
42 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
165 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: TEx->y = H(Xt+τ) - H(Xt) - H(Xt+τ,Yt,Xt) + H(Xt,Yt) In order to produce a shuffling ...
2
votes
0answers
56 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
94 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
71 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
54 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
124 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
61 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
120 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
66 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 ...
2
votes
0answers
36 views

Fastest decaying probabilities with infinite entropy

A well known theorem of analysis is that there is no slowest rate of divergence of a series. "Completely irrelevantly," we know that there exists probabilities (e.g. $\mathtt{Const}/(n\log^2 ...
2
votes
0answers
124 views

Relation between entropy of variable and entropy of conditioned variable

Let $X$ be a discrete random variable, and let $E$ be an event on the same probability space as $X$. Let $X_E$ be $X$ conditioned on the event $E$. Is there a general relationship between the Shannon ...