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
0answers
6 views

Non parametric estimation of point process entropy

Let point process $\Phi$ be defined on some bounded set $A$ in the borel $\sigma$-algebra on $\mathbb{R}^d$, and assume that the parametric structure of $\Phi$ is unknown. Let $\{x_1,\ldots,x_N\}$ be ...
0
votes
0answers
29 views

Show that ${n \choose \lambda n} p^{\lambda n}q^{ \mu n}\approx \frac{2^{nD\left(\lambda || p\right)}}{\sqrt{2\pi \lambda \mu n}}$

I have the following problem: Use the Stirling formula $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}$ to show that $${n \choose \lambda n} p^{\lambda n}\left(1-p\right)^{\left(1-\lambda\right)...
2
votes
1answer
32 views

How to interpret that a distribution does not have defined entropy (or has infinite entropy)?

An entropy (is Shannon sense) can be interpreted as uncertainty or missing knowledge. When the knowledge is added, the entropy decreases. Hence it can also be interpreted as information content. ...
0
votes
0answers
21 views

Seeming abitrariness of the Maximum Entropy Distribution

I have a two parameter model $C = (C_1, C_2) \in \mathbb{R}^2$ and would like to look at the choice of parameters from a stochastic point of view. A minimal set of constraints on $C$ is that The mean ...
0
votes
0answers
20 views

Biprefix code and word factorization

Let $Y_1$ a biprefix code over a free monoid $A^{*}$. Let $u= x_{i}y_{j}$ and $v= x_{i}’y_{j}’$, with $x_i, x_i’ \in A^*$ and $y_j, y_j’ \in Y_1$. If $u=v$, while does this imply that $y_{i} = y_{i}’$...
1
vote
1answer
52 views

Entropy of extractions

A box contains $3$ white and $6$ black balls. We draw $2$ balls consequentially without replacement. Find the entropy of first and second extractions and the entropy for both of them.
0
votes
1answer
15 views

Conditional Mutual Information - Cover exercise

Following is the exercise from T. Cover's Elements of Information Theory While I understand that $$I(X_{n-1}; X_n \mid X_1, \ldots, X_{n-2}) = H(X_{n-1} \mid X_1, \ldots, X_{n-2}) - H(X_{n} \mid X_1, ...
3
votes
2answers
69 views

Show that $G\left(n,p\right)e^{-\frac{1}{12np\left(1-p\right)}}<{n\choose pn} < G\left(n, p\right)$

The problem: Using the inequalities $\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}e^{\left(\frac{1}{12n}-\frac{1}{360n^{3}}\right)} < n! < \sqrt{2\pi n}\left(\frac{n}{e}\right)^ne^{\frac{1}{12n}}$ ...
0
votes
0answers
10 views

modulating object properties and demodulating it using numbers [closed]

Say for example I have three shapes and three colors and every shape can be in one of the colors so we have nine possibilities, i wanna a way to find a number(x) that encodes the shape and the color ...
0
votes
0answers
16 views

Generalising Information Entropy to Compare Distributions

Intuitively I think of information entropy as representing something like scientific knowledge. It’s surprisingly difficult to define scientific progress, but I think a reasonable definition is that ...
-1
votes
0answers
37 views

Probability distribution and information theory

