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
1answer
32 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
61 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
32 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
26 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
82 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
44 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
38 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
16 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
82 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
44 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
34 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
34 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
114 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
74 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
51 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
64 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
95 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
130 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
164 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
123 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
185 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
81 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
50 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
100 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
164 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
190 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
133 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
47 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
257 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
596 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
188 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
281 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 ...
3
votes
2answers
186 views

Markov chains for beginners, how to think about them?

So this is what my book states: Random variables $X,Y, and Z$ are said to form a Markov chain in that order denoted $X\rightarrow Y \rightarrow Z$ if and only if: $p(x,y,z)=p(x)p(y|x)p(z|y) $ ...
2
votes
2answers
291 views

Random process, stochastic process explained intuitively?

So I've read the definitions online and this is what I understood. $X(t)$ is a random process for $t>0$ and we can think of it as being a random variable at any given time $t=t_0$. For example, ...
1
vote
1answer
148 views

$I(X;Y;Z)$ and $I(X,Y;Z)$?

Anyone can conceptually explain what the difference is between $I(X;Y;Z)$ and $I(X,Y;Z)$? where $I(X;Y;Z)=I(X;Z)+I(Y;Z/X)$ Basically, what the semicolon and coma mean in mutual information? In ...
1
vote
2answers
286 views

“by definition A and B R.V are independent means that: $p(A∪B)=p(A)+p(B)$ right?” No, absolutely not right.

Can someone please explain why? Isn't $p(a,b)=p(a)*p(b) $ equivalent to $p(A∪B)=p(A)+p(B)$? If not can you please give a counterexample or something? Thanks a lot!
2
votes
1answer
98 views

I.I.D what does this stand for?

So almost everywhere in the book it's written "random variables are IID", what does this mean? I think it means independent and identically distributed but not sure. So by definition A and B R.V are ...
2
votes
1answer
36 views

Error correcting binary partition

Let's say I have a collection of $2^n$ labeled objects, and I want to find one of them. If I can ask yes-no questions about it, binary partition would immediatly lead us to the desired object in $n$ ...
1
vote
1answer
102 views

Is there a way to mathematically describe “surprise”?

Let's say that there are ten people entered into a random drawing, the winner gets some large prize. If I were one of those ten people, and I were to win, then I would be pleasantly surprised. If ...
1
vote
1answer
37 views

Is $p(X \in A|\frac{Y+Z}{2}) = p(X \in A|Y,Z)?$

Let $X,Y, and \space Z$ be random variables. Let $A$ be a subset of $U$ such that $p(X \in U)=1$ Is $p(X \in A|\frac{Y+Z}{2}) = p(X \in A|Y,Z)?$ Do these two expressions represent the same thing? ...
1
vote
1answer
33 views

Show that entropy $(p1,…,pi,…,pj,…,pm)$, < entropy $(p1,…, (pi+pj)/2 ,…, (pi+pj)/2 ,…,pm)$.

Show that the entropy of the probability distribution, $(p1,...,pi,...,pj,...,pm)$, is less than the entropy of the distribution $(p1,..., (pi+pj)/2 ,..., (pi+pj)/2 ,...,pm)$. I don't understand what ...
2
votes
1answer
98 views

Notion of Relative Entropy

I do not understand the notion of relative entropy. Relative Entropy. $D_{KL}(P||Q) = \sum_{i}^{}P(i)\log \frac{P(i)}{Q(i)}$. I try to get some intuition why it looks the way it looks. I see that it ...
5
votes
1answer
146 views

A tight lower bound for the entropy of the XOR of two random variables

Let $U$ be the uniform random variable over $n$-bit binary strings, and let $X$ be another random variable that is dependent on $U$ and ranges over $n$-bit binary strings. Assuming $I(X;U) \le ...
5
votes
1answer
135 views

Card drawing algorithm

I want to know whether there is an algorithm for randomly and securely drawing cards from a deck. I was thinking about a way to play deck-based games online with no trusted party and no way to cheat. ...