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.

Filter by
Sorted by
Tagged with
0
votes
1answer
14 views

How do we show $Z=g(Y) \implies X \Rightarrow Y \Rightarrow Z$ i.e. $X,Y,Z$ form a Markov chain?

I am reading Elements of Information Theory by Cover and Thomas, and I have come across the above corollary to Markov chains. In their notation, this would amount to showing that $Z=g(Y) \implies p(x,...
0
votes
0answers
19 views

Relationship Between Entropy of a Measure and Hausdorff Dimension of Its Support

In this paper by Chhabra and Jensen, the authors make the claim (based on a theorem by Eggleston which is proven in this paper) that "for a special class of measures $\mu$ that arise from ...
0
votes
1answer
38 views

How to compute the transition matrix of this channel?

I am working on the following exercise: Let $X, Z$ be independent RVs with values in $\mathcal{X} = \{0, 1, \ldots , n − 1\}$ and with probability distributions $p_X$ and $p_Z$ respectively. Let $...
0
votes
0answers
23 views

Transition matrix for noisy symmetric channel

I'm working on the following exercise: Let $X, Z$ be independent RVs with values in $\mathcal{X} = \{0,1,...,n-1\}$ and with probability distributions $p_x$ and $p_z$ respectively. Let $Y$ be the ...
0
votes
1answer
29 views

Minimal mutual information for the Binary Symmetric Channel

I am working on the following exercise: Let $X, Y$ be RVs with values in $\mathcal{X} = \mathcal{Y} = \{0, 1\}$ and let $p_X(0) = p$ and $p_X(1) = 1−p$. Let $\mathcal{C} = (X , P, Y)$ be the ...
0
votes
1answer
22 views

How to compute the transition matrix of a channel composed of two channels?

I have a quick question on the following exercise: Let $C = (X , P, Y)$ be a binary channel which is composed of two binary channels in sequence, such that the output of the first channel $C1 = (...
0
votes
0answers
29 views

How can relative entropy be a measure of how well a candidate model approximates the unknown true data generating model if the true model is unknown?

I have a decent understanding of most of the general idea of relative entropy(Kullback-Liebler Divergence). However I would like help clarifying the following from a set of notes: " Relative entropy ...
0
votes
0answers
23 views

Channel capacity larger than one in noisy channel coding theorem

The Noisy channel coding theorem stated that: For every discrete memoryless channel, the channel capacity $C=\sup\{{I(X,Y)}\}$ has the following property: For any $\epsilon>0$ and $R<C$, for ...
1
vote
0answers
34 views

Information theory reference: comparison between Mackay to Thomas and Cover

I'm a computational neuroscience student with a background in mathematics. I want to learn information theory over the summer. I am interested in its applications to neuroscience, machine learning, ...
0
votes
0answers
18 views

Relationship Between Covering Numbers of Different Diameters

If I denote the covering number of a set $A$ via $\epsilon$-balls with respect to a norm $||\cdot||$ as: $N(\epsilon, A, ||\cdot||)$, I'm wondering if there's anything I can say about the relationship ...
0
votes
0answers
7 views

Could it possible to construct a Turbo Product Codes with component codes RS code and BCH Code?

guys,I'm wondering if it possible to construct a Turbo Product Codes with component codes RS code and BCH code? Could somebody prove this? Many thanks!
0
votes
1answer
27 views

Conditional entropy upper bound between two discrete random variables.

Let's suppose X and Y two discrete random variables that can assume the number of states $k_x$ and $k_y$ respectively. Is possible to determine the maximum conditional entropy achievable $H_{max}[Y \...
4
votes
1answer
36 views

Failure of Maximum Information Content Strategy for Puzzle Solving

In the book (available online for free) "Information Theory, Inference, and Learning Algorithms" by David J.C. MacKay, on pages 68f, and in this recorded lecture of his (Youtube), the "Weighing ...
2
votes
1answer
50 views

Information content of two bits

Let $X \in\{0,1\}$ and $Y \in\{0,1\} $ be two uniformly distributed bits. Let $B$ be an arbitrary random variable such that $I(X:B)=0$, $I(Y:B)=0$, and $I(X \oplus Y:B)=0$, then is it true that $I(X,Y:...
1
vote
1answer
61 views

How to compute channel capacity?

I am working on the following exercise: Let $\mathcal{C} = (\mathcal{X}, P, \mathcal{Y})$ be the following channel: $$\mathcal{X} = \{0,1,2,3\}$$ $$\mathcal{Y} = \{0,1,2,3,4,5,6,7\}$$ $$P =...
1
vote
1answer
46 views

how to find the probability density function that maximizes the entropy under the constraint $E(X)=\sum_{n=0}^{\infty}{n\cdot p(n)}=A$?

I'm approaching this with Lagrange multipliers, I have defined $$L(p(0),...,p(n),\lambda)=H(X)-\lambda\cdot(E(X)-A)=-\sum_{n=0}^\infty{p(n)\cdot{log(p(n))}}-\lambda(\sum_{n=0}^{\infty}{n\cdot p(n)}-...
0
votes
0answers
49 views

A Strong Chernoff Bound

In this paper by Winter et al, it is stated that the following 'Chernoff bound' holds for $i.i.d.$ random variables $X_k$ such that $0 \leq X_k \leq 1$ and $E(X_k) = p$ for all $k$, $$\Pr \left[ \...
1
vote
1answer
43 views

Convex hull of the set of distributions with constant entropy

Let $H(p):=-\sum_{i=1}^n p_i \log p_i$ be the Shannon entropy defined on the set of probability distributions on $\{1,2,...,n\}$. Let $h$ be a constant such that $0\leq h \leq \log n$. The question is:...
0
votes
1answer
39 views

Entropy of the Uniform Mixture of Discrete Probability Distribtuions

Consider the following inequality: \begin{equation} H\left(\frac{1}{3}p_{1} + \frac{1}{3}p_{2} + \frac{1}{3}p_{3}\right) \geq H(0.5p_{1} + 0.5p_{2}) \end{equation} where H(.) denotes the Shannon ...
1
vote
0answers
16 views

How to show that $P_{ML}$ is equal to the reversed I-projection of any element $P$ of a linear family

Let $\mathcal{E}$ be an exponential family of distributions $P_{\theta}$, $\theta = (\theta_1, \dots, \theta_k) \in \mathcal{H}$ on an arbitrary measurable space $(\mathcal{X}, \mathcal{F})$ defined ...
0
votes
0answers
26 views

Information loss function for numerical approximations

The other day I was reading about some aspects in information including Shannon's source coding theorem and other interesting ideas. Coming from a computational/numerical mathematics background I was ...
1
vote
0answers
16 views

Proving that if $\mathcal{L} \cap \mathcal{E} \neq \emptyset$, then $P_{ML}$ equals the single element of $\mathcal{L} \cap \mathcal{E}$.

Let $\mathcal{E}$ be an exponential family of distributions $P_{\theta}$, $\theta = (\theta_1, \dots, \theta_k) \in \mathcal{H}$ on an arbitrary measurable space $(\mathcal{X}, \mathcal{F})$ defined ...
1
vote
1answer
40 views

KL Divergence of (y|z) in terms of KL Divergence of (x|y) and (x|z)

Consider there are three distributions $X$, $Y$ and $Z$ and all three have same support. Then is there some relationship of the following form which holds? \begin{align} D_{KL}(Y||Z) \stackrel{?}{=} f(...
0
votes
0answers
14 views

Measure of spread or amout of information in a standardized distribution (how to calculate entropy?)

Suppose I have a distribution of scores {-1, 0, 1} and another distribution of scores {-0.70711, 0.70711}. These two distributions have the same mean, 0, and almost the same standard deviation, ...
1
vote
0answers
15 views

How to prove that $\liminf_{n \to \infty}\frac{1}{n} \log Q^n(\tilde A_n^c) \geq -\min_{P:H(P)\geq R}D(P||Q)$?

Let $A_n \subset \mathcal{X}^n$ be the union of all type classes $T_P^n$ with $H(P) \leq R$. I aim to prove that if an arbitrary $\tilde A_n$ satisfies $$\frac{1}{n} \log |\tilde A_n|$$ then $$\...
1
vote
1answer
56 views

Standard deviation of length of compressed file with arithmetic coding

I am working through the exercises in David Mackay's book "Information theory, inference and learning algorithms" (https://www.inference.org.uk/itprnn/book.pdf) and I am stuck with problem 6.9. In ...
1
vote
0answers
15 views

Universal source coding with fixed length codes of rate R

Let $A_n \subset \mathcal{X}^n$ be the union of all type classes $T_P^n$ with $H(P) \leq R$. I would like to show that for every distribution $Q$ on $\mathcal{X}$ with $H(Q) < R$ $$Q^n(A_n^c)=2^{-n\...
0
votes
0answers
18 views

what are the codewords for random variable $X$ having the probability $P(X=2^n)=\frac{1}{2^n}$?

I have looked it up and understood that this is called a dyadic distribution , and I'm trying to understand how the coding will be for this random variable. What i know is based on a theorem from ...
0
votes
0answers
28 views

A generalized entropy measure

In (Frank 2009), it is shown that several probability distributions, such as Uniform and Gaussian, are maximum-entropy distributions. When discussing the Binomial distribution, Frank notes, ‘we must ...
1
vote
0answers
25 views

How many points on a sphere whose distance is greater than $\epsilon$

I have a "simple" question, but my first researches are not very successful. Given a dimension $d$ and a distance $\epsilon$, is there a standard lower bound on the number of points $N(d,\epsilon)$ ...
0
votes
0answers
27 views

The smallest number to represent a set of numbers

I would like an "algorithm" to find the smallest number that can represent a list of numbers exactly, order included. As an example, if a list is [2 3 4 6 9], I would like an algorithm to yield a ...
3
votes
1answer
92 views

Entropy of partitioning for set of all $\binom{n}{k}$ combinations

Let $\binom{[n]}{k}$ represent the set of all $k$-combinations of the set $[n]=\{1,\dotsc,n\}$. We will use the notation: $$\{x_1, \dotsc, x_k\} \in \binom{[n]}{k},$$ where $x_1 < x_2, < \dotsc ...
0
votes
0answers
27 views

Can Kullback-Leibler distance comply triangle inequality when symmetrized with symmetric function?

The relative entropy between two probability mass functions $p(x)$ and $q(x)$ can be computed with the Kullback-Leibler distante $$ D(p||q) = \sum_x p(x) \log \frac{p(x)}{q(x)} $$ The KL distance ...
2
votes
1answer
34 views

Kolmogorov complexity of a product of two numbers

In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $K(x)$ of a word $x$ consisting of zeros and ones as the binary length of the shortest Pascal ...
0
votes
1answer
44 views

Entropy of Input to N Parallel BSC's Given the Output

Given the N noisy observations $Y_{1:N}$ of a length-$L$ binary input sequence X passed through N parallel BSC's with the same crossover probability $p$, what is the entropy of the input sequence: \...
1
vote
1answer
19 views

Find upper and lower bound for the sum of the Hamming Distances?

Given an $[n,M,d]$ code, find an upper and lower bound for the sum $$\sum_{u,v \in C \\ u \neq v} d_{H} ( u,v)$$ From my understanding, the lower bound of any hamming distance is 1, so the lower ...
0
votes
0answers
30 views

Is there an intuitive explanation as to why Galois Fields exist only for a prime powers? [duplicate]

I am looking for an intuitive or example based explanation as to why Galois Fields exist only if the number of elements are a power of a prime. I find most explanations I've read difficult to ...
1
vote
1answer
26 views

Which is the continous probabilty density function that, given both standard deviation and a finite support, maximizes entropy?

It is fairly known that acorrding to the Entropy definition: $$ H=-\int p(x) \log (p(x)) dx $$ The Gaussian or Normal distribution maximizes the value of $H$. Also, if we have a finite Interval with a ...
0
votes
0answers
12 views

find the transmitted code BCH?

for a $(15,7)$ double error correcting BCH code with $G(x) = x^8+x^7+x^6+x^4+1$ if the recieved vector in $r(x)=x^9+x^5+x+1$ using $GF(2^4)$
0
votes
1answer
38 views

The monotonicity of the entropy operator

Define the entropy operator of a distribution as $\mathbb{H}(p) = -\int p \log p$, how does the entropy change for distributions that are proportional to the powers of $p$? For example, define $\...
1
vote
1answer
28 views

Maximise entropy of random sample of random distribution

Let $X_1, ..., X_n$ be positive discrete r.v.s such that $p^j_k = \mathbb{P}(X_j=k)$. Let $N \in \{ 1, ..., n\}$ be a discrete r.v. with pmf $a_j=\mathbb{P}(N=j)$. Then $X_N$ is the random variable ...
0
votes
0answers
52 views

Is there “information theory” for topological space?

Dear stackexchangicians, I have been reading an expository paper about the information theory founded by C. Shannon. The following question is vague, but has been there successful applications of ...
1
vote
0answers
24 views

Statistical interpretation of the Kullback-Leibler divergence ball

In many studies on robust optimization, sensitivity analysis, machine learning and so on, it is assumed that a set of the form \begin{equation} \Delta(\eta) = \{Q \in \Delta(X): D(Q||P) \leq \eta\}, \...
1
vote
0answers
35 views

Convexity of an alternative Rate-Distortion function

An alternative way of writing the rate-distortion function is: $$D(R) =\min_{p(\hat{x}|x):\ I(x;\hat{x})\leq R} \mathbb{E}[d(x,\hat{x})],$$ where $x,\hat{x}$ are variables, $d(x,\hat{x})$ is a ...
1
vote
1answer
43 views

Proving that for the class of i.i.d. processes $R_n^*=\frac{k-1}{2}\log n + O(1)$

Let $\mathcal{P}$ be the class of i.i.d. processes on $A^\infty$ where $A = \{ 1, \dots, k \}$, and let $Q$ be the coding process treated in class, $$Q(x_1^n)=\frac{\prod_{i=1}^k [(n_i-\frac{1}{2})(...
0
votes
2answers
60 views

Entropy of a Binary Sequence with Restrictions

Consider a length-L binary sequence $e_{1:L}$ of i.i.d. symbols, where a symbol can be $1$ with probability $p_{f}$ and $0$ with probability $1-p_{f}$. The entropy associated with such a sequence can ...
-4
votes
0answers
21 views

Why is “five-divide method” and “random-divide method” equal in “number guess game”?

set a range like [0,1000)digital, pick one number a like 733. "two-devide-method":First time you choose 500,and the host tells you it is smaller than a.Then you pick 750,next (500+750)/2.until pick ...
3
votes
1answer
89 views

Definition of Entropy

I am going through the book Computational Optimal Transport by Peyré and Cuturi. In it (see Formula (4.1), P. 65/209) I came across the definition of the discrete entropy, which is not what I expected:...
0
votes
2answers
106 views

Is this an entropy identity?

For $\mathcal{X}$ finite, take $\mathcal{X}$-valued random variables $x_1,\dots, x_n$ with some joint distribution and a function $f:\mathcal{X}^n\to \mathbb{N}^n$. Also choose $I$ uniformly randomly ...
1
vote
1answer
70 views

Best way to quantify amount of “information” in a matrix?

Given a matrix $X$ of dimensions $n*d$ my goal is to determine the amount of resources used by this matrix. The definition for resources used here is flexible, but relates to the amount of information ...

1
2 3 4 5
35