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.

learn more… | top users | synonyms (1)

1
vote
0answers
82 views

Entropy Rate of a sequence of Random Variables with Distributions related to Primes

Let us consider a stochastic process $\mathcal{X}=\{X_i\}_{i \in \mathbb{N} }$ where $X_i$'s are independent and $X_i$ is distributed as $$X_i=p_k \ \mbox{w. p.}\frac{p_k}{\sum_{l=1}^{i}p_l},\ 1\leq ...
3
votes
1answer
133 views

Positivity of Renyi Mutual Information

The differential Renyi entropy for a probability distribution is given by $H_q(P(X))=\frac{1}{1-q}\log\int p^q(x)dx$. In the limit of $q\to 1$, it reduces to the usual Shannon entropy. We can write ...
0
votes
1answer
94 views

questions in channel capacity

Q) Suppose we have a set of t coins, all but two of which have uniform weight $0$. and two counterfeit coins have different weights$>0$. If one can only use a spring scale, what is the ...
1
vote
1answer
55 views

approximate $[0, 1]$ continuous function with 2d basis.

everyone. I've been thinking of this problem when reading papers about Fourier series. I think I can state my question as follows: in the interval $[0, 1]$, I want to approximate an unknown ...
6
votes
1answer
232 views

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one ...
3
votes
2answers
262 views

Intuition of information theory

I am reading the book "Elements of Information Theory" by Cover and Thomas and I am having trouble understanding conceptually the various ideas. For example, I know that $H(X)$ can be interpreted as ...
2
votes
0answers
110 views

Lower bound on uncertainty reduction

Let $T$ be a set of tuples such that each score tuple $s(t_i)$, $t_i \in T$ is uncertain (i.e., not known deterministically). The score $s(t_i)$ can be represented as a uniform probability density ...
0
votes
1answer
51 views

Optimization of entropy for fixed distance to uniform

Suppose that I know that a probability distribution with $n$ outcomes is very close to being uniform (that is: $\forall i,p_i=\frac{1}{n}$), and in particular for $n\epsilon\ll 1$ the distribution ...
3
votes
1answer
119 views

Source coding theorem - optimum number of bits?

The source coding theorem says that information transfer with variable length code uses less bits and is equal to the entropy of the distribution. It also says that there is no code that uses lesser ...
0
votes
1answer
110 views

concatenation of channels

Assuming I have 2 channels: BSC => Z Z=> BSC the first channel is a concatenation of the BSC channel and then the Z channel. the second channel is a concatenation of the Z channel and then the BSC ...
2
votes
1answer
89 views

Properties of Entropy

When someone writes $H(X_1, X_2, X_3) = H(X_1) + H(X_2\mid X_1) + H(X_3\mid X_2, X_1)$, how should that last term be interpreted/read? As the joint entropy between 2 variables where variable 1 is ...
3
votes
0answers
54 views

Is there a conditional version of the asymptotic equipartition property?

Let $X_i$ be independent random variables with $\operatorname{Pr}(X_i = x) = p_x$, and let $F_n$ be the empirical frequency distribution of $X_1, \ldots, X_n$: that is, $(F_n)_x$ For any frequency ...
2
votes
1answer
78 views

Conditional Probability, Lack of Dependence on a Parameter

I am trying to understand why the following is true: $$ p(f(Y) = f(y) \mid Y = y) = p(f(Y) = f(y) \mid X = x, Y = y) \qquad \ldots \text{(Eq. 1)} $$ where $Y$ and $X$ are random variables, and $f(Y)$ ...
6
votes
3answers
310 views

Another Information Theory Riddle

The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay. In a magic trick, there are ...
2
votes
2answers
229 views

How can you use a (fair) coin to draw straws among 3 people? (Information Theory) [duplicate]

The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay. How can you use a (fair) coin ...
0
votes
0answers
70 views

Intregral of exponential of Shannon Entropy Function

Here I am going to ask a similar question as rde asked , that is what is the integral of exponential of entropy function. That is what is the value of $F[H(x)]=\int_{-1}^{+1} e^{ikH(f(x^2))} dx$ ...
1
vote
1answer
94 views

Information content associated with an outcome

