Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [information-theory]

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.

-1
votes
0answers
12 views

Difference Entropy Output and Input [on hold]

In a ternary channel with same probabilities for all inputs. I have H(X) entrance entropy and H(Y) output entropy. What does the difference of these 2 Entropy tell me?
-2
votes
0answers
17 views

Majority voting 9 Bits Error probability

i have 1 Bit that will send 9 times. Each bit has an error probabiltiy of 1/3. The received Bits will be interpreted with a majority voting. Do anyone have an idea how i do check the probability ...
2
votes
1answer
43 views

Expected Hamming distance between typical strings

Let $S$ be the set of bitstrings of length $n$ with $pn$ ones and $(1-p)n$ zeros, for some $p \in [0,1]$. I want to show that, for large $n$, if one uniformly samples pairs from $(s,s') \in S^2$, ...
0
votes
0answers
24 views

Tricky information inequality $I(X;Z) \geq H(T)$

I am wondering whether $I(X; Z) \geq H(T)$ when the following conditions hold: $H(T | X) = H(T)$ $H(T | Y) = H(T)$ $H(T | X, Y) = 0$ $H(Y | Z) = H(T | Z) = 0$ $X, Y, Z, T$ are discrete. I know first ...
0
votes
0answers
17 views

Conditional Entropy sum of 2 dice rolls and even/uneven

So i have the sum of the 2 dice rolls with X and that the sum is even/uneven with Y out of 0 or 1 Probabilities: (2=1/36) (3=2/36) (4=3/36) (5=4/36) (6=5/36) (7=6/36) (8=5/36) (9=4/36) (1=3/36) (11=2/...
0
votes
0answers
22 views

understanding the conditional entropy in the case of having uniform distribution?

Would you please help me to understand the conditional entropy in this example which I got stuck in? The example Considers 4 uniformly popular binary vectors, for example; {f1,f2,f3,f4} each with ...
0
votes
0answers
26 views

What is your opinion on David Ellerman's Partition Logic and his distinction based view of Entropy? [on hold]

I have been skimming through David Ellerman's work on Partition Logic and Information theory. What exactly is the difference between dits and bits in his treatment of information theory? What exactly ...
1
vote
1answer
28 views

Probability conditional on entry of exchangeable random vector: does the index matter?

I have a random varbiable $Y\in\{0,1\}$, which is dependent on a random vector $X \in \{0,1\}^n$. Therebey, the entries in $X$ are exchangeable. That is, $P(X_i=1)=P(X_j=1)$. I want to compute/...
1
vote
1answer
22 views

Similarness of random samples

Say, I have a set of random variables, $\{\vec{x}_1,...,\vec{x}_N\}$, which were all drawn from the same probability distribution, $p(\vec{x})$. I do not know the form of the $p(\vec{x})$. I am given ...
0
votes
0answers
17 views

Probability mass of a source of L symbols

I am trying to get a list of probabilities to test a function that computes the mutual information of an information channel. I have this function in Matlab ...
0
votes
0answers
32 views

Maximizing over $\alpha$ gives $2^C=2^{c_1}+2^{c_2}$?

I was reading about the derivation of the channel capacity in the two simetric binary channel when they are used in parallel. I don't understand how you get the equality from this: Then $$C=\max_{p(...
1
vote
3answers
70 views

Understand better the entropy of Shannon

I'm not really sure what the entropy represent. In wikipedia, they say that the entropy is the quantity of information available and is defined as $\mathbb E[\log_b P(X)]$ where $P(X)$ is the mass ...
0
votes
0answers
25 views

MIMO Capacity grows linearly with number of antennas

I read the following statement from the paper "EVALUATION OF MIMO SYSTEM CAPACITY OVER RAYLEIGH FADING CHANNEL", where it says: MIMO Channel Capacity grows linearly for a case of $N_r=N_t$ rather ...
4
votes
1answer
77 views

In Huffman coding, how do I choose the frequency to get the maximum average bit length?

First I want to give you a little summary about the Huffmann code to avoid misunderstandings. Summary begins So we have an alphabet $A$ with $|A| > 1 $. For example $A$= {$a,b,c,d,e$}. Now we ...
0
votes
1answer
14 views

upper bound on cross entropy or relative entropy

Am looking for upper bounds for relative-entropy or cross-entropy for non-gaussian case . All I am aware of is bounds for entropy based on determinant of covariance matrix. What about for relative ...
0
votes
1answer
52 views

Modulo addition of independent random variables

Let $X,Y,W$ be discrete random variables with support set $\{0,1,\ldots,M-1 \}$. Assume that $X$ and $Y$ are independent with respect to $W$ and $H(X)<H(Y)<\log M$ and $H(W)<\log M$. Let $+$...
0
votes
1answer
34 views

Does Minimum Description Length apply for noisy communication?

Rissanen's Minimum Description Length principle shows that, for a set alphabet $A$ of $n$ symbols with probabilities $\{p_1, ..., p_n\}$, one can construct a set of $n$ prefix binary codewords, using ...
0
votes
1answer
23 views

How can I understand this sentence in Shannon's “Mathematical theory of communication”

If the number of messages in the set is finite then this number or any monotonic function of this number can be regarded as a measure of the information produced when one message is chosen from the ...
3
votes
0answers
59 views

Random mapping and entropy ordering

Let $X_1,X_2$ be discrete random variables such that $H(X_1)<H(X_2)$ where $H()$ is the entropy. We know that for any random mapping $T$ which is invertible ($T$ is a function of $\omega$ and $X$, ...
0
votes
1answer
34 views

Entropy of $\max(0, \mathrm{uniform}(-1, 1))$

I'm trying to figure out how to deal with distributions that are mixtures of discrete and continuous. A simple example is max(0, uniform(-1, 1)) -- draw a (real) ...
0
votes
1answer
20 views

Information content of a categorical variable

The information content of an outcome of a variable is $h(x_i)=-\log_2 (p(x_i))$. I am interested in using this concept to provide more insight on the differences in the distributions of two ...
0
votes
0answers
27 views

question about linear algebra in information theory

im learning about hamming code there is equation $x=uG$ where G is generator matrix i need to find generator matrix from the codeword x and u is message bit suppose code word is $(100110)=(100)G$ ...
0
votes
0answers
37 views

Can conditioning increase Entropy?

Is there any circumstance in which conditioning can increase entropy? Can $H(X|Y) > H(X)$ ?
0
votes
0answers
21 views

Service queue with expiration

from an Internet of Things setting we have the following question. There is an information service. It has a contract with a customer that it would provide information which is at most N seconds old (...
1
vote
1answer
33 views

Operational Meaning of Relative Entropy

Is there an operational meaning to understand the non-negativity of relative entropy between two probability distributions? I understand the mathematical argument/proof. But I want to know if there is ...
1
vote
0answers
17 views

how to compute how many bits of information about a given sentense?

I am learning Stanford CS224N: natural language processing with Deep Learning. the professor said something and claim that what he said was about 200 bits of information. how to compute how many ...
1
vote
1answer
21 views

How to construct a Huffman tree.

I was trying to make a D-ary Huffman tree for the probabilities $(\frac{1}{21},\frac{2}{21},\frac{3}{21},\frac{4}{21},\frac{5}{21},\frac{6}{21})$ in the case of the threnary tree, grouping the tree ...
0
votes
0answers
8 views

Entropy of a race and information of a message [duplicate]

Having 17 people running a race, the 1st runner have 3/4 probability of winning and all the others have (each) 1/64. The entropy of the marathon is 1.811bits.Knowing that the 1st runner didn't won ...
0
votes
1answer
19 views

Notation for this quaternary linear code

I've been reading about self dual codes, and the literature says that there is a quaternary self dual code $$i_2 \otimes \mathbb{F}_4$$where $i_2 = {\{00,11}\}$ is a binary self dual code and $\mathbb{...
1
vote
1answer
53 views

Green-eye paradox (an information paradox) or the Dragon puzzle

I was trying to solve this puzzle but I believe I have run into a paradox.Found the puzzle in https://io9.gizmodo.com/can-you-solve-the-hardest-logic-puzzle-in-the-world-1642492269 "There are 100 ...
0
votes
1answer
24 views

Lower bound for joint entropy

Let $ H(X_{1})\leqslant H(X_{2})\leqslant,...,\leqslant H(X_{n})$ I seem to have a problem of finding a lower bond of joint entropy. I proved that upper bound using the chain rule and the fact that ...
1
vote
1answer
21 views

Relationship between differential entropy and quantized entropy

I am reading Elements of Information Theory (2nd Ed.) by Cover. I have something that I couldn't figure out. On page 248, theorem 8.3.1 If the density f(x) of the random variable X is Riemann ...
0
votes
1answer
32 views

Calculate the Mutual Information between $X$ and $X^2$, where $X$ is uniformly distributed.

Let us consider two random variables, $X$ and $Y$. Let $X$ be uniformly distributed in $[-1,1]$ and let $Y=X^{2}$. Is it possible to calculate the Mutual Information between them? E what is the ...
0
votes
0answers
21 views

Is the Shannon capacity for a baseband signal different than its modulated counterpart?

I understand the Shannon-Hartley theorem to define channel capacity $C$ as $$C=W\log\left(1+\frac{S}{N_0 W}\right)$$ where $W$ is the channel bandwidth, $S$ is the signal power, and $N_0$ is the ...
0
votes
0answers
28 views

Measuring information preserved by a slowly varying function

Let $\phi$ be a continuous and injective mapping $\phi: \mathbb{R} \to \mathbb{R}$. Intuitively, this is an information preserving map, but the information is not `stably' preserved. This is because $\...
0
votes
0answers
14 views

finding the overhead and distance of an unknown code based on message making algorithm

For an information word M with m bits that is coded as following: M Is coded into a word A using an unknown code that allows detection of not more than one error. The code word is the word obtained ...
0
votes
0answers
18 views

Conditions for physical degraded Binary asymmetric broadcast channel

A broadcast channel is composed of a binary input and two separate binary outputs, one for each of two receivers. The binary channels for the two receivers have the following cross-over probabilities. ...
7
votes
2answers
116 views

Searching for tagged balls under constraints

(This is a modification of this problem.) You have $k$ white balls and $k$ black balls, and know that exactly one of each color is radioactive. You can place any number of balls of your choosing in ...
0
votes
1answer
28 views

Minimum Entropy for a given mean

For a given mean $1/\lambda$, find the minimum entropy among distributions that are continuous with support $\mathbb{R}^{+}\cup \{0\}$. If we were looking for a maximum, the answer was exponential ...
0
votes
1answer
28 views

Looking for the name of a theorem relating Shannon entropy to largest probability

Based on the definition of the Shannon entropy, $$ H = \sum_x p(x) \log \frac{1}{p(x)} $$ for a probability distribution $p$ defined on a discrete set of outcomes $x$, one can bound the probability ...
0
votes
2answers
26 views

Conditional entropy on race outcome

The problem is: 9 guys are racing. The favorite has a probability of 3/4 to win the race. Each other competitor has an equal chance to win. If it becomes known that the favorite did not win the ...
0
votes
0answers
40 views

Entropy relative to convolution with a Gaussian

Denote by $H(\cdot||\cdot)$ the relative entropy (also known as KL divergence). If $X$ is a centered random variable and $G_{\sigma^2} \sim \mathcal{N}(0,\sigma^2)$ is a normal random variable with ...
0
votes
1answer
37 views

conditional entropy inequality

Does the "information can't hurt" inequality for conditional entropy $H(X)\ge H(X\mid Y)$ extend to $H(X\mid Y)\ge H(X\mid Y,Z)$?
0
votes
1answer
36 views

Understanding when the entropy $H(f(X))=0$?

I've been trying to understand this for a while now, but can't seem to get it. This question only refers to a discrete random variable X and some function $f$ in $\mathbb{R}$. I've been told that $f(X)...
1
vote
2answers
57 views

Lower bound on the probability that a random variable is greater than half of its mean

Consider a random variable $X$ that takes values between $-1$ and $1$. What is a non-trivial lower bound on the probability that the outcome of $X$ is greater than half of its mean? EDIT: I am ...
0
votes
0answers
37 views

Connection between two definitions of Fisher information.

In statistics, the Fisher information is commonly defined as the covariance matrix$\operatorname{Cov}_\theta X$ of the random vector $X$, with $X_i = \frac{\partial}{\partial \theta_i } \left(\log(f(X,...
0
votes
2answers
42 views

Entropy and its relation to proportion

I have that entropy is $$ H(X) = - \sum_i^m p_i \log_2 (p_i) $$ And my understanding is that for a fair coin toss entropy would be maximised as there's the greatest amount of uncertainty for a ...
0
votes
1answer
25 views

Rate of systematic code that is a combination of two codes over the same information symbols.

Let $I_k$ be the systematic columns and let two codes be defined over the same systematic columns $I_k$ as below. Let $[n_1,k]$ be the first linear systematic code with rate $\frac{k}{n_1} \leq r_1$,...
0
votes
0answers
13 views

Is the mutual information jointly concave for multiple access channels:

We have a discrete memoryless multiple access channel: $X\times Y\rightarrow Z$, where the channel is $p(z|x,y)$. The mutual information $I(X,Y;Z)=\sum_{x,y,z}p(x)p(y)p(z|x,y)\{\log p(z|x,y)-\log[\...
1
vote
1answer
64 views

Is it known the value of $\sum\limits_{n=1}^{\infty}\frac{\log(n)}{ n^2}$?

In my information theory course, we have been asked to find the entropy of a particular distribution in $\mathbb{N}$. In order to do so, I have come to the following integral $$\sum\limits_{n=1}^{\...