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)

0
votes
0answers
111 views

Proof of Mrs. Gerber's Lemma Using Convexity and Jensen's Inequality

Can anyone give a proof of the Mrs. Gerber’s Lemma for the scalar case: $$ \ H^{-1}(H(Y|U)) \ge H^{-1}(H(X|U))*p $$ where $$ \ a*b = a(1-b) + b(1-a) $$ $$ \ X\ ,\ Y $$ are binary random ...
2
votes
0answers
37 views

Kullback–Leibler divergence with elements that are $0$

I have a problem that I need to calculate Kullback–Leibler divergence, but the problem is that I have some elements that are $0$. Is there a way that I'm able to deal with situations like that? I know ...
0
votes
3answers
109 views

Calculating probability in a Markov Chain

Suppose I have this Markov chain: And suppose that: $P_{AA} = 0.70$ $P_{AB} = 0.30$ $P_{BA} = 0.50$ $P_{BB} = 0.50$ I realize that $P_{AA} + P_{AB} = P_{BA} + P_{BB}$ but when I simulate I'm ...
4
votes
0answers
79 views

Dividing a deck of cards using only imagination

The idea came up from a discussion I had with my friends. Suppose we want to play a game using a deck of cards, and we can't use any physical materials. If we are intelligent enough, we can remember ...
1
vote
0answers
89 views

Continous wavelet transform and shannon Entropy.

Note: I have asked the same question on signal processing forum,but didn't get any answer. so it might be more like a math or physics question. Hope you don't consider it as cross-post. I am trying to ...
1
vote
0answers
40 views

Information Entropy Applied to Complexity Theory

I was just wondering whether or not information entropy has significant applications to complexity theory. I ask because of a simple example I thought of. It comes from a riddle. Suppose you had 8 ...
1
vote
1answer
48 views

locally linearize a CDF

I have a sequence of discrete CDF's that converge to continuous CDF. Assume we call it $F_n(x)$. If say at some point, say $R$, $F_n$ is differentiable, then we can write $F_n(R+\xi) \approx ...
0
votes
1answer
26 views

KL-divergence with zero probability?

Suppose $P(X=1)=P(X=2)=1/2$ and $P(Y=1)=1$. Then $$D(Y||X)=\log\left(\frac{1}{1/2}\right)+0\cdot\log\left(\frac{0}{1/2}\right).$$ If we consider ...
0
votes
1answer
36 views

information content of a quadratic surd

how much information is required to construct the equation: $$ X^2 - 2=0 \; ? $$ suppose, in a spirit of seasonal festivity, we squander a few further bits, and pamper ourselves with the additional ...
3
votes
2answers
130 views

Estimating the entropy

Given a discrete random variable $X$, I would like to estimate the entropy of $Y=f(X)$ by sampling. I can sample uniformly from $X$. The samples are just random vectors of length $n$ where the entries ...
2
votes
0answers
40 views

Upper bound of mutual information in a Markov chain

Consider binary random variables $X$ and $V$ with marginal distributions $p$ and $\pi$ respectively and also the conditional distribution $p(X=x\mid V=v)=q(x\mid v)$, where $x\in\{-b,b\}$ and ...
1
vote
0answers
93 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...
1
vote
1answer
28 views

Proving the monotonicity of a recurrence.

Define the following recurrence for $n = 1, 2, \cdots$ $T(n) = ( 1 - \operatorname{H}(\frac{1 - P^{\frac{1}{n}}}{2}))^n$ where $0 < P < 1$ is a constant, function $\operatorname{H}(\cdot)$ is ...
1
vote
0answers
60 views

Negative exponential/ exponential power distribution between 0 .0 and 1.0?

Note: I'm not very familiar with distribution and higher level math Heyho, I'm currently looking for a way to generate random values between 0.0 and 1.0 with an exponential power or negative ...
1
vote
0answers
31 views

How to define a utility of an information source?

This is a more specific (and, hopefully, clearer version of a previous question). The utility of discovering the value of a random variable $X$ can be defined to be its information content. When ...
2
votes
0answers
22 views

Fastest decaying probabilities with infinite entropy