I have the following exam question for a multimedia exam in college: Assume that you roll a single ordinary six-sided die twice, and observe that the second number rolled is greater than the ...
2
votes
4answers
174 views

What exactly is a probability measure in simple words?

Can someone explain probability measure in simple words? This term has been hunting me for my life. Today I came across Kullback-Leibler divergence. The KL divergence between probability measure P ...
0
votes
1answer
109 views

How information works?

I am really confused after reading wikipedia... What I don't get is how can something "bring" information, and in mathematics, how a mathematical object (like a set) can "have" information. For ...
1
vote
0answers
44 views

Hellinger distance between 3-parameter Weibull distributions

I found Wikipedia to have listed Hellinger distance between pairs of 2-parameter Weibull distributions sharing the same shape parameter http://en.wikipedia.org/wiki/Hellinger_distance However, I ...
0
votes
1answer
48 views

What is being maximised in the channel capacity formula?

The channel capacity formula is given as such: $$C=\max_{p(x)}I(X,Y)$$ Does this mean that it is the maximum probability multiplied by the mutual information, or is something else being maximised ...
1
vote
1answer
78 views

Entropy vs predictability vs encodability

Imagine there's a guessing game where a series of binary symbols are presented and a human must decide quickly if the symbol is the same as the previous or different. There's a property of the ...
2
votes
1answer
47 views

Shannon inequalities

I have some difficulties in showing the relationship between mutual information $I(X; Y |Z)$ and $I(X; Y)$? What is larger?
0
votes
1answer
45 views

The information of a Bernoulli random variable and surprisingness

Consider a random variable $\mathbb{X}$ with: $f(x;p) = 2^{-n}$ if x = 1 and $f(x;p) = 1-2^{-n}$ Then the information gained from an experiment where x=1 is ...
10
votes
3answers
266 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
2
votes
0answers
56 views

Computing Relative entropy?

I am doing a project for my CS class and I was wondering if the following would work. I have 50 different people who have rated the same 50 books. The rating system is as follows: negative 5 = hate ...
0
votes
1answer
49 views

Possible Mistake in Calculating Posterior of Distribution using Bayes Rule and Integration

I have been struggling on a homework question where I have to compute the posterior density of a distribution. While I can compute the posterior, I believe I made a mistake because the area under the ...
7
votes
3answers
188 views

Measure of how much information is lost in an implication

In an implication like $p \implies q$, is there some measure of how much information is lost in the implication? For example, consider the following implications, where $x \in \{0,1,\ldots,9\}$: ...
3
votes
0answers
88 views

Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
1
vote
0answers
67 views

convexity of the product of two entropy-like functions

Consider the functions $T_p(q)= \sum_i q_i^p$, where p>1 and q is a finite-dimensional vector satisfying $\sum_i q_i = 1, q_i >0$ (ie, a probability mass function). In information-theoretic terms, ...
1
vote
1answer
54 views

Entropy: Is $H(X_{1},X_{2}) = H(X_{1})$ true?

Question: If $X_{1}, X_{2}$ are two discrete random variables. $X_{1}, X_{2}$ have the same probability distribution can we then deduce that: $H(X_{1}, X_{2}) = H(X_{1})$ is true? Remark: ...
0
votes
1answer
50 views

Easy bound involving logs and binomial coefficients

I am currently working on an information theory problem where I have to bound the divergence between two distributions. The divergence can be simplified to: $$\sum_{k=0}^N \ {N\choose k} ...
0
votes
1answer
49 views

i.i.d binary random variable question

Suppose there are i.i.d. binary random variables $X_i \sim X$ with distribution $P(X=1) = 0.75$ and $P(X=0) = 0.25$ i) For $n=5$ and $e=0.1$, which sequences fall in the typical set $A_e^n$? What is ...
0
votes
1answer
104 views

Help deciphering Levenshtein formula

I am trying to completely understand the Levenschtein formula, and I have been reading the Wikipedia article on this. However, the description of the mathematical formula confuses me: ...
0
votes
1answer
49 views

Expanding information capacity of Gaussian Channel