In the study of statistics, a given family of probability densities depending smoothly upon a parameter $\theta$ can be expressed in the form $p(x,\theta)=exp\left[c(x)+\sum_{r}\theta^{r}S_{r}(x)-\psi(...
0
votes
0answers
34 views

Entropy vs Relative Entropy.

Can anyone help me reconcile two well known observations. $\textbf{Observation 1}$ The Second Law of Thermodynamics says that a system wants to minimise (the negative of entropy) $$ H(\rho):=\int \...
0
votes
0answers
90 views

Differential entropy from samples: $\int_{-\infty}^{\infty} p(x) \log(p(x)) dx$

Question I am trying to calculate the differential entropy of a probability distribution with an unknown probability density function $p(x)$ but for which I have multiple samples. The random variable, ...
0
votes
0answers
15 views

Conditional Entropy $H (X + z_1 | X + z_2)$ [closed]

How does the Conditional Entropy $H (X + z_1 | X + z_2)$ where $z_1$ and $z_2$ are independent RVs simplifies?
-1
votes
0answers
14 views

What is/could be “input cost function” [closed]

In the following article - https://www.researchgate.net/publication/3084702_To_Code_or_Not_to_Code_Lossy_Source-Channel_Communication_Revisited The authors defined input cost function $\rho(x)=D(p_{Y|...
0
votes
0answers
30 views

Maximum Value of the Entropy Rate of a Two-State Markov Chain

So I have a problem asking for the entropy rate and the maximum value of that rate. I have found the rate, but I am having trouble finding the maximum value. The problem: Find the entropy rate and the ...
1
vote
1answer
28 views

Kraft Inequality Proof error

In every proof of this theorem I see, I get stuck by the same thing. Once we choose the final node $v_n$ at depth $l_n$ to be the code word of length $l_n$, the subtree rooted at that $v_n$ has no ...
0
votes
1answer
24 views

Kleene Star over a formal Language containing Unions

I am a little bit confused, how the following language should be understood or further more, how the Kleenestar is interpreted in some ways: $ ( \{0\} \cup \{1\}^*)^*$ I think the language looks like ...
0
votes
0answers
22 views

Meaning of Relative Entropy

KL divergence means Expectation log of 1 likelihood by another ie., $E_{X \sim P_{\theta}}[- \log \frac{P_{\theta}(x)}{Q_{\phi}(x)}]$. Overall it means what is the average gap between the 2 ...
0
votes
1answer
26 views

Shannon entropy of languages

In his paper Prediction and Entropy of Printed English Shannon defines the entropy $H$ of a language as $$H = \lim_{N \to \infty} F_N$$ where $$F_N = \sum_{i, j} p(b_i, j) \log p(j | b_i)$$ where $b_i$...
1
vote
1answer
42 views

Sum of squared probability distribution $\sum_c p_c^2$ is a measure of uncertainty?

Can the sum of squared probabilities, i.e. $\sum_c p_c^2$, be considered to be a measure of uncertainty? If so, does it have a mathematical name or theory? The form is similar to Shannon's entropy, $-\...
1
vote
0answers
21 views

Is there any value related to a time series pattern?

I've been digging a little into signals and I just started a networks and telecommunications class at college. We saw there are different encode techniques Amplitude, Frequency and Phase shift keying (...
0
votes
0answers
15 views

Information content of an inaccurate classification

I am trying to see how much information I am giving when I am making a classification. Say that there are $n$ classes, each with probability $p_i$. Now I have trained a classification model that ...
0
votes
1answer
26 views

Relation involving entropy and dimension

Assume $n$ is a postive integer much larger than $\ell$. Let $\tau$ be a distribution over $\mathbb{F}_p^\ell$ satisfying $n\cdot\tau(x)\in\mathbb{N}$ for all $x\in \mathbb{F}_p^\ell$ (and $\sum_{x\in\...
2
votes
1answer
25 views

Are bits defined in a Boolean ring?

Premise: I'm not a mathematician, please be patient. Anyway, if I consider the Galois field $GF(2)$ and two operations $+$ (inclusive or, also denoted with $\lor$) and $\neg$ (negation), where, given $...
0
votes
1answer
30 views

Interpretation of a discrete channel and $(M,n)$ codes

I'm having trouble understanding what the right way to think about the presentation of discrete channels and codes in text by Cover and Thomas. A discrete channel is a system consisting of an alphabet ...
1
vote
1answer
24 views

Law of large numbers for non-stationary but independent process?

This question is motivated by the following: Suppose we have a conditional distribution $p(Y|X)$, denoting a “channel” (in the information theory sense). Suppose we fix a particular sequence $x_1,...$,...
1
vote
1answer
27 views

Gradient of Gaussian entropy w.r.t. $W$

I have been struggling with deriving a gradient in matrix form for the following function. (w.r.t. $w$) $$ H(w) = \sum_{i = 1}^{n} p(y_i - x_i^T*w) \log (p(y_i - x_i^T w)) $$ where $$p(x)$$ is the ...
0
votes
0answers
42 views

Relation of entropies under linear transformation

The entropy $H(X)$ of a random variable $X$ that takes value on a finite set $S$ is defined to be $$H(X)=-\sum_{x\in S}\mathbb{P}(X=x)\log(\mathbb{P}(X=x)).$$ Now assume $X$ takes values in $S=\mathbb{...
0
votes
1answer
73 views

Information lost in going from n-dice rolls to the sum of their faces?

I'm trying to understand how to figure out how much information is lost in going from n dice to the total score. If I rolled n-dice I could add up their face values to find the total sum, however if I ...
1
vote
1answer
33 views

Why a matrix with a low entropy will be sparser?

The entropy of a matrix $\mathbf{P}$: $$H(\mathbf{P})=-\sum_{i j} \mathbf{P}_{i j} \log \mathbf{P}_{i j}$$ Why a matrix with low entropy will be sparser, and with high entropy will be smoother?
1
vote
1answer
41 views

Entropy of a Fair Coin Toss

The problem: A fair coin is tossed until a a heads is reached for the first time. What is the entropy $H\left(x\right)$ in bits? My solution: Because $P\{X=i\}=\left(\frac{1}{2}\right)^i$, $H\left(x\...
0
votes
2answers
32 views

Channel Decoding: Gaussian Channel as Time-Varying Binary Symmetric

I am reading Information Theory, Inference and Learning Algorithms by David MacKay. It is available free of charge online: http://www.inference.org.uk/mackay/itila/book.html (official site, not ...
1
vote
1answer
31 views

Gibbs' inequality; continuous case

I'm reading alternative proof of Gibbs' inequality written in wikipedia, which states that Suppose that $P=\{p_1,...,p_n\}$ be probability distribution. Then for any other probability distribution $Q=...
7
votes
1answer
125 views

Is there a way to find the value of the largest entry of a hidden vector of integers?

Consider the following set-up: A person has a vector of with integer entries, which is not known to you. The person refuses to reveal the vector to you; however, you may supply another vector with ...
1
vote
1answer
23 views

Number of conditional types

Let $A = \{1, 2, ..., J \}$ and $B = \{1,2, ..., K \}$. A sequence $x^n \in A^n$ induces a probability distribution $t$ called the type where \begin{align} t(j) = \frac{1}{n} |\{x_i:x_i = j \}| \,\,...
2
votes
2answers
116 views

Permutation-invariant embedding preserving as much information as possible

Suppose there are 2 discrete random variables $x$ and $y$ that each can take $n$ possible values, and $n$ is not too large, at most 10. Then their joint PMF $p \in \mathbb{R}^{n^2}$ is a histogram of $...
0
votes
0answers
53 views

Doubts on some definition of Shannon's entropy notion

I would like some clarifications on two points of Shannon's definition of entropy for a random variable and his notion of self-information of a state of the random variable. We define the amount of ...
0
votes
0answers
27 views

Are there any tight upper bound for KL divergence like the DV bound?

We know that from the DV representation we can write a lower bound for the KL divergence that is easy to be used in machine learning: $$KL(P||Q)\le E_P[T]-log(E_Q[e^T])$$ This bound is useful in ML ...
0
votes
0answers
46 views

How to compare the entropy of copulas?

Three different bivariate copulas are shown below with increasing degrees of dependence (parameter $\theta$). Differential entropy is a measure of disorder in a probability density like the copula. ...
0
votes
1answer
19 views

Conditional Entropy - How to deal with zero-valued probabilities?

I would like to calculate $H(Y|X)$, however, for some values of $X$ and $Y$, I have probabilities which are zero. I understand that for calculating entropy such as $H(X) = \sum p(x)log(p(x))$, if $p(x)...
0
votes
0answers
39 views

Application of Pinsker's inequality

I am not very experienced with Information Theory and I trying to the following exercice in Rao&Yehudayoff's book: Let $n$ be odd and let $x \in \{0,1\}^n$ be sampled uniformly among all $x$ with $...
2
votes
1answer
58 views

Derivation of equation. Mackay pg. 17

Can someone explain how the final equation is obtained? I cannot understand how the exponential term occurs. from Mackay Pg. 17 $1=\sum_{K}\left(\begin{array}{l}N \\ K\end{array}\right) 2^{-N} \simeq ...
2
votes
3answers
87 views

Solving Coin-Weighing Problem (81 Coins, 1 Fake) Using Information Theory

So I have a coin-weighing puzzle under these situations: There are 80 real coins and 1 fake coin (total of 81 coins). The real coins are all the same weight, and the weight of the fake coin is ...
3
votes
1answer
55 views

Measuring the Shannon Entropy of an ordered sequence

I have 927 unique sequences of the numbers 1, 2 and 3, all of which sum to 12 and represent every possible one-octave scale on the piano, with the numbers representing the intervals between notes in ...
0
votes
0answers
25 views

Hamming distance vs absolute value constraint

In this case, what is the HD according to each bit position between $x_g$ and $x_h$? I want the linearized HD value i.e., expressed with this $z_{g,h,l}$. E.g., when n=4, the HD value when l=1,2,3,4.
1
vote
0answers
26 views

Can information transmission be proven in a Rule 30 ECA?

(This is hopefully a clearer version of an earlier post of mine.) I have been spending lots of time on the open challenge of proving the aperiodicity of the central column of a rule 30 cellular ...
0
votes
0answers
25 views

How does negative copula entropy imply reduction in uncertainty like mutual-information?

Mutual information measures the reduction in uncertainty in a random variable $X$ from knowing additional information from another variable $Y$. If we instead measure the mutual information of $X$ ...
1
vote
1answer
40 views

How to compare two variables whose differential entropy are both negative?

I know that a higher positive value for entropy indicates greater uncertainty, but not sure how this works when comparing two negative values If two continuous random variables $X$ and $Y$ have ...
0
votes
1answer
61 views

Proving Convexity of KL Divergence w.r.t. first argument?

I'd like to show that the KL divergence is convex w.r.t. its first argument, where the KL divergence is defined as $KL(q|p) = \sum_x q(x) \log \frac{q(x)}{p(x)}$ This question suggests that I can show ...

1
2 3 4 5
38