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)

3
votes
0answers
53 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
77 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
308 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
221 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
93 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
171 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
43 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
47 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
77 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
44 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
263 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
48 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
187 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
65 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
48 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
101 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
48 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
60 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
356 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
98 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
86 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
242 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
90 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
185 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
76 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
165 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. ...
1
vote
2answers
79 views

Ask for a question about independence

This is the question I met while reading Shannon's channel coding theorem. Assume a random variable $X$ is transmitted through a noisy channel with transition probability $p(y|x)$. At the receiver a ...
0
votes
1answer
42 views

A question about independence of bivariate random variables

Assume we have two bivariate random variables $(X_1,X_2)$ and $(Y_1, Y_2)$ and the distribution satisfies $p(y_1,y_2|x_1,x_2)=p(y_1|x_1)p(y_2|x_2)$. I can prove that if $X_1$ and $X_2$ are ...
1
vote
2answers
252 views

How to prove the following entropy formula?

Could anyone show me a proof or redirect to a source where the following entropy equation is proved? =) $$H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$$ Thank you!
7
votes
1answer
249 views

Does “50/50 chance of.. . ” convey information?

I distinctly remember the professor in the undergrad introductory systems & control course saying that "when weather forecasters say there's a 50% chance of precipitation, they are conveying no ...
8
votes
1answer
210 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
1
vote
0answers
45 views

$f(n) = n^2 \lceil \log n \rceil$ is time constructible

I have a question, I want to show, that: $$f(n) = n^2 \lceil \log n \rceil $$ is time-constructible. I have no idea how to do this. I know that $n^2$ is time-constructible and I know that $\log n$ ...
2
votes
0answers
78 views

Simple / Fast way to calculate the period of a arbitrary polynomial?

If I get a polynomial, say $u^5 + u^4 + u^2 + 1$, what is a simple and fast (by which I mean not to much to write) way to get the period of this term? Should I first test whether the polynomial is ...
0
votes
1answer
88 views

rule for adding nested sums with a common index

I've just started learning information theory and have stumbled upon a roadblock due to my apparently not understanding how summation works. I do not understand why this is true: $- ...
1
vote
1answer
69 views

generalization of base-n notation from naturals to fractions

not exactly sure how to best ask this. base-$n$ notation involves a series of digits written where each digit is a natural number less than $n$. is there some math/theory generalization of ...
2
votes
1answer
54 views

How to test the convexity of mutual information using leading principal minors?

I read from textbooks that the mutual information function $I(X;Y)$ is a concave function of $p(x)$ for fixed $p(y|x)$ and a convex function of $p(y|x)$ for fixed $p(x)$. I tried to test the ...
7
votes
2answers
288 views

Can the entropy of a random variable with countably many outcomes be infinite?

Consider a random variable $X$ taking values over $\mathbb{N}$. Let $\mathbb{P}(X = i) = p_i$ for $i \in \mathbb{N}$. The entropy of $X$ is defined by $$H(X) = \sum_i -p_i \log p_i.$$ Is it possible ...