Stack Exchange Network

Stack Exchange network consists of 175 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
2answers
73 views

Decomposing a discrete random variable

Note: this question is a duplicate of another question asked by my classmate with much more contexts. Attempt to suggest edits is rejected due to drastic change, so I reask the question. I hate to ...
0
votes
1answer
12 views

information entropy - why does a skewed probability distribution lead to smaller entropy?

System A: n=0.25prob. e=0.25. w=0.25 s=0.25 System B: n=7/16; e= 1/4; w=1/4; s=1/16; using information entropy formula system B has a smaller entropy. I thought that a distribution of probabilities ...
0
votes
2answers
11 views

Minimum entropy of a discrete random variable - find the appropriate distributions.

I am asked to determine what the minimum entropy of a discrete random variable might be. I have a hunch that the result will be zero, given that $$H(X) = \sum_i p(x_i)\log(\frac{1}{p{x_i}})$$ Let's ...
0
votes
0answers
33 views

Metaphors for the entropy of a question

What would be appropriate metaphors to call the entropy of a question? I was thinking along the lines of "information value," but this would clearly be inappropriate, because it is the answers that ...
2
votes
1answer
36 views

An inequality related to the Renyi divergence

Can you prove the following? Conjecture. Let $\lambda > 1$. Let $p_i$, $q_i$, $\mu_i$, $\nu_i$ be probability densities over $\mathbb R$ for $i = 1, ..., n$, such that for all $i = 1, ..., n$, (...
3
votes
3answers
109 views

How to maximize the expected number of corrected guesses?

A, B are to play heads or tails for $N$ rounds. They win a round if both guess correctly. A and B are allowed to communicate their strategy before the game starts. A knows the full sequence of $N$ ...
2
votes
0answers
22 views

Varshamov-Gilbert, question about proof with probabilistic method

Let $d \in \mathbb{N}$ such that $d \equiv 0 \pmod{4}$, and take $S_1, \dots, S_d \sim Bernoulli(0, 1)$. Define for $v \in \{0,1\}^d$ the ball $B(v, d/2) = \{w \in \{0,1\}^d : \|v - w\|_1 \leq d/2\}$....
-1
votes
0answers
12 views

How do I draw a tanner graph?

I have this question enter image description here I have this solution enter image description here In the solution can anybody explain how we got this graph for belief propagation? How do we know ...
0
votes
1answer
27 views

Analysis of Entropy on Two Distributions: Proving $H(X) < H(X')$

Let $P=\{p_1, p_2, p_3 ..., p_n\}$ and $P^{'}= \left\{ \dfrac{(p_1 + p_2)}{2}, \dfrac{(p_1 + p_2)}{2}, p_3, ..., p_n\right\}$ be distributions on the same random variable $X$. $1$. Show $H(X)\leq H(X^...
1
vote
1answer
36 views

There exists a measure-preserving transformation with any given (nonnegative) entropy

Let $(X,\mathscr{B},\mu,T)$ be a measure-preserving system and let $\xi$ be a partition of $X$ with finite entropy. Then the entropy of $T$ with respect to $\xi$ is $$h_\mu(T,\xi)=\lim_{n\to \infty}\...
1
vote
3answers
62 views

Do large integers carry more information than small integers?

Naively, the answer seems to be yes. Our representation of numbers in a base-ten system requires that large integers take more digits. Large numbers also take up more space when we write them in ...
0
votes
2answers
34 views

Difference between product distribution and joint distribution?

What is the difference between an $n$-fold product distribution and a joint distribution with $n$ random variables? Is it only defined for independent random variables? I am confused as to what is the ...
0
votes
0answers
17 views

Calculating a discrete maximum entropy prior

Given a discrete random variable $\theta$ that takes values on $\{\theta_i\}_{1\leq i \leq m}$, with probability $\pi(\theta_i)$ the entropy is defined as $$ \mathcal{E}(\pi) = -\sum_i \pi(\theta_i)...
1
vote
2answers
38 views

How to compare the entropy of two systems?

Suppose I have two systems $A$ and $B$ that produces the numbered tiles. System $A$ produces tiles 1, 2, 3, 4, and 5 with the probabilities: ...
0
votes
1answer
22 views

An inequality on mutual entropy

The question is as follows: Prove $H(X,Y,Z) - H(X,Y) \le H(X,Z)-H(X)$. Here, I tried to prove instead $$H(X,Z) - H(X) + H(X,Y)-H(X,Y,Z) \ge 0$$ I know that $H(X,Y,Z) = H(X,Y) + H(Z|X,Y)\ $ and $...
0
votes
1answer
20 views

Signal arrival time difference [closed]

How can i solve a signal arrival time difference for two-beam propagation model?
0
votes
0answers
22 views

Entropy calculation between binary and geometric random variables

I can't solve an exercise. I don't know how to suggest it. Let X be a geometrically distributed random variable; i.e., $$\text{p(X=k) = $p(1-p)^{k-1}$ where k = 1,2,3,...}$$ with 0$\lt$p$\lt$1. a) ...
0
votes
2answers
48 views

Variational Representation for Kullback-Leibler Divergence

In the book I'm currently studying, the KL Divergence is defined as follows:$$D(q||p) = qlog\frac{q}{p}+(1-q)log\frac{1-q}{1-p}$$ for $p,q\in(0,1).$ I want to convert this definition into a so-called ...
3
votes
1answer
48 views

What theorem in topology was Claude Shannon referring to?

In 1949, in a classic paper, Claude Shannon wrote the following: As we change the message a small amount, the corresponding signal will change a small amount, until some critical value is reached. ...
0
votes
0answers
32 views

Information Theory and Topology Textbooks

I am currently in need of a book (for an undergrad) that would serve as a good introduction to Information Theory, as well as the same for the subject of topology. To be more specific, I am interested ...
0
votes
0answers
23 views

Conditional-marginal KL divergence

I came across the following formula in a research paper and I am having a hard time understanding it. $KL(q(z|x) || q(z)) = -H(q(z|x)) - \int q(z|x) \log \int q(z|x')p(x')dx'dz$ Could someone ...
0
votes
0answers
22 views

how to calculate weighted mutual information

I would like to ask how to calculate weighted mutual information? Absolute mutual information is $H(A)+H(B)-H(A,B)$. In practice: $$H(A) = 0.3$$ $$H(B) = 1$$ $$H(A,B) = 1.25$$ Mutual information ...
4
votes
1answer
116 views

Set or list compression

Apologies for poor use of terms, I do not understand enough of the problem to even ask the right questions. My main question is, what domain of mathematics is this problem and is it solved problem ...
0
votes
0answers
27 views

Information content for one event

I have event that has probability $p=0.96$. There is such task: How many an information I need to determinate the event that has probability $q=0.04$? Anyway: How many bits I need to deteminate the ...
0
votes
1answer
34 views

Is it possible to get a solution for all inequality constraint values in Lagrange multipliers?

I am reading a paper on the Information Bottleneck Method. In this paper authors give a short review of rate distortion theory. In rate distortion theory we are interested in the rate distortion ...
0
votes
0answers
24 views

Deriving function for Information Content using continuity

I'm trying to understand the derivation of Shannon's formula for entropy and information content. I follow the proof up to here: For any $t,s \in (0,1]$ $$\frac{I(t)}{I(s)}=\frac{log(t)}{log(s)}=\...
0
votes
1answer
40 views

Discrete memoryless channel with 2 linearly dependent columns

Suppose we have a random variable $X$ taking in values in $\{ x_1, .., x_a \}$, and a discrete memoryless channel (DMC), $M$, represented as a matrix, with output alphabet $\{ y_1, .., y_b\}$where its ...
1
vote
1answer
40 views

Finding distribution to maximize entropy of a random variable subject to fixed mean

I saw this as a past paper question: $X$ is a random variable taking values in the positive integers, $\mathbb Z^{\geq 0}$, and has fixed mean $\mathbb E(X) = m$. Find the distribution of $X$ when ...
0
votes
1answer
29 views

Understanding mutual information derivation

The mutual information between the joint and marginal gives this proof: $$I(X;Y) = D(p(x,y) || p(x)p(y))\\ ... \\ \sum_{x,y}p(x,y) log p(x,y) - \sum_{x,y}p(x,y) log p(x) - \sum_{x,y}p(x,y) log p(...
0
votes
1answer
26 views

Understanding the conditional entropy derivation

This lecture on slide 5, has the following derivation which I don't understand their notation changes: let $(X,Y) \sim p$. For $x\in Supp(X)$ the random variable $Y|X=x$ is well defined. Q1: ...
0
votes
1answer
35 views

How to properly expand Expectation

I'm a bit confused with the expectation notation and how people use it. This one, in particular, is about entropy. They define Information as $$I(P) = -log(P)$$ and the entropy as the ...
-3
votes
1answer
40 views

Looking for formulas/equations, by which I can replace $1.8\cdot 10^{19}$ numbers.

I have a series of numbers between $281474976710655$ and $18446744073709552000$. I want to write one or more formulas/equations/etc. that can generate most of the numbers in the range. For example, I ...
1
vote
0answers
49 views

Distinguishing two channels with known probability distributions

Let $p(\cdot | \cdot)$ and $q(\cdot | \cdot)$ be two known channels from alphabet $X$ to $Y$. What is the optimal strategy to distinguish between them if you are allowed to use the channel only once, ...
1
vote
0answers
20 views

Conditionnal entropy : intuitive interpretation

Consider two system $X$ and $Y$ described by probabilities distribution. We define the conditionnal entropy of $X$ knowing $Y$ as : $$S_{X|Y}=\sum_y p(y) \left( - \sum_{x} p(x|y) \log(p(x|y)) \right)...
0
votes
0answers
40 views

Finding the Information Gain in sets

I have a universe, $ U = \{a, b, c, d, e, f\}$ and sets $A = \{a, b, c\}$ and $B = \{a, d, e, f\}$ If $P(A) = P(X = x \in A)$ and $P(B) = P(X = x \in B)$, where $X$ is a random variable defined by ...
0
votes
1answer
25 views

Upper bound of Mutual Information

The Shannon entropy of a discrete random variable ${\textstyle X}$ with possible values ${\textstyle \left\{x_{1},\ldots ,x_{n}\right\}}$ and probability mass function ${\textstyle \mathrm {P} (X)}$ ...
0
votes
1answer
37 views

Log det of covariance and entropy

I understand log of determinant of covariance matrix bounds entropy for gaussian distributed data. Is this the case for non gaussian data as well and if so, why? What does Determinant of Covariance ...
0
votes
1answer
83 views

Why is this inequality about KL-divergence true?

Let $p,q \in [0,1]$. Then the following bound seems to hold: $$ p \log \frac{p}{q} + (1-p) \log \frac{1-p}{1-q} \leq \left( \log \frac{p}{q} - \log \frac{1-p}{1-q} \right)^2$$ The left-hand side is ...
0
votes
0answers
12 views

mutual vs join entropy interpretation

If I have joint entropy = 10 bits and mutual information = 2 bits, could we say our two distributions have only 0.4% of useful communication overall? Or to say it differently: 99,6% is complete noise....
1
vote
0answers
27 views

Bound for type of correlation measure

Assume you have a finite, discrete probability distribution for a joint random variable and such that $P(X=i,Y=j) = p_{i,j}$ for $i \in \{1, \dots, |X|\},j \in \{1, \dots, |Y|\}$. The marginal ...
0
votes
1answer
22 views

Can we increase the channel capacity of a channel?

I'm reading about Channel capacity from Elements of Information theory - Wiley (2006). The definition of channel capacity, which is characterized by $p(y|x)$, is $\hspace{3.0cm} C = \max_{p(x)} I(X; ...
0
votes
1answer
20 views

Entropy of a normal distribution in Bits versus Nats in book Elements of Information Theory

This should have been easy. Converting between nats and bits is a logarithmic change of base. So going from $\log$ base $e$ to base $2$, should require the denominator to have $\log_2(e)$. However in ...
0
votes
1answer
25 views

can mutual entropy be higher than joint entropy?

Let's assume I have three probability distributions A,B,C. The entropy of each is 1.58, with joint entropy 1.58. Calculating mutual entropy with formula I(A,B,C) = H(A)+H(B)+H(C)-J(A,B,C) results ...
2
votes
0answers
19 views

Understanding a likelihood as a loss function

Paper Link (IJCAI'18 Yang et al): http://dmkd.cs.vt.edu/papers/IJCAI18.pdf In the following paper, the authors defined Eq.8 as the conditional check-in rate in the Recurrent-censored Regression model ...
0
votes
0answers
34 views

Why people like Hoeffding's inequality more than CLT?

I am reading some paper in information theory and machine learning, and I found that many people like to use the Hoeffding's inequality rather than the CLT. I know the Lindeberg Feller CLT can also be ...
0
votes
0answers
14 views

Minimum and Maximum Data Points in a Spectrum

If I am collecting data that will be used to assemble a spectrum, how often should I take a data point to properly sample, but not oversample given the following information? I can control my data ...
0
votes
1answer
32 views

$d(\xi, \eta) = H_{\mu}(\xi|\eta) + H_{\mu}(\eta|\xi)$ defines a metric

I want to show that $d(\xi, \eta) = H_{\mu}(\xi|\eta) + H_{\mu}(\eta|\xi)$ defines a metric on the space of all partitions (considered up to sets of measure zero) of a probability space $(X, \mathscr{...
1
vote
0answers
23 views

Reversible analog coding of strings (mathematical expressions)

Neural coding converts single word or single sentence of words into the vector of real numbers. This coding, while sometimes useful, is not revertible. Are there methods (or at least research effort ...
0
votes
0answers
29 views

The Coding Theorem

Can you please give any hint for part c ?
2
votes
0answers
65 views

Is there more efficient way to to find maximum pairwise hamming distance in an array of hashes then brute force O(N^2) algorithm?

We have unsorted array of hashes, each hash is a 64bit integer. We need to find the pairwise hamming distance in an array. What state the problem to find maximum Manhattan distance between points in ...