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
11 views

Entropy of sum of uniform random variables on a simplex

For two i.i.d random variables $X$ and $Y$, which are uniformly distributed on the $n$-dimensional simplex $\Delta_n= \left\{(x_1,\ldots,x_n): x_i \geq 0, \sum_i x_i \leq 1 \right\}$, I want to find ...
0
votes
1answer
40 views

Conditional entropy and independent conditioning variables

Let $X,Y,Z,Y',Z'$ be random variables where $Y\sim Y', Z\sim Z'$, $Y$ and $Z$ are independent, while $Y'$ and $Z'$ are, in the sense that we have $p(X,Y,Z)=p(X|Y,Z)p(Y)p(Z)$ ...
0
votes
0answers
29 views

mutual information and data processing inequality for $X\to Y\to Z$ where $Y=f(X)$

Let $X\to Y\to Z$ be three random variables. The data processing inequality states $I(X;Y)\geq I(X;Z)$. Further assume $Y=f(X)$ where $f:\mathcal{X}\to\mathcal{Y}$ is an arbitrary function. What ...
0
votes
1answer
15 views

Bits/second Versus Bits/symbol

Can someone reconcile between the channel capacity in bits/symbol and in bits/second? Are they related to the definition of channel capacity in terms of mutual information and the other in terms of ...
4
votes
1answer
48 views

References for information theoretic statistical tools

Strange statistical concepts like spaces of probability distributions, "metrics" like Fisher information or relative entropy, and convergence with respect to these quantities are necessitated in my ...
0
votes
0answers
37 views

Mutual information $I((X,Y,Z);A)$ larger for small pairwise mutual informations $I(X;Y), I(X;Z), I(Y;Z)$?

Is the mutual information $I((X,Y,Z);A)$ larger for small pairwise mutual informations $I(X;Y), I(X;Z), I(Y;Z)$? In particular, in the extreme case that the pairwise mutual informations are ...
0
votes
0answers
41 views

how to mathematically represent a matrix of vectors?

My problem is the following: I have a dataset in particular have $4$ dimensions, for didactic reasons I need to represent this dataset as a $m\times n$ matrix array such that the ($i$-th, $j$-th) ...
0
votes
1answer
33 views

Sets defined by probabilities

I am doing the following problem from Cover and Thomas, Elements of Information Theory, for self-study: Let $X_1,\dots, X_n$ be an i.i.d. sequence of discrete random variables with entropy $H(X)$. ...
2
votes
0answers
28 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 ...
1
vote
2answers
40 views

Geometric distribution achieves maximum entropy for given mean

Let $X$ be a random variable with geometric distribution, ie $P(X=k)=p(1-p)^k$. If I calculated it correctly, $X$ has mean $E(X)=\frac{1-p}p$ and entropy $H(X)=-\log p - \frac{1-p}p\log{(1-p)}$ ...
1
vote
1answer
39 views

Word lengths of optimal binary code

Given an optimal binary code (ie the expected word length if as small as possible while the code is still decipherable) with word lengths $s_1, \ldots,s_m$, I'd like to show the following ...
0
votes
0answers
14 views

Lower bound of KL-divergence between unknown and known distribution

Suppose I have two multivariate continuous random variables $X$ and $\hat{X}$ with underlying probability distributions $P_{X}$ and $P_{\hat{X}}$, where $P_{\hat{X}}$ is a Gaussian approximation of ...
2
votes
2answers
45 views

trouble understanding calculation of signal-to-noise for ldpc codes

My apologies if the answer to this question is too easy. I am a mathematics student and the subject of low density parity check codes is new to me. In many papers on LDPC codes, there are plots ...
0
votes
1answer
28 views

Capacity of AWGN channel with infinite bandwidth

I am supposed to find the capacity of an AWGN communication channel with infinite bandwidth $B$, signal power $S$ and spectral density of noise $n/2$. Now, I know that the formula for calculating ...
0
votes
1answer
31 views

Proving if a permutation cipher is perfectly secret?

From what I've read, perfect secrecy in its most basic form, that the encrypted text reveals no information about the plaintext, be it structure or content. A permutation cipher is easy for me to ...
0
votes
1answer
31 views

generalised log sum inequality

The log sum inequality states that $ \sum_i a_i\ln\frac{a_i}{b_i}\geq a\ln{\frac{a}{b}}$ where $a=\sum_i a_i$ and $b=\sum_i b$. Is there a generalisation (with whatever conditions) that extends it ...
1
vote
1answer
19 views

