Tagged Questions

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.

2answers
49 views

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

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 ...
3answers
119 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 ...
3answers
275 views

Is it wrong to use Binary Vector data in Cosine Similarity?

I am doing Information Retrieval using Cosine Similarity. My data is binary vector. Since most of all reference I read is using non-binary vector (non-binary matrix) data, I am wondering if it is ...
0answers
35 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$ ...
1answer
70 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 ...
4answers
90 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 ...
3answers
130 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\}$: ...
1answer
95 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 ...
0answers
11 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 ...
1answer
17 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 ...
1answer
26 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 ...
1answer
21 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 ...
1answer
28 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?
4answers
118 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)$ Why ...
3answers
170 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 ...
0answers
28 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 ...
1answer
165 views

measure of information

We know that $l_i=\log \frac{1}{p_i}$ is the solution to the Shannon's source compression problem: $\arg \min_{\{l_i\}} \sum p_i l_i$ where the minimization is over all possible code length ...
1answer
28 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 ...
0answers
30 views

Why is K-L divergence defined as it is?

Why is the K-L divergence defined this way: if $P$ and $Q$ are probability measures over a set $X$, and $P$ is absolutely continuous with respect to $Q$, then the Kullback–Leibler divergence from ...
2answers
63 views

Given $\forall x \in \mathbb{R} \: h(p^t(x))=th(p(x))$, how to get $h(p(x)) \propto \ln p(x)$?

The whole question is in the title. $p(x)$ is a probability distribution, and $h$ is continuous and monotonic in $p(x)$. The purpose is to motivate that the "degree of surpise", or the "amount of ...
0answers
71 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 ...
0answers
29 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, ...
1answer
29 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: ...
1answer
27 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} ...
2answers
151 views

Are there simple examples of capacity-achieving block codes for discrete memoryless channels?

The title pretty much says it all, but I am particularly interested in the case where the number of input and output symbols are equal and the transition matrix defining the DMC is nondegenerate. I am ...
1answer
31 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 ...
1answer
33 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: ...
1answer
32 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) = ...
3answers
94 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 ...
1answer
32 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 ...
2answers
73 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 ...
1answer
81 views

Definition of entropy of an ergodic measure

I'm reading a paper in which it is stated that The entropy of an ergodic measure is defined as $$\lim_{n \to \infty} -\frac{1}{n} \sum_{|w|=n} \mu[w] \log \mu[w].\tag{1} \label{eq:1}$$ Here ...
3answers
182 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 ...
1answer
47 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) = ...
0answers
67 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 ...
2answers
231 views

Theoretical basis for overfitting

There are many examples in which making more "precise" predictions gives worse performance (e.g. Runge's phenomenon). My professor implied that there was a sound basis for choosing "simple" functions ...
1answer
55 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 ...
0answers
45 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 ...
0answers
91 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 ...
0answers
101 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 ...
0answers
62 views

Proof for the upper bound on entropy $H(S)$?

I was trying to prove the upper bound on $H(S)$ using the inequalities $\ln(x)\le(x-1)$ and $\ln(1/x)\ge(1-x)$ for independent and memory less source symbols $s_1,\dots,s_q$ . I am trying to prove ...
1answer
36 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 ...
1answer
140 views

A generalisation of a well known result in information theory

It is well known that Entropy is additive, and that it is the only sensible choice for measuring uncertainty if we want additivity to hold, i.e. $H(XY) = H(X)+H(Y)$ or more explicitly, if we have ...
1answer
56 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 ...
1answer
51 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 ...
1answer
56 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 ...
1answer
65 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. ...
1answer
28 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 ...
0answers
37 views

Multivariate Generalizations of the Mutual information

I'm interested in Multivariate generalizations of the Mutual information. So I'm just wondering if anyone can point me to a list of all such generalizations currently proposed. I've heard about the ...
1answer
85 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? =) Thank you!
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 77, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9141648411750793, "perplexity_flag": "middle"}