A well known theorem of analysis is that there is no slowest rate of divergence of a series. "Completely irrelevantly," we know that there exists probabilities (e.g. $\mathtt{Const}/(n\log^2 ...
0
votes
0answers
35 views

How to define “compound entropy”

Entropy measures the "surprise" one experiences when uncovering a the actual value of a random variable as $$-\sum_i p_i \log_2 p_i$$ E.g., if we observe Red 8 ...
1
vote
1answer
68 views

Mutual information and additivity under independence?

So I've been trying to figure this out since I saw it quoted in a paper. Suppose $y$ and $z$ are two independent variables. Is it true then that $I(x;y) + I(x;z) \leq I(x:y,z)$? My intuition is that ...
3
votes
0answers
41 views

Prove that communication protocol complexity less than $n\epsilon$

Alice and Bob get as an input words $x$ and $y$, which consist of $0$ and $1$. Length of $x$ is $n$ and length of $y$ is $2n$. They want to know if the word $x$ is subword of word $y$. For example, ...
0
votes
0answers
32 views

Choice of $n$ channels - capacity

For example: If we have two channels whose input and output symbols do not intersect. One can easily show that the capacity of a new channel which uses only one at a given moment is $$C = ...
0
votes
1answer
72 views

Code for specific case [Information Theory]

I have a channel where the probability of sending a $0$ and receiving a $1$ is $P_e$, sending $0$ and receiving $0$ is $1-P_e$, sending $1$ receiving $0$ is $P_e$, sending $1$ receiving $1$ is ...
1
vote
0answers
24 views

Does this quantity have a meaning or relation to something else?

$X$ is a discrete random variable taking values in $\{0,1,2,3,\ldots\}$ with a probability mass function $p_X(n)$. Let $$U_k(X)=\sum_{n=k}^\infty\sqrt{np_X(n)p_X(n-k)}$$ where $k$ is a positive ...
0
votes
1answer
15 views

Question about flipping terms in matrix multiplication in proving that $h(N_n(\mu , K))=\frac{1}{2}\log(2 \pi n)^n |K|$

So in my book, it is written: Let $X_1,X_2,...,X_n$ have a multivariate normal distribution with mean $\mu$ and covariance matrix $K$ and $\textbf{X}=(X_1,X_2,...,X_n)$ The above isn't really ...
2
votes
0answers
72 views

Relation between entropy of variable and entropy of conditioned variable

Let $X$ be a discrete random variable, and let $E$ be an event on the same probability space as $X$. Let $X_E$ be $X$ conditioned on the event $E$. Is there a general relationship between the Shannon ...
0
votes
0answers
41 views

Generator Structure for Hamming and Dual code

To begin with i am not sure again if this is related to this particular forum ot it is an acceptable question.My question to find a (3,1) Hamming (repetition code) and its dual code and then draw the ...
1
vote
0answers
32 views

Independent transformation of probability measures

I have a pair of dependent random variable $(\theta, X)$ where $\theta\in K$ for a compact subset $K\subset\mathbb{R}$ and $X\in\mathbb{R}^d$ with marginals $P_{\theta}$ and $P_X$. I want to ...
2
votes
0answers
30 views

Is it true that $\sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}$?

Given $q \in \mathbb N$, $q\geq 2$ is it true that \begin{equation*} \sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}? \end{equation*} Here $H_q(x) = x\log _q(1/x) + (1-x)\log _q(1/(1-x))$ is the ...
1
vote
0answers
19 views

Orthogonality of parameter space

Folks, I have a basic information theory question. I am fitting a highly parameterized model to some data. In general: $$ y = \sum\limits_{i=1}^{13} \alpha_i X_i $$ Currently I use gradient descent ...
2
votes
0answers
102 views

Explanation of Radon-Nikodym derivates wrt to probabilities

I am currently working in communications, where a lot of work is done via probability calculations (densities and such). As I am not a mathematician, I do have a quite hard time understanding one ...
1
vote
0answers
67 views

what is relative entropy between to random binary string with length of $L_1$ & $L_2$?

I want calculate relative entropy between two strings of binary such as: $L_1:11000100011101001$ $L_2:00101110110111001$ It is primarily when the lengths of two strings is same and in general when ...
0
votes
1answer
26 views

$Y$ is a function of $X$: making an inference based on the markovity of $ X$

In the information theory book by Cover and Thomas it is written: if $X$ is markov and $Y$ is a function of $X$ then: ...
0
votes
2answers
49 views

Can infinite random sequences be asymptotically compressed?

A number $0.5<p<1$ is chosen at random and given to two people A and B whom are allowed to communicate before beeing separated. A is then given a sequence S of N random bits where each bit has ...
2
votes
1answer
63 views

Confused about notation: difference between $\prod_{i=1}^np(x_i)$ and $\prod_{i=1}^np(x)$

In my information theory book by Cover and Thomas, at the beginning of the channel coding theorem, it's written: "Each entry in this matrix" (the matrix of the randomly generated code) "is ...
2
votes
1answer
90 views

3-bit sensors — A question about Hamming distance in signals

I came across this question on Willy Wu's riddle site You have two 3-bit sensors, A and B, that measure the same thing, whatever it is -- temperature of the room, radioactivity levels, whatever. ...
2
votes
0answers
123 views

Information content of universal sentence

What is the information content of a sentence S like 'one has a successor'. To me, it looks like if we assume no a priori knowledge, both S and it's negation will have equal probablity 1/2. This is ...
0
votes
2answers
137 views

Hamming Code Error Detection

I am learning few things about hamming code and error detection so my question may sound stupid. So i know that lets i ahve (7,4) hamming code and i made transpose of parity check matrix H(t). Now say ...
1
vote
1answer
121 views

Bounding mutual information given ROC curve statistics

When evaluating a binary classifier, the basic data are as in this contingency table, where rows represent groundtruth value and columns represent the estimated value: $$ \begin{matrix} & + ...
3
votes
1answer
174 views

Solid Angle Calculation - Understanding a formula

I'm currently reading a paper and try to understand this one formula. The problem is: In an n dimensional space. A cone with half-angle $\theta$ is given (the top of the cone is in the origin). We are ...
0
votes
1answer
74 views

A quick chanllenge: height and weight probability problem

The average height and weight of a group of people is 175cm and 70kg; Find the upper bound of the portion of the people who are over 200cm and over 100kg. I thought about Markov inequality, but I ...
0
votes
0answers
80 views

Source Words & Huffman Codes

A source $S$ has source words $w_1, w_2, \ldots, w_n$, with probabilities $p_1 \geq p_2 \geq \ldots \geq p_n > 0$. Let $C$ be a binary Huffman code for $S$, and let $l$ be the length of the longest ...
1
vote
0answers
49 views

Rate Distortion function and similarity of probability distribution

I have been reading about the rate distortion function in which the fundamental limit of compression of a random variable $X$ to another random variable $Y$ taking values on smaller alphabet within ...
0
votes
1answer
89 views

Need help in understanding state transition diagram of a convolutional coder. How are the output bits calculated?

Have a look at the above figure. I am confused in how the output bits are calculated. e.g. according to my understanding a state transition from 00 to 10 (with input bit 1) should produce output 10 ...
0
votes
2answers
160 views

Cover information theory 7.21 tall, fat people

I am stuck on Thomas Cover information theory 2nd edition, problem 7.21 Fat, tall people. The problem is like following: 7.21 Tall, fat people. Suppose that the average height of people in a room is ...
6
votes
2answers
168 views

What is the connectivity between Boltzmann's entropy expression and Shannon's entropy expression?

What is the connection between Boltzmann's entropy expression and Shannon's entropy expression? Shannon's entropy expression: $$ S= -K\sum_{i=1}^np_i\log (p_i) $$
2
votes
0answers
128 views

How many code words if average code length equals entropy

I've been given a proof of the following: If $q\geq2$, then there is a source $S$ with $q$ symbols, and an instantaneous $r$-ary code $C$ satisfying $L(C)=H_r(S)$ if and only if $q\equiv 1 ...
0
votes
0answers
45 views

decreasing capacity of channel

I have a question regarding the capacity of a channel Consider a channel given by the transition probabilities $p(y|x)$ with capacity $C$. Now a friendly statistician offers to preprocess the output ...
2
votes
1answer
218 views

Conditional Independence and Mutual information

I have a question concerning conditional independence. According to wikipedia (yes, maybe not the best source) two random variables are conditionally independent given a third if $$p(x,y|z) = ...
1
vote
2answers
512 views

Fano's inequality explained intuitively?

I am now reading through a book to understand Fano's inequality, but I remember my professor explaining it in a certain way that made it seem so logical. I will go office hours as soon as possible, ...
0
votes
1answer
152 views

If $f_\theta=Uniform(\theta,\theta +1)$, a sufficient statistic for $\theta$ is… but why?

If $f_\theta=\mathrm{Uniform}(\theta,\theta +1)$, a sufficient statistic for $\theta$ is $$T(X_1,X_2,\dots,X_n)=(\max\lbrace X_1,X_2,\dots,X_n\rbrace,\min\lbrace X_1,X_2,\dots,X_n\rbrace).$$ Can ...
2
votes
1answer
247 views

Graph Entropy - What is it?

I am having trouble getting some intuition as to what graph entropy measures. The definition that I have is that given a graph $G$, $H(G) = \min_{X,Y}I(X ;Y)$, where $X$ is a uniformly random vertex ...