calculus of variations or optimize over function form

I have a question about optimizing the following quantity over function form . Given unknown function $f(\theta)$ such that $f(\theta)\geqslant 0$ and $\int f(\theta)d\theta\leq \infty$. And ...
1
vote
0answers
50 views

Prove that this series converges (originally from information theory)

Suppose the positive sequence $p_1,p_2,p_3,\ldots$ satisfies $\displaystyle\sum\limits_{i=1}^\infty p_i=1$. Prove that if $\displaystyle\sum\limits_{i=1}^\infty p_i \log i$ converges, then so does ...
1
vote
0answers
11 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
1answer
35 views

higher moments of entropy… does the variance of $log x$ have any operational meaning?

The Shannon entropy is the average of the negative log of a list of probabilities $\{ x_1 , \dots , x_d\}$, i.e. $$H(x)= -\sum\limits_{i=1}^d x_i \log x_i$$ there are of course lots of nice ...
0
votes
0answers
23 views

Is there any definition of entropy of a stochastic process?

Entropy of finite random variables is defined in Wiki https://en.wikipedia.org/wiki/Entropy_(information_theory) Entropy rate of a stochastic process is defined in Wiki ...
0
votes
1answer
37 views

Information of an event

We know that a basketball player is moving from Europe to USA. He can go to one of the teams $A,B,C,D,E$ with probabilities: $P(A) = \frac{1}{2}$, $P(B) = \frac{1}{4}$, $P(C) = \frac{1}{8}$, $P(D) = ...
1
vote
0answers
18 views

Minimizing mutual information using Lagrange multipliers

Im trying to follow a minimization of mutual information using Lagrange multipliers in a highly cited paper called The Information Bottleneck Method (1999), page 4: $$R(D) = \min_{p(\tilde{x}|x): ...
0
votes
1answer
24 views

Calculate capacity of given channel

I have the following communication channel represented with its transitional matrix: and I'm supposed to calculate its capacity. I'm thinking it's probably quite simple, but nothing comes to mind ...
0
votes
1answer
50 views

What does $\operatorname{bb}()$ mean in information theory?

I'm coming across a lot of formulas in the textbook that use "bb()" however, I don't know what bb is, it isn't mentioned anywhere. For example max entropy in a binary source: $$\mathbb{H}_{max} = ...
4
votes
0answers
123 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}, $, ...
0
votes
0answers
19 views

Comparison between Shannon's and Blackwell's measure of informativeness

I want to compare the concept of ``precision of information'' between signals $x \in X$ and states $\omega \in \Omega$ defined by Blackwell and Shannon. Denote the conditional probability ...
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 ...
0
votes
0answers
7 views

Prove the convergence of the Shannon entropies

For any two $[0,1]$-valued independent random variables $X$ and $Y$, I have that: $$ H\left( \lfloor m(X+Y)\rfloor \right) - H\left(\lfloor mX \rfloor + \lfloor mY \rfloor \right) \xrightarrow{m ...
-1
votes
0answers
32 views

Information Bottleneck toy example

I am currently trying to learn the Information Bottleneck method by calculating a simple toy example through the iterative algorithm as described here: ...
0
votes
1answer
33 views

When can conditional mutual information be decomposed as a sum?

More specifically: What are the necessary conditions to be able to write the following? $$I(X;Y|Z) = \sum_z p(z) \cdot I(X;Y|Z=z)$$ Isn't this always possible, since I can always write $p(x,y,z) = ...
0
votes
0answers
13 views

Slepian-Wolf Region for independent binary symmetric sources

How to compute and plot the Slepian-Wolf region for the source $P_{XY}(·)$ where $Y = X · Z$, $P_X$ and $P_Z$ are independent binary symmetric sources, and “·” denotes multiplication modulo-2.
0
votes
0answers
21 views

Rate Distortion function for vector gaussian sources

Let us consider a Gaussian source with output $\bar{X} = [X_1, X_2, ..., X_M]$ where $X_m$ are independent gaussian random variables and $X_m$ has the variance $N_m$. Suppose the per-source-letter ...
0
votes
0answers
17 views

Finding entropy of two sets of elements H(X), H(Y) if we have conditional probability p(Y/X).

How to find entropy of two sets H(X) and H(Y) if we are given conditional probability P(Y/X) for every part of these sets? Elements of X and Y are related.
1
vote
0answers
33 views

Conditionally independent versions of a random variable

I have been going through some research papers related to information theory. Very often, I have come across this concept of independent versions and conditionally independent versions of a given ...
3
votes
2answers
144 views

Convergence to normal distribution

Consider the probability distribution of the simple symmetric walk. That is the random variable $X_i$ equals $c$ or $-c$ with equal probability and all $X_i$ are independent and $c\geq1$. We are ...
0
votes
0answers
56 views

A weighted measure of international diversity

Suppose that you are a company manager and you are looking for a statistical measure that defines the international reputation of your company. So, you collect data on your clients and the countries ...
1
vote
1answer
50 views

Prove the equivalence between two definitions of graph entropy

I am trying to prove that the following two definitions are equivalent. Let $G=(V,E)$ be a graph. Let $\mathcal{A}$ denote the collection of all maximal independent sets of the graph, and ...
0
votes
0answers
26 views

Approximating the set of 2-typical sequences

I have been trying to find an upper bound for the set of 2-typical sequences; here is how far I got - I would appreciate any further help very much: Let $x^n=x_1,x_2,\ldots, x_n$ be a sequence from a ...
1
vote
0answers
39 views

Entropy and the probability to guess

Let $X$ be a discrete random variable and suppose that we choose a random value $X=x_1$. Let $A$ be an event such that $H[ X \mid A] = k$, where $$H[X \mid A] = - \sum_{x} P[X =x \mid A] \log_2( P[X ...
1
vote
0answers
28 views

limit of a sequence zero?

Let two points $a,b\in\mathbb{S}^{2}$, where $\mathbb{S}^{2}$ is the two-dimensional simplex in $R^{3}$ with $\sum{}x_{i}=1$ for all $x\in\mathbb{S}^{2}$. $x_{1},x_{2},x_{3}$ are the coordinates of ...
1
vote
1answer
31 views

Find the capacity of the channel with uniform noise

A Discrete Memoryless Channel (DMC) has the following relation between input $X$ and the output $Y$: $$ Y=X+Z, $$ where $X$ lies in the interval $\left(-0.5,0.5\right)$ and $Z$ has uniform ...
0
votes
1answer
51 views

Typical sequences and entropy

The book "Probability, Random Processes, and Statistical Analysis" (written by Hisashi Kobayashi and Brian L. Mark and William Turin), talks about the role of entropy in characterising typical ...
0
votes
1answer
43 views

Entropy of a character in a String

Taking into account the Shannon entropy, I was wondering that, if we have a String like $1122344444455$ , is this possible to find out the entropy of digit $4$ in this String? In other words, I would ...
3
votes
1answer
38 views

Kullback-Leibler divergence and mixture distributions

Let's say I have three probability densities, $h, g$, and $f$, where f is a weighted mixture of h and g, i.e., $$ f(x) = w\,h(x) + (1-w)\,g(x) $$ For simplicity, let's assume all densities share the ...
-1
votes
1answer
20 views

Kullback leiber Divergence Proof

Let us consider the distributions $P_1$, $P_2$, $Q_1$ and $Q_2$, then prove verify the following: $D(P_1 P_2 || Q_1 Q_2) = D(P_1 || Q_1) + D(P_2 || Q_2)$ where $D(P_i||Q_i)$ is the divergence of ...
1
vote
0answers
27 views

Solomon Golomb's infinite tree

Let us construct a tree G(M). It's constructed in the following manner: The left line maps into A(M), the right line get's us to spot k1. The left line from k1 maps to A(M), the right line to k2. ...
0
votes
1answer
89 views

Is it obvious that this integral converges given the following assumptions?

The integral is $\int\limits_{p(x) > 0}p^{-\lambda + 1}(x) \, \left| \ln p(x) \right|^k \, dx$. Assumptions: $\lambda > 0, k > 0$ $\int\limits_{p(x) > 0}p^{-\lambda + 1}(x) \, dx < ...
3
votes
0answers
47 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 ...
0
votes
1answer
30 views

Chromatic number of a graph on a binary alphabet

given the graph defined in this post: A binary sequence graph i.e., Define a graph $H(n,2)$ as follows. Each vertex corresponds to a length nn binary sequence and two vertices are adjacent if and ...