Skip to main content

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
1 vote
0 answers
49 views

Mutual information when sampling a random variable multiple times

Let $X$ be a random variable. For a fixed (known) preparation of $X$, suppose I have a protocol that generates a second random variable, $Y$, in a way that indirectly depends on $X$. Ultimately the ...
smitke6's user avatar
  • 679
0 votes
1 answer
31 views

Estimating the conditional entropy of a discrete variable conditioning on continuous variable

I am doing a machine learning project and I am trying to select the best features by computing their mutual information and select the ones with the highest information gain. I was looking at this ...
Ishigami's user avatar
  • 1,611
0 votes
0 answers
18 views

Is there a more general form of convolution useful for entropy-coding? [closed]

I have some unidimensional waveform data, and I wish to exploit its nearby point correlation before entropy-encoding it. The most basic operation that does this is Delta Encoding (using the finite ...
2 False's user avatar
  • 65
3 votes
1 answer
70 views

Intuitive explanation of "Information Filter" formation of Kalman filter

Can someone intuitively explain this "Information Filter" formation quoted from wikipedia ? In particular I struggle to understand why $\mathbf{I}_k = \mathbf{H}_k^\textsf{T} \mathbf{R}_k^{-...
CuriousMind's user avatar
  • 1,590
1 vote
0 answers
40 views

Decomposition of TV distance

Suppose $P$ and $Q$ are two joint distributions over (for simplicity, let's say discrete) random variables $X$, $Y$ such that $P(X,Y) = P_1(X)P_2(Y|X)$ and $Q(X, Y) = Q_1(X)Q_2(Y|X)$. Now construct a ...
Han Zhao's user avatar
1 vote
1 answer
35 views

Symmetric difference of Shannon's entropy satisfies triangle inequality

For random variables $X$ and $Y$, we define: $$\delta(X,Y) = H(X|Y) + H(Y|X)$$ Show that $\delta(X,Y)$ satisfies the triangle inequality. My attempt: I tried to write $H(X|Y) = H(X,Y) - H(Y)$, then I ...
vegetandy's user avatar
  • 305
0 votes
0 answers
9 views

Output process of Huffman encoding an i.i.d. source

A binary Huffman code for a pmf $(p_1,\dots,p_m)$ is constructed by starting with all $p_i$ as leaves and iteratively constructing a tree by merging the two nodes of lowest probability. Edges are then ...
hegash's user avatar
  • 195
0 votes
1 answer
25 views

Does Entropy really change depending on the encoding? [closed]

So I'm self studying information theory, and I have a few doubts on entropy and encoding as a whole. I'm trying to compress a simple 16bit signed int sequence of values the best I can. I learned about ...
2 False's user avatar
  • 65
0 votes
1 answer
22 views

Lengths of binary Huffman codes for uniform distribution

A binary Huffman code for a pmf $(p_1,\dots,p_m)$ is constructed by starting with all $p_i$ as leaves and iteratively constructing a tree by merging the two nodes of lowest probability. Edges are then ...
hegash's user avatar
  • 195
0 votes
1 answer
11 views

About the derivative of the conditional Rényi entropy

Preliminary considerations: In the paper unifying framework of information measures the conditional exponential entropy (see equation 29) is defined as: \begin{equation} \mathcal{E}_{\alpha}(X|Y) = ...
Upax's user avatar
  • 2,103
0 votes
0 answers
17 views

Measuring Robustness in Variational Bayesian Inference and Nonlinear Filtering

I am interested in how to properly pose/measure robustness, in a qualitative or potentially quantitative manner, when inferring a probability density function (pdf) either by Bayes' rule or a ...
kjc93's user avatar
  • 41
1 vote
1 answer
23 views

Kullback-Leibler divergence as a sum over “$T$” with product of multivariate Gaussians?

Imagine we have two multivariate Gaussian random variables and both of them can be written as the product of “$T$” individual probability density functions. Can we write the Kullback-Leibler ...
jrh229's user avatar
  • 11
1 vote
0 answers
18 views

Explanation of the notation for probability measures in the context of the Kullback-Leibler divergence sought

I came across some notation in the Wikipedia article https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence on the Kullback-Leibler divergence that I am unfamiliar with, in which the ...
Martin Vaughan's user avatar
1 vote
0 answers
25 views

Why does Elias's product code have vanishing error rate?

I am studying information theory and I just encountered a code constructed by Elias in 1954. I am struglling to understand why this code gives vanishing error rate, as is shown also in this lecture ...
ksks's user avatar
  • 11
1 vote
1 answer
30 views

Optimizing entropy of conditional Gaussians

this is a very specific problem, but i don't really know who to turn to to ask if my logic is correct, hence the post. My problem is the following: Let $V\in \{1,2\}$ be a random variable such that $P(...
Victor's user avatar
  • 11
0 votes
0 answers
19 views

Maximum Capacity of a Communication Channel w.r.t. $P(Y | X)$ when $X$ and $Y$ are discrete

Let $X$ and $Y$ be two discrete stochastic variables. I want to find $P(Y|X)$ that maximizes the mutual information between $X$ and $Y$, i.e., $$\max_{P(Y|X)} I(X, Y).$$ This problem is different from ...
Sam's user avatar
  • 357
2 votes
0 answers
78 views

Minimum information to order integers based on prime factorization without a priori knowing the order.

Suppose I give you the set $S$ that contains the integers $2$-$n$ but I have obscured it somehow so that you don’t know the true identity of S and you can’t discern the numeric notion of magnitude of ...
tyobrien's user avatar
  • 3,521
-1 votes
0 answers
43 views

How is this signal encoded?

In James V. Stones' Principles of Neural Information Theory on page 3 I found the following figure: Can some experienced information theorist tell at a glance which mathematical operation is used ...
Hans-Peter Stricker's user avatar
1 vote
1 answer
24 views

Appendix 1 of "A Mathematical Theory of Communication"

In Appendix 1 of "A Mathematical Theory of Communication", Shannon states: Let $N_i(L)$ be the number of blocks of symbols of length $L$ ending in state $i$. Then we have $$N_j(L)=\sum_{i,...
hchar's user avatar
  • 1,195
2 votes
3 answers
65 views

Shannon source coding theorem and differential entropy

Loosely speaking, Shannon's source encoding theorem says that there is an encoder with rate at least $H(x)$ such that $n$ repetitions of the source can be mapped to at least $nH(x)$ bits, such that ...
nervxxx's user avatar
  • 271
0 votes
0 answers
29 views

Mutual Information of two conditionally independent varibales given other varibale

I have data as $X$ which has two independent labels as $Y$ and $M$. So the goal is to process the $X$ to $Z_1=\mathcal{F}_1(X)$ to maximize $I(Z_1;Y|M)$. We know that: $$I(Z_1;Y|M) = I(Z_1;Y) - I (Z_1;...
mahdi_12167's user avatar
1 vote
0 answers
37 views

Valididity of information based solution to Monty Hall problem

The hypothesis: the probability that you will win by using the best strategy is equivalent how well you would do if you were given the minimum amount of information Monty needs to know. Ex. In the ...
Michael Wang's user avatar
1 vote
1 answer
24 views

Relative entropy and finite second moment bound

Suppose that $\nu$ is a probability measure (say on $\mathbb{R}$) with finite second moment. Let $\mu$ be another probability measure. Suppose that $KL(\mu \mid \nu)<\infty$. Does this then imply ...
pseudocydonia's user avatar
1 vote
2 answers
43 views

Why does block coding via typical strings give messages longer than $nH(p)$?

This semester, I am taking a course on quantum information and quantum computing. Since I am rather new to information theory I have a problem with understanding a paragraph in my lecture notes. The ...
luki luk's user avatar
  • 159
0 votes
1 answer
28 views

Codes with low error-control rate

Suppose that $C \subset \mathbb{F}_2^n$ is a code, and let $d = d(C) = \min\{d(x,y): x,y\in C\}$ the minimum distance of $C$, where $d(\cdot, \cdot)$ is the Hamming distance. We can define $r = \frac{...
blomp's user avatar
  • 571
1 vote
0 answers
21 views

Queues wait for other queues: A communication problem

I am working on a problem which involves a single server that requires multiple inputs to do a computation. Each of these inputs arrive as a Poisson process with rate $\lambda$. Hence, a situation ...
Ishan's user avatar
  • 36
0 votes
1 answer
55 views

Can you use entropy to find good splits in Guess Who?

In the game Guess Who, there are 24 characters with various traits. The objective is to guess the character of your opponent. I was wondering if it makes sense to use entropy as a measure of ...
hhh3's user avatar
  • 41
0 votes
1 answer
32 views

Derivative in information/rate theory

I am trying to understand how to obtain the following derivation w.r.t. $p(\hat{x}|x)$ but cannot for the life of me find out how they do. $$\frac{\partial}{\partial p(\hat{x}|x)} \left( \sum \sum p(x)...
idlatva's user avatar
  • 155
-1 votes
1 answer
28 views

Cosine similarity magnitude vector

there is one thing I'm not sure about regarding cosine similarity. Does the magnitude of the vector matter? I think the answer is yes, especially if you look at the picture below where the word count ...
Moooz's user avatar
  • 3
1 vote
2 answers
40 views

How can I design a non-integral-power efficient range coding that is statistically "fair" over the whole range?

Numbers are represented using binary digits "bits" which are integers in the set $\{0,1\}$. Positive integers for example, are usually encoded as a sequence of bits so that which power of 2 ...
mathreadler's user avatar
2 votes
0 answers
39 views

For a probability distribution is the difference between the largest and smallest probabilities bounded by the Shannon entropy?

Consider a set of probabilities $\{p_1, ..., p_N\}$ where $p_1\leq p_2\leq ... \leq p_N$. Now consider the difference between the largest and smallest probabilities $D =p_N-p_1$. I want to know if one ...
asph's user avatar
  • 404
0 votes
0 answers
26 views

Calculate the distortion measure $d(x,\hat{x})$

I want to to implement the Blahut-Arimoto algorithm to evaluate the clustering membership probability, $p(\hat{x}|\mathbf{x})$, with fixed number of clusters, $N_c$, and compression-distortion ...
idlatva's user avatar
  • 155
1 vote
0 answers
28 views

Confusion about Kraft-McMillan inequality for infinite alphabet

I was wondering if the Kraft-McMillan inequality continues to hold for codes with infinite alphabets. The reason I'm confused about this is because I was thinking about a code from $\{0,1\}^*$ to $\{0,...
user675763's user avatar
0 votes
0 answers
26 views

Lossless steering Order of Magnitude estimation

This is an equation from Rau's book "Quantum theory-an Information Processing Approach". It's leading to "lossless steering" of a particle if you insert an infinite number of ...
N1otAn1otherN1ame's user avatar
0 votes
1 answer
59 views

Negative mutual information example. What's wrong about it?

I'm aware that by definition the Mutual Information (MI) should be non-negative, and there are two related questions here: (1) and (2). However, I can think of an example in Physics where it is (or at ...
Girardi's user avatar
  • 355
0 votes
0 answers
32 views

Showing that the claim $I(X;Y) = I(X;Z)= 0 \implies I(X;Y;Z) = 0$ is true for jointly normal random variables only.

If we have three random variables $X,Y,Z$, which are jointly normal, how can it be shown that $I(X;Y) = I(X;Z)= 0 \implies I(X;Y;Z) = 0$? I know that for jointly normal distributions $X,Y,Z$: $I(X;Y) =...
proton100's user avatar
0 votes
1 answer
75 views

Functional Derivative Rate distortion theory

Can someone help me to see where the problem of the functional derivative below is? Minimize the functional: $$ F[p(\hat{x}|x)] = I(X; \hat{X}) + \beta \sum_{x \in X}\sum_{\hat{x} \in \hat{X}} p(x,\...
J.doe's user avatar
  • 173
2 votes
1 answer
48 views

Maximum Entropy and Minimum Divergence

Let random variable $X$ be defined over alphabet $X = \{-2, 0, 2\}$. a) Find the distribution $p(x)$ that maximizes the entropy $H(X)$ while maintaining $E\{|X|\} = \theta$, where $\theta \in [0, 2]$. ...
learner's user avatar
  • 21
1 vote
0 answers
21 views

How to construct a maximum-information embedding of sampled objects using a binary function?

This feels like a very specific problem, but I hope there already is a method to achieve what I want. There is a random process from which I can draw samples of non-numerical, variable sized objects (...
fazekaszs's user avatar
  • 153
3 votes
1 answer
115 views

Conditional Kullback Divergence

Let X be a discrete random variable drawn according to probability mass function $p(x)$ over alphabet $X$ , and let random variables $Y_1$ and $Y_2$ take value in alphabet $Y$ with probability $p_1(y)$...
Math Lover's user avatar
0 votes
3 answers
126 views

How can I find numerically nice-to-compute upper limits of nCr?

How can I find nicely behaving functions which are easy to compute and which fit well to the upper limits of the (2-logarithm) of the nCr function? What I am interested in in practice is to be able to ...
mathreadler's user avatar
1 vote
1 answer
41 views

Is it possible to decrease the channel capacity by adding a row to the coding channel matrix?

I have the following channel with $\mathcal X = \mathcal Y$: $ p(y|x) = \begin{bmatrix} 1/2 & 1/2 & 0 \\ 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2\end{bmatrix} $ Is it possible to ...
Danny's user avatar
  • 51
1 vote
1 answer
22 views

Convergence result for the union of type classes with bounded entropy

I need to prove the following in coding theory: For a set $\mathcal{X}$, the type of a sequence $x_1^n = (x_1,\ldots, x_n) \in \mathcal{X}^n$ is its empirical distribution $\hat{P}=\hat{P}_{x_1^n}$, ...
sicmath's user avatar
  • 362
11 votes
1 answer
248 views

Strategy for Black&White game

Consider the following game. Let $n$ be a positive integer. There are two players, $\newcommand\A{\mathrm{A}}\A$ and $\newcommand\B{\mathrm{B}}\B$, and a referee. $\A$ and $\B$ first agree on a ...
youthdoo's user avatar
  • 1,303
2 votes
1 answer
51 views

Inconsistency of capability of random coding in information theory and coding theory

In information theory, it is well known that the capacity of a channel can be achieved asymptotically using random coding method (Section 7 of Cover & Thomas' textbook). However, in coding theory, ...
Jiawei Wu's user avatar
0 votes
0 answers
19 views

Is the a version of typical set defined for non-i.d.d. sequences

For some context, recently I chanced upon the definition of typical set in information theory, and I had a feeling that it could be a useful tool to analyze large language models (LLMs). The issue is, ...
Sam's user avatar
  • 461
0 votes
0 answers
19 views

Minimum KL-divergence between histogram and continuous distribution with constraint on the mean

I am interested in finding the histogram's weights that minimize the KL-divergence with a uniform distribution, with for extra constraint that the means of both distributions should be equal. The ...
Nicolas's user avatar
  • 36
0 votes
0 answers
20 views

Differential entropy of independent samples of a random process

Suppose we have white gaussian noise $N(t)$ which is band-limited to B Hz and flat PSD with amplitude $\frac{\mathscr N}{2}$ in the freq. range [-B, B]. we do sampling from N(t) at Nyquist rate, $f_s=...
Ang's user avatar
  • 33
0 votes
1 answer
63 views

Conceptual Question regarding Shannon Entropy and bits

It is said that the number of "information bits" contained in a certain piece of information can be roughly translated as the number of yes/no-questions that would have to be answered in ...
Xerxes123's user avatar
8 votes
4 answers
359 views

Proving a multivariate normal distribution gets the maximum entropy when mean and covariance are given

I'm working on a homework question. The first part was: Given an unbounded one dimensional continuous random variable: $X\in\left(-\infty,\infty\right)$, that satisfies:$\left\langle X\right\rangle =\...
Nadav's user avatar
  • 469

1
2 3 4 5
50