I'm currently try to understand a Gaussian Capacity Channel. I found litterature on internet, and some expand the information capacity of a Gaussian Channel as follow: $$I(X,Y)= h(Y) -h(Y\mid X) = ...
4
votes
3answers
129 views

Does any error correction code still work in such situation?

I'm looking for a kind of error correction code or solution that can correct my codeword in this case: My message holds k bits, and 2*k bits codeword (rate is 1/2) is produced by the generator ...
2
votes
1answer
61 views

Amount of information a hidden state can convey (HMM)

In this paper (Products of Hidden Markov Models, http://www.cs.toronto.edu/~hinton/absps/aistats_2001.pdf), the authors say that: The hidden state of a single HMM can only convey log K bits of ...
13
votes
7answers
1k views

Intuitive explanation of entropy?

I have bumped many times into entropy, but it has never been clear for me why we use this formula: If $X$ is random variable then it's entropy is: $$H(X) = -\displaystyle\sum_{x} p(x)\log p(x).$$ ...
10
votes
3answers
358 views

What is the least amount of questions to find out the number that a person is thinking between 1 to 1000 when they are allowed to lie at most once

A person is thinking of a number between 1 and 1000. What is the least number of yes/no questions that we can ask and know what that person's number is given that the person is allowed to lie on at ...
28
votes
2answers
310 views

Information-theoretic aspects of mathematical systems?

It occured to me that when you perform division in some algebraic system, such as $\frac a b = c$ in $\mathbb R$, the division itself represents a relation of sorts between $a$ and $b$, and once you ...
2
votes
1answer
72 views

Infinite Bias in a Maximum Likelihood Estimator

I'm having some problems calculating the bias of a ML estimator in the following problem: Let $\mu$, $x$, $y$ be random variables such that: $y|x$ is distributed as $\exp(x)$ so that $p(y|x) = ...
1
vote
1answer
100 views

Expression for the size of type class, or multinomial coefficient.

The notations follow those in Cover&Thomas, "Elements of Information Theory", 2ed. I saw from a paper that the size of type class $T(P)$ can be expressed as ...
0
votes
0answers
87 views

Rigorous formulation of Shannon-Hartley theorem

The Shannon-Hartley theorem gives an expression for the capacity of a bandwidth and power limited channel. How would one formulate this theorem mathematically (rigorously)? I understand the formula ...
3
votes
0answers
246 views

Intuition for Fisher information metric

In statistical maniolds $S=\{p_\theta\}$,$\theta=(\theta_1,\dots,\theta_n)$, the Riemaanian metric usually defined is the Fisher information metric $$g_{ij}(\partial_i,\partial_j)=\int \partial_i(\log ...
0
votes
1answer
43 views

Decoding used in Algorithms

Using a transposition matrix of size 4 by 6 (4 columns, 6 rows) and key ‘time’ decode the following message: RLAPET HWBUIE EIERSS TELSRT I am just looking for either a starting point or a step by ...
0
votes
1answer
92 views

mutual information problem

Consider the following problem: What is $I(X;Y)$ where $X$ is the outcome of a roll of a fair 6-sided die and $Y$ is whether the outcome of THAT SAME ROLL was even or odd? Intuitively, I thought ...
0
votes
1answer
188 views

Entropy Problem: mutual information

I have a problem about entropy and mutual information that I have attempted, but would like feedback on. 30% Boas 20% Anaconda 50% Cobra Half of the Cobras were medium sized, and the other half were ...
1
vote
1answer
77 views

About the differential entropies of well-known continuous distributions

Assume that the continuous random variable $X$ has a distribution (in a closed form expression) with differential entropy $h(X)$. Q) Then, is it true for any continuous distribution that the ...
1
vote
0answers
168 views

Random variables identities - how to make a formal proof.

Let $X, Y, Z$ be three random discrete variables. Consider the below random variables: $A = X\vert Y\vert Z$ ,$B= X\vert Y,Z$ Question: Can I conclude that $A$ and $B$ are the same ...
1
vote
1answer
76 views

One cannot know if a number could be written any shorter according to Gödel's incompleteness theorem

I am reading Tor Nørretranders (cannot find the English version, sry) and he states that Gödel's incompleteness theorem implies that we cannot know if we can write a number any shorter (e.g. ...