Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [information-theory]

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.

0
votes
1answer
21 views

The intuition of fair odds (information theory)

I'm reading about gambling in Elements of Information theory. As stated in the book, given that the gambler bets $o_i$-for-$1$ on horse $i$, Fair odds (w.r.t some distribution): the odds is fair if $\...
13
votes
0answers
122 views

The Complexity of “The Baby Shark Song”.

This question is just for fun. I hope it's received in the same goofy spirit in which I wrote it. I just had the pleasure of reading Knuth's "The Complexity of Songs" and I thought it'd be hilarious ...
3
votes
0answers
38 views

Minimum distance required to travel to “see” all points on a hypercube

You begin on a hypercube of dimension N at the origin i.e. $(0,0,0,0,...,0)$ When at the origin you are able to "see" one and only one step away from you. So from the origin you can see vertices $(1,...
0
votes
0answers
26 views

Huffman code - Probability of finding a specific bit in the code

Let $X$ be a random variable in $A = \{1,2,3,4\}$ with pmf $p(1) = \frac{1}{8}$, $p(2) = \frac{1}{8}$, $p(3) = \frac{1}{4}$ and $p(4) = \frac{1}{2}$. Let $c$ be the binary Huffman code $c(1) = 110$, $...
1
vote
2answers
31 views

Generator matrix of the extended hamming code

Given a check matrix $H$ of the $Ham(3,2)$ code, so $$H = \begin{bmatrix} 1&1&1&1&0&0&0\\ 1&1&0&0&1&1&0\\ 1&0&1&0&1&0&1 \end{...
12
votes
1answer
295 views
+50

Can you determine a set of values from a set of distinct sums

Consider an array of positive integers $A$ of length $n$. Now consider the set of sums of all the contiguously indexed subarrays of $A$. For example if $A = (1,3,5,6)$ then the set would be $S_A = \{1,...
0
votes
1answer
30 views

The differential entropy of the sum of independent random variables

Let $X$ be a random variable with density $f$. The differential entropy is defined by $$h(X):=-\int_{\mathbb R^d} f(x)log(f(x))dx.$$ The conditional entropy is defined by replacing the density with ...
1
vote
2answers
44 views

Small o notation PROOF [closed]

It's probably a vey silly question, but I'm confused. I should proof the small o notation with lim but i don´t know how $(\ln n)^a = o(n^b )$ how do i solve this and do i need to proof it for $a<...
0
votes
1answer
28 views

what means the redundacy of a code?

I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $log(6n-3)$ bits. But what does that means? I was ...
0
votes
0answers
68 views

Upper Bound on Mutual Information of a Function of Random Variables

I am struggling to understand the following. Let $X_1$, $W_1$, and $Z_1$ be mutually independent discrete random variables with finite alphabets, $S_1 := X_1 + W_1$, and $f(\cdot)$ be some ...
0
votes
0answers
20 views

Upper Bound on Mutual Information of a Function of Random Variables

I am struggling to understand the following. Let $X_1$, $W_1$, and $Z_1$ be mutually independent discrete random variables with finite alphabets, $S_1 := X_1 + W_1$, and $f(\cdot)$ be some ...
0
votes
1answer
15 views

How to get the P matrices of a linear code?

I have a question attendend to linear codes matrices and the creating of it. The generator matrices is defined as: G=$\array{[I_n | P]}$ and the check matrices is defined as: H=$\array{[-P^T | I_n-...
13
votes
5answers
2k views

Most efficient strategy for guessing outcome of (fair) dice roll?

I'm starting to learn about information theory and I'm a bit stuck on this one. here's what I have so far: 1 possible strategy is to simply ask 'did outcome 1 occur?' if yes then we have our answer, ...
1
vote
1answer
33 views

Chernoff-Hoeffding

I'm looking for a proof for a particular application of Chernoff's inequality in the case of the binomial distribution: https://en.wikipedia.org/wiki/Chernoff_bound#Additive_form_(absolute_error) in ...
0
votes
0answers
14 views

What is the probability mass function of the output of a channel

if a signal, s = +2 Volts, enters a channel which adds noise to the signal from the set {0,-1,-2,-3} with respective probabilities {4/10,3/10,2/10,1/10}, what is the probability mass function of the ...
0
votes
0answers
19 views

Find the probability of r for an additive-noise channel

I know that r = s + n, where s is the signal (input) and n is the noise and r is the output. and: $$ P[S]= \left\{ \begin{array}{cc|c} 0.75,&s=-1\\ 0.25,&s=1\\ 0,&otherwise \end{...
0
votes
2answers
38 views

Understanding Claude Shannon's Formula for Information and Entropy

I'm trying to understand Shannon's formula for information as entropy in some detail. (I'm obviously not a trained mathematician, so please bear with me). Here's what I understand and then following ...
1
vote
1answer
24 views

Finding the coding scheme for an optimum variable length code

Suppose X is an i.i.d. r.v. with an infinite alphabet, X = {1, 2, ...}. I also have P(X = i) = 2^{−i} I want to find the coding scheme for an optimum variable length code however I don't follow the ...
1
vote
1answer
39 views

A bound on $I(X;Y)$ in terms of $I(X;Z)$ for $Y$ and $Z$ that are similar

Let $X,Y,Z$ be three random variables. Assume that $Y$ and $Z$ are binary. $I(A;B)$ is the mutual information between the random variables $A$ and $B$. I'm curious if there is a bound on $I(X;Y)$ in ...
0
votes
1answer
26 views

KL divergence between noisy strings with small hamming distance

Let $x$ and $y$ be strings of length $n$ from a vocabulary of $m$ characters. Suppose that the hamming distance between $x$ and $y$ is $d$, and that $d << n$. Let $X$ and $Y$ be noisy versions ...
0
votes
0answers
14 views

Are there standard notaions for true, reconstructed and modeled information/variables?

I need to write a short note on some information-theory related topics that are relevant to my current work. It would be good to use standard notation, if possible and if it dosn't interfere with ...
2
votes
0answers
43 views

Is the product of uniquely decipherable codes uniquely decipherable?

A code $C$ is prefix-free if no codeword in $C$ is a prefix of another codeword in $C$. For example, $C=\{0,10,110\}$ is prefix-free but $D=\{0,10,100\}$ is not. A code $C$ is uniquely decipherable ...
0
votes
0answers
37 views

Connecting information entropy to the prime number theorem for compression of numbers?

Prime number theorem states how often primes occur (approx. how densely they are distributed). The Shannon theorem of information entropy gives us a lower bound of how much data is at least required ...
1
vote
1answer
38 views

Distributions satisfying expectation condition

Let $q$ be a continuous density on $\mathbb{R}^d$. I am interested in the set $\mathcal{S}$ of continuous distributions $p$ that have the same support as $q$ such that: $E_{X\sim q}[\log p(X)] = E_{X\...
0
votes
1answer
41 views

About the funtions that satisfies $f(ab)\geq b f(a) + a f(b)$

I am doing some research in information theory related to the $f$-divergences and some of their properties. So we have a convex function $f:(0,\infty)\rightarrow \mathbb R$ such that $f(1)=0$, and ...
0
votes
1answer
32 views

Minimal possible entropy of 4 pairwise independent unbiased Bernoulli random variables.

Suppose we have 4 pairwise independent unbiased Bernoulli random variables $X_1, X_2, X_3, X_4$ (i.e., each of them takes two values, each value with probability $1/2$). What is the minimal possible ...
0
votes
0answers
26 views

Data processing inequality for renyi divergence

Anyone know a reference that demonstrates that classical Renyi divergence satisfies a data processing inequality (DPI)? Here by data-processing I mean 'application of an arbitrary bistochastic map on ...
0
votes
0answers
33 views

Entropy maximizing distribution when power constraint exists for one random variable

Suppose I have a random vector $\bar{X}=[X_{1},X_{2}, X_{3}]$. X1,X2 and X3 can take values from the alphabet {0,1,2,3} . (This can be even generalized to a finite set of cardinality N). I don't have ...
0
votes
1answer
42 views

Find probability distribution (joint pdf) that satisfy constraints

Suppose I have a random vector $\bar{X}=[X_{1},X_{2}]$. $X_{1}$ and $X_{2}$ comes from the alphabet {0,1,2}. I don't have any information on the probability distribution of these random variables. In ...
0
votes
0answers
15 views

Channel capacity and rate distortion function

I am learning rate-distortion theory (RTT) and I am confused about its relationship with Shannon's source coding (SSC) and channel coding (SCC) theorems. Here's my understanding. Loosely, SSC states ...
0
votes
1answer
30 views

Corollary to Chernoff's bound: $P(x \geq a+b) \leq e^{-2b^2/n}$

Our information theory textbook says as a easy corollary to Chernoff's bound ($P(x>a+b)\leq e^{-n\mathbb{RE}[p+\frac{b}{n}||p]}$), we have $P(x>a+b)\leq e^{-2b^2/n}$, where $\mathbb{RE}[p+\frac{...
0
votes
3answers
93 views

What is the relationship between information in the sense of Shannon entropy and information for the human brain?

In an informatic theoretic sense, complete randomness maximizes information. For instance, an image of randomly distributed black and white pixels has a very high entropy/information. For a human ...
0
votes
0answers
26 views

detecting the position of an error

I am looking for code that detect an error and it's position (or an aproximation of it), this is more than an error detector code but a little less than a correcting code. Do you know something like ...
0
votes
0answers
43 views

Minimising the Forward KL-divergence via moment matching

The forward KL-divergence is defined as \begin{align}\label{eq:for_KL2} \text{KL}(p(\theta|x)||q(\theta)) & = \int p(\theta|x) \ln \left\{ \frac{p(\theta|x)}{q(\theta)}\right\} dZ\\ & = \...
5
votes
1answer
72 views

How could Bob help Alice

Suppose there’s a sequence $a$ of 0 or 1, that is long enough , eg $length(a)=2^n$, $n$ sufficiently big enough integer. Now Alice is to guess the content of $a$. If Alice knows nothing about $a$, in ...
-1
votes
1answer
21 views

Solution of $D_{KL}(q_\phi(z)||p_\theta(z))$ of Gaussian case

Following is from the original paper of concept of VAE(variational autoencoder) by Kingma,Welling 2014 B. Solution of $D_{KL}(q_\phi(z)||p_\theta(z))$ of Gaussian case The variational lower bound (...
0
votes
0answers
152 views

Problems with martingale lemma in Khinchin's Mathematical Foundations of Information Theory

I'm currently working through Khinchin's "Mathematical Foundations of Information Theory," and while it's been pretty tractable thus far, the section on martingales and Doob's Theorem seems to be ...
1
vote
1answer
27 views

What is the intuitive meaning of the capacity of a timing channel?

I am studying a timing channel. A queue can act as a noise source to such systems as it will disturb the information coded in the incoming time. If the queue has a deterministic service time than we ...
2
votes
2answers
34 views

“triangular” relation conditional entropy

Let $X,Y,Z$ be random variables. Assume we know the conditional entropies $H(Y|X)$ and $H(Z|Y)$ but we want to bound $H(Z|X)$ which is unknown Is there any relation between these 3 quantities, some "...
1
vote
1answer
18 views

Joint Entropy of a sequence of random variables resulting from XORing with a Markov process at stationary distribution

Suppose a sequence of n random variables $X_1 \dots X_n$ is generated from a source where the first random variable $X_1$ is determined by a fair coin flip, and subsequent random variables are the ...
0
votes
1answer
28 views

Does the data processing inequality hold for continuous variables? [closed]

Suppose I have a Markov chain $X \to Y \to Z$ of continuous r.vs. Is it true that: $I(X;Y) \geq I(X;Z)$?
0
votes
0answers
13 views

Bayesian model selection books

I was trying to find some "good" reading books about Bayesian Model selection. So is there any recommendations? To be specific, I was trying to understand the Bayesian Information Criterion (BIC), the ...
0
votes
0answers
42 views

An Event with Unit Density Still Has Zero Information, Despite Not Being an Event That Is Guaranteed to Occur.

My textbook says the following in a section on information theory: The basic intuition behind information theory is that learning that an unlikely event has occurred is more informative than ...
2
votes
2answers
54 views

Compute in practice a channel capacity

I need to compute the capacity of a channel which takes a vector input $X=(x_1,x_2,\ldots,x_n)$ and returns a vector $Y$ which is exactly $X$ but where a random block has been reversed, for example: $...
25
votes
4answers
2k views

Shannon entropy of a fair dice

The formula for Shannon entropy is as follows, $$\text{Entropy}(S) = - \sum_i p_i \log_2 p_i $$ Thus, a fair six sided dice should have the entropy, $$- \sum_{i=1}^6 \dfrac{1}{6} \log_2 \dfrac{1}{6}...
3
votes
1answer
47 views

Variational distance of product of distributions

Let $F(\bar{x})=\prod_{i=1}^{n}f(x_i)$ and $G(\bar{x})=\prod_{i=1}^{n}g(x_i)$, where $f(x)$ and $g(x)$ are probability density functions, and $\bar{x}=(x_1,\ldots,x_n)$. The variational distance ...
0
votes
0answers
36 views

Information Theory

So i'm facing this problem. It sais A Tribe leader has 2 Children. Modern researches came up with 2 conclusions. A) He had 1 Daughter and 1 Son B) He had 1 Daughter and 1 elder Son And the ...
2
votes
2answers
50 views

How to construct an example for the entropy equation: $H(Z)=H(X)+H(Y)$ where $Z=X+Y$ [duplicate]

Given $Z=X+Y$ where X and Y are two random variables, under what conditions does $H(Z)=H(X)+H(Y)$? Notice $Z$ is a function of $(X,Y)$, therefore $H(Z)\leq H(X,Y)$, and $H(X,Y)\leq H(X)+H(Y)-I(X;Y)$. ...
0
votes
0answers
67 views

Is there a formula to best determine what is most likely true?

TL;DR Given some finite set of data where each datapoint is a vote on what the individuals giving the vote think is true, and given that collusion and manipulation is possible is there an optimal ...
1
vote
0answers
19 views

Is there an analogue of Kolmogorov Complexity for Strongly Normalizing Languages?

The definition of Kolmogorov Complexity relies upon the definition of Turing Complete description languages. Famously, Kolmogorov Complexity is uncomputable and akin to the halting problem. I have two ...