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
0answers
25 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
1answer
20 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: $...
22
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
39 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
29 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
66 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
18 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 ...
1
vote
0answers
55 views

How long message can I send?

I know the $n$-bit message ($M$). I have to send it to the receiver bit by bit. For each bit I can also send one bit of comment ($C$). Before receiver gets the bit, he have to guess it($G$). After ...
1
vote
1answer
48 views

What is the meaning of an overline over a finite field?

I'm studying cyclic codes. I read the following theorem : $\mathbb{F}_q$ is a finite field with q elements. Let's consider $X^n - 1 \in \mathbb{F}_q[X]$. If $GCD(q,n) = 1 $, Then $\exists \alpha \...
1
vote
1answer
34 views

Alternative ways of sampling from a distribution

I have recently been working on some numerical algorithm that required me to pick a random element $r_i$ from a finite set $R$ with probability $p_i$. This is a fairly standard procedure and many ...
1
vote
1answer
40 views

Constraint on number of codes of maximum length in a binary Huffman code.

A Random Variable '$X$' take values from a discrete alphabet $K = \{k_1, k_2, k_3,k_4 \}$, with probability mass function {$p(k_i)$} = {$0.6, 0.2, 0.15, 0.05$}. The constructed Binary Huffman codes ...
2
votes
1answer
23 views

Counting free parameters in vector after applying restrictions

I am reading the paper "Detection of Signals by Information Theoretic Criteria" by Wax and Kailath. In this paper, a vector $\Theta$ is defined according to: $\Theta = (\lambda_1, ..., \lambda_k, \...
0
votes
1answer
29 views

reducing fractions with logs in the numerator

I was reading a tutorial introduction to Information Theory and it presented a formula for determining 'average surprise' of 100 coin flips with 50 heads and 50 tails, as follows: $${[50 * log(1/0.5)]...
0
votes
0answers
38 views

What is the simplest way to show that the following inequality is true in information theory?

I have following relation of random variables $$Y_1=aX_1+bX_2+N_1,\\Y_2=X_1+X_2+N_2,$$ where $X_1,X_2$ are discrete random variables which can take a value uniformly from a set and $N_1,N_2$ are ...
8
votes
2answers
139 views

Secret Santa algorithm that does not rely on a trusted 3rd party?

With a trusted 3rd party, running Secret Santa is easy: The 3rd party labels each person $1,\dotsc,n$, and then randomly chooses a derangement from among all possible derangements of $n$ numbers. ...
1
vote
1answer
39 views

How to show the following relation is true in information theory?

Suppose $X_1,X_2$ are two random variables which can take values from the set $\mathcal{X}$ with uniform distribution. Further, $N$ is a Guassian random variable with zero mean and unit variance. In ...
0
votes
1answer
20 views

How to proof the Fano's inequality using the following formulation?

The Fano's inequality for the Markov chain $X\to Y\to \hat{X}$ is given as follows $$H(X|\hat{X})\leq H(E)+P(E)\log_2(|\chi|),$$ where $E$ is error random variable defined such that $E=1$ if $X\neq \...
0
votes
0answers
21 views

Orthogonal basis for binary code in information theory

Agent A has sent to agent B a total of $N$ messages, all of which are bit-strings of length $M$ each. The probability of different bitstrings used by A may be non-uniform, and is not known in advance. ...
1
vote
0answers
42 views

To show the code is not linear

Consider the projective plane of order 2 or the Fano plane and its incidence matrix.https://en.wikipedia.org/wiki/Fano_plane. Any two rows of the incidence matrix thought of as binary words, have ...
-2
votes
1answer
32 views

Understanding the received vector in syndrome decoding

I have an exercise, which I do have solutions to but cannot understand the problem text. As far as I understood, syndromes are computed by checking the received vector against the parity check matrix. ...
0
votes
1answer
28 views

What is the simplified formula to calculate joint conditional entropy of 4 or more variables for instance H(a|b,c,d) or H(a|b,c,d,e)?

I'm a medical science student and I came across a point in my research I've to work with entropy. As entropy involve probability theory which , like many, I'm not good at ;) I can calculate an H(a) ...
3
votes
1answer
68 views

Pattern Recognition and Machine Learning (Bishop) - Exercise 1.28

1.28 In Section 1.6, we introduced the idea of entropy $h(x)$ as the information gained on observing the value of a random variable $x$ having distribution $p(x)$. We saw that, for independent ...
3
votes
1answer
59 views

Proving the information inequality using measure theory

The information inequality is a theorem that shows that the Kullback-Leibler divergence between two probability distributions is always non negative. This can be proved easily using the Jensen's ...
3
votes
2answers
85 views

Differential entropy vs Kolmogorov-Sinai “partition trick”

Shannon entropy is well-defined for probability distributions $p(x)$ on finite (or countable) sets $X$, \begin{equation} H_S=-\sum_{x\in X}p(x)\log p(x)\,. \end{equation} To compute the entropy of a ...
2
votes
1answer
49 views

How do I find the set of functions that would make this non-linear operator diverge?

I have this non linear operator $$H(p) = -\sum_{n=0}^ {\infty} p_n ln(p_n)$$ where $p_n$ are given by a function $p(n)$ when $n$ is a whole number. I want to find what set of $p(n)$ makes $H(p)$ ...
0
votes
0answers
14 views

How to declare a configurable type?

Can a type (alike plain C data struct) we declare an alphabet like $A= [a_1,...a_n]$ and declare that each letter is a vector alike $a_i= \begin{bmatrix} i \\ j \\ ...\\ ...
2
votes
0answers
50 views

Lower bound for quantum relative entropy

In my research this summer, I have become interested in lower bounds on the standard "Umegaki quantum relative entropy". For two non-negative matrices $X$ and $Y$, the Umegaki quantum relative ...
1
vote
1answer
45 views

The Hellman Raviv upper bound?

While reading this paper on page 4 I encounter a upper bound named Hellman Raviv. I know the lower bound in the picture, but could anyone please tell me how I can get the upper bound which is half of ...
1
vote
1answer
30 views

Finding the conditional entropy on the sum of independent random variables

I have two independent random variables $X_1$ and $X_2$. I want to find the differential entropy defined as $$H(X_1+X_2\mid X_1)=\int_{X_1} \int_{X_2} p_{X_1,X_2}(x_1,x_2)\log\left(\frac{1}{p_{X_1+X_2\...
0
votes
1answer
30 views

Comparing Differential Entropy of Normal Distribution to Shannon Entropy

The (differential) entropy of the multivariate normal distribution is given by: $$H(\underline{X}) = \frac12 \ln(|2 \pi e \Sigma|)$$ Does the Shannon entropy: $$ H(\underline{X})=−p(\underline{x}...
0
votes
0answers
30 views

Application of de Finetti's theorem for channels with finite-state memory

I am working with a channel with $d$-state memory which is define as a collection of $d$ channels $W_{C}(Y|X)$ with $C \in \{1,2,...,d\}$ the internal state of the channel, $X$ the input and $Y$ the ...
3
votes
0answers
57 views

Improving on the data processing inequality for Markov chains

Given a Markov chain $X \rightarrow Y \rightarrow Z$, the data processing inequality bounds the mutual information $$I(X;Z) \leq \min \big( I(X;Y),I(Y;Z) \big)$$ However, it seems intuitive that we ...
2
votes
1answer
72 views

optimization loss due to misperceived probability

Suppose $a$ is chosen to maximize the expected value of $u(a,x)$ under a probability measure of $x$. Image the true distribution is $P(x)$, but the optimization may be conducted under a misperceived ...
0
votes
1answer
42 views

Lossless Compression and definition of Entropy

I am taking an intro class to Information Theory and I have a question. Suppose we have three symbols a, b, and c with probabilities of them coming out of a chanell ...
1
vote
1answer
38 views

Proof of $H(Y|X)=H(Y)$ when X and Y are independent

Does anyone know how to prove the $H(Y|X)=H(Y)$ when X and Y are independent? I know the proof of $H(Y|X)=\sum p(x,y)\log_2p(y|x)$,but I found that I can't prove $H(Y|X)=H(Y)$ when $X$ and $Y$ are ...
0
votes
1answer
35 views

How to find the conditional distribution of an estimator given a prior

The problem: Given a known quantity $x$, distributed with known distribution $π(x)$ ~ $N(0,σ^2)$, I'm looking for the distribution of the estimator of $x$, $\hat{x}$ distributed with $p(\hat{x}\mid x)...
10
votes
5answers
235 views

9-Bits Game, a Brain Teaser on Information Theory or Cryptography

This question was asked in a recently interview, I didn't solve it. Suppose there are two very smart people Alice and Bob, there participate in a game, the game is set as followed. Some ...
0
votes
1answer
22 views

Will the mutual information equal to $2$ when H(X) and H(Y)=$0$?

$P(X,Y)=$\begin{bmatrix} P(x_1,y_1) & P(x_1,y_2)\\ P(x_2,y_1) & P(x_2,y_2) \end{bmatrix} = \begin{bmatrix} 0.54 & 0.06\\ 0.06 & 0.34 \end{bmatrix} And i calculate the $H(x)=-1log_21=...
0
votes
1answer
41 views

conditional probability which their condition have $XOR and Z=X+Y$

Let $X$ and $Y$ be two independent binary random variable with the same alphabet {$0,1$},ie,$Pr(0)=Pr(1)=\frac{1}{2}$ Define $I(X;Y|Z)=H(X|Z)-H(X|Y,Z)$ $1.$Let $Z=X+Y$,Find $I(X;Y|Z)$ $2.$Let $Z=X ⊕...
0
votes
0answers
64 views

Deriving Probability Theory from Information Theory

In the paper "A Philosophical Treatise of Universal Induction" section 3 on Probability describes three different interpretations of probability theory: frequentist, objectivist, and subjectivist. I ...
3
votes
0answers
72 views

How to use Kullback-Leibler Divergence if probability distributions have different support?

I have two discrete random variables $X$ and $Y$ and their distributions have different support. Assume $X$ and $Y$ can both take on the same number of values. Lets say $X$ takes values in $\{10,13,15,...
3
votes
0answers
72 views

Expressing conditional entropy as a relative entropy

This question is from Nielsen & Chuang "Quantum Computation & Quantum Information Theory", Chapter 11, Exercise 11.7. Find an expression for the conditional entropy H(Y|X) as a relative ...
0
votes
1answer
96 views

The number of combinations of Fi to F255 that satisfies the following inequality.

Consider the following equation: $H(x) = - \sum_{i=0}^{255} P_{i} \ \log_{2} \ (P_{i}) $ When $ P_{0} = P_{1} = ... =P_{255} = \frac {1}{256}$ $H(x) = - \sum_{i=0}^{255} \frac {1}{256} \ \log_{2} \ ...
1
vote
0answers
25 views

Mutual Information between dataset and output of algorithm

I am trying to understand how the Mutual Information behaves when I have a sequence of iid samples $X^n$, where each $X$ takes values in an alphabet $\mathcal{X}$ and I have an algorithm $\mathcal{A}:\...
0
votes
0answers
39 views

data processing inequality-mutual information

suppose that we have a family of probability mass functions ${f_\theta }\left( x \right)$ indexed by $\theta$, and let $x$ be a sample from this distribution. Then from the information theory, we have ...
0
votes
0answers
34 views

Regularized Least Squares to Solve Entropy Minimization Problems?

I am aware that convex optimization methods can be used with terms related to (information) entropy $$I[{\bf p}] = -{\bf p}^T\log({\bf p})$$ But do there exist any "purely" linear least-squares ...
4
votes
2answers
70 views

Entropy of a Measure Preserving Transformation

$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\lrp}[1]{\left(#1\right)}$ I am reading the concept of entropy from Peter Walters An Introduction to Ergodic Theory and I am having trouble understanding ...
0
votes
0answers
28 views

When finding the upper bound, why is a ceiling evaluated to a +1?

Why does removing the ceiling result in $a + 1$? I'm reading Introduction to Data Compression by Guy E. Blelloch on page $19$ on Information Theory, here he is proving an upper bound. $$ \begin{...
0
votes
3answers
61 views

How can they come up with the definition of entropy in information theory? [duplicate]

I have read some books about information theory but I don't have any ideas how can they find the definition of entropy? We have $$H(X)=-\sum_{x\in X}p(x)\, \text{log}\, p (x)$$ X is a discrete random ...