# 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.

2,467 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 679
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 ...
• 1,611
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 ...
• 65
70 views

• 11
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 ...
• 357
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 ...
• 3,521
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 ...
• 18.2k
1 vote
24 views

• 101
1 vote
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 ...
1 vote
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 ...
• 2,204
1 vote
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 ...
• 159
28 views

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{... • 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 ... • 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 ... • 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)... • 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 ... 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 ... • 26k 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 ... • 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 ... • 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,... 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 ... 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 ... • 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) =... 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,\... • 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]$. ... • 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 (... • 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)$... • 738 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 ... • 26k 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 ... • 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}$, ... • 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 ... • 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, ... 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, ... • 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 ... • 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=...
• 33
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 =\...