Questions tagged [it.information-theory]

Questions in Information Theory

Filter by
Sorted by
Tagged with
1 vote
0 answers
47 views

Relation Between Different Definitions of Information Distance

I'm reading the fourth edition of An Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi. In Section 8.3 of the book, it introduces the concept of "information distance.&...
Ravi Deedwania's user avatar
1 vote
0 answers
39 views

Why the measure of information complexities for passive and active learning are increasing in research communities?

I am a PhD student working on the theory of active learning. Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
Ayoubayjx's user avatar
  • 122
0 votes
1 answer
57 views

Detecting Erroneous Corrections

A block code $C$, with minimum distance $d$ can be used to: Detect $d - 1$ errors Correct $\lfloor\frac{d - 1}{2}\rfloor$ errors However, the above usually assumes that the number of errors that are ...
Coziyu's user avatar
  • 1
1 vote
1 answer
90 views

Information Bottleneck - Calculating the Mutual information between the Labels and the Features [closed]

I am trying to understand the Nonlinear Information Bottlecneck paper along with their implementation, but I am confused as to what is actually being calculated in the Mutual information $(I(Y, M))$ ...
Liam F-A's user avatar
0 votes
0 answers
54 views

Does Co-occurrence Information Differ Qualitatively From Shannon and Algorithmic Information?

In Distributed Computation as Hierarchy Michael Manthey argues that co-occurrence of indistinguishables (critical for quantum theory) supplies spatial information that qualitatively differs from both ...
James Bowery's user avatar
0 votes
0 answers
32 views

What are the two quantities involved in the tradeoff for a language to follow Zipf's law?

In any human (and non-human) language the frequency distribution of words follows Zipf's law, which states that the slope of the linear regression for the frequency distribution of words vs the rank ...
Swike's user avatar
  • 101
0 votes
0 answers
50 views

Can information, eg. Shannon Entropy, be considered an absolute value?

This question is a distillation of my question here: How do I calculate the information content of a mass spectrum? Using a theoretical instrument that makes perfect measurements of fundamental ...
Ninja Chris's user avatar
1 vote
2 answers
216 views

How much information does it take to specify, not each member of a group, but any one member?

It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ ...
Charles's user avatar
  • 1,737
0 votes
0 answers
62 views

How do I calculate the information content of a mass spectrum?

Ions in a mass spectrum are represented using two independent values for the mass-to-charge ratio [m/z] of the ion and it's relative abundance. Here's an example for caffeine from HMDB: https://hmdb....
Ninja Chris's user avatar
0 votes
1 answer
47 views

Looking for information on Information Theory applied to image pixelation

I'm in seventh grade and am doing a science project about how age and gender affects people's ability to recognize pixelated images. For background research I have been reading about information ...
cs-researcher's user avatar
3 votes
0 answers
21 views

Modelling channels without specifying input alphabets

The standard mathematical model of a communication channel is that of a stochastic matrix $(C(x|a))_{a \in A, x \in X}$, where $A$ is the input alphabet and $X$ the output alphabet. This definition ...
Tobias Fritz's user avatar
1 vote
0 answers
85 views

Generalizing Fano's inequality

Fano's inequality says the following: Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
learning_tcs's user avatar
2 votes
0 answers
178 views

On the number of optimal prefix-free binary codes [closed]

Let $T$ be a text of length $L$ containing the symbols $$\mathcal{A}=\{a_1, a_2, \ldots, a_n\},$$ where each symbol appears at least once and no other symbol appears in $T$. Define the weights $$\...
Riccardo's user avatar
0 votes
0 answers
58 views

Is there a name/terminology for binary codes with evenly spaced number of ones?

I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
randomprime's user avatar
0 votes
1 answer
176 views

Information theoretic arguments for complexity

This Wikipedia article,Decision tree model, states that decision tree complexity lower bound $O(n \log_2 n)$ for sorting problem is information theoretic since any algorithm ( modeled as decision ...
Mohammad Al-Turkistany's user avatar
2 votes
0 answers
71 views

Origin of Berge's (Weak) Perfect Graph Conjecture

In an account of his thought process (refer p. 3) leading up to the perfect graph conjecture (which I'm preparing a seminar talk on), C. Berge states what seems to be a crucial step: (1) a graph $G$ ...
bolzep's user avatar
  • 21
0 votes
0 answers
61 views

Interesting statistical experiment concerning data compression

I want to present the following statistical experiment concerning data compression, on which I will ask you to predict the result obviously justifying the choice made. The statistical experiment is ...
Alix's user avatar
  • 1
3 votes
1 answer
166 views

Maximal uniquely decodable codes

This question is about the Kraft-McMillan inequality: If $w_1,\ldots,w_n$ are words of lengths $l_1,\ldots,l_n$ from an alphabet with $r$ letters, which form a uniquely decodable code, then $$ \sum_{i=...
aiz89's user avatar
  • 33
0 votes
1 answer
63 views

meaning of "algorithms that do not resample points" in the algorithms that do not resample points theorem

The No Free Lunch theorems for search and optimization demonstrate that for search/optimization problems in a limited search space, where the points being searched through are not resampled, the ...
Gianni Spear's user avatar
1 vote
1 answer
161 views

Can theoretical computer science be combined with mechanism and information design and applications in financial markets

I am considering to take a position as a phd student in a computer science department. I am a mathematician with a master degree in finance and my research interests are mainly focused in game theory. ...
Phd student's user avatar
4 votes
0 answers
243 views

Maximize the mutual information between 2 discrete random variables

I have two random variables $X$ and $Y$. $X$ follows Poisson-Binomial distribution with parameters $\{q_1, \ldots, q_k\}$. Thus, $X$ can take values in the set $\{0,1,\ldots,k\}$. $Y$ is a binary ...
wanderer's user avatar
2 votes
0 answers
86 views

Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
user2316602's user avatar
9 votes
0 answers
160 views

"Looking for help understanding a proof by Gossner (1998)."

Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
Nav89's user avatar
  • 209
1 vote
0 answers
113 views

Does any physical process constitute a "computation"? [closed]

I am trying to sharpen the convex hull of what seems like a (surprisingly) stubborn concept to enclose based on answers here, as well as conversations with others, around the nature of what actually ...
dnnct's user avatar
  • 27
5 votes
1 answer
234 views

Upper bound on the expected number of correct bits via a "lossy compression"

Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm ...
Marcel Dall'Agnol's user avatar
2 votes
2 answers
289 views

Information and Coding Theory Texts

I am coming from a pure mathematics (in analysis) background and am curious to learn some information and coding theory. I am after some recommendations on texts. Due to my personal background I am ...
Zeta-Squared's user avatar
4 votes
1 answer
207 views

Does this notion of entropy have a name?

Recently I stumbled upon the following notion of entropy which seems quite natural to me. I am looking for its "real" name and/or any references where it might come up. I tried searching ...
dkaeae's user avatar
  • 300
1 vote
0 answers
55 views

sophistication or logical depth to detect intelligent extra-terrestrial species

From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
dorikolmo's user avatar
1 vote
0 answers
125 views

Deterministic one way communication complexity for message with arbitrary length

Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message. I have been looking into ...
Koko Nanahji's user avatar
0 votes
0 answers
173 views

Error in entropy properties in Mathematical Theory of Cryptography by Claude E. Shannon

I am reading this classic paper by Claude E. Shannon and I think there may be a couple of errors in his description of the properties of Entropy/Uncertainty. The screenshot shown at the bottom of this ...
nuggimane's user avatar
10 votes
1 answer
443 views

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner. We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
R B's user avatar
  • 9,438
0 votes
1 answer
114 views

Why isn’t information-probability relationship linear? [closed]

I am completely new to information theory. I was learning about information content but couldn’t make sense of why the relationship between information content and probability isn’t linear? And why it ...
Aether's user avatar
  • 133
3 votes
1 answer
188 views

Converting a Bernoulli to a Gaussian

It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a "...
Clement C.'s user avatar
  • 4,451
0 votes
0 answers
15 views

Capacity of spike-based neuronal code

Assume that a neuronal population $A$ is connected to a neuronal population $B$ by a bunch of synapses - one-directional channels that propagate spikes. For simplicity assume that the current ...
Aleksejs Fomins's user avatar
4 votes
1 answer
196 views

Generating $k$ random bits from a pdf with entropy $H(p) = k$

All the sources online say that, intuitively, a distribution with entropy $k$ has $k$ bits of pure randomness in it. So can we formalize this as follows? Suppose I can only sample from my distribution,...
Karagounis Z's user avatar
2 votes
0 answers
170 views

Damerau–Levenshtein distance with transposition of non-adjacent characters?

Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
Ted's user avatar
  • 21
1 vote
0 answers
84 views

Difference between a lossy encoder and a noisy channel in Information Theory

$S \to X \to Y \to \hat{S}$ $\text{source} \to \text{input} \to \text{output} \to \text{target}$ In information theory introductory books, an encoder is usually defined as a deterministic function $f:\...
Fred Guth's user avatar
  • 143
2 votes
1 answer
199 views

Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures

I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter ...
Daniel Severo's user avatar
1 vote
1 answer
131 views

Data processing inequality for interaction information

The interaction information is defined as $I(X;Y)-I(X;Y|Z)$. Let $Z-(X, Y) -(X', Y')$ be a Markov chain. Is there an inequality similar to the data processing inequality, relating $I(X';Y')-I(X';Y'|Z)...
Dina Abdelhadi's user avatar
3 votes
1 answer
190 views

Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
Fred Guth's user avatar
  • 143
5 votes
1 answer
240 views

Kolmogorov Complexity of a Decidable Language

The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable ...
Raphael Augusto's user avatar
-1 votes
1 answer
66 views

Notation in proof for Asymptotic Equipartition Property

In the following lecture notes chapter 3, page 12-13, they state the following We begin by introducting some important notation: - For a set $\mathcal{S},|\mathcal{S}|$ denotes its cardinality (...
sn3jd3r's user avatar
  • 133
0 votes
1 answer
153 views

Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

In this paper by Tishby, Pereira and Bialek they mention on page 4 in the Relevant quantization chapter the setting is the following; Given some signal space $X \sim p(x)$ and a quantized codebook $\...
sn3jd3r's user avatar
  • 133
0 votes
1 answer
118 views

Notation of sequences in rate distortion theory

I have been reading whatever sources I could get my hands on today, regarding this problem. Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas ...
sn3jd3r's user avatar
  • 133
7 votes
1 answer
249 views

Expected vs worst-case communication complexity

In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an $n$-bit string as input; denoted by $X$ for Alice's input, and $Y$ for Bob's input. They need to ...
cstheory_student1's user avatar
4 votes
0 answers
104 views

Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience. So, Iet $X = (X,d)$ be a Polish space, ...
dohmatob's user avatar
  • 291
2 votes
0 answers
109 views

Representing data with Shannon entropy predicted bits

Let us assume a file based on a character set where each character has equal probability of occurance. This will result in the maximum entropy for that character set. On calculating the entropy, let ...
Paddy's user avatar
  • 121
4 votes
1 answer
431 views

Maximization of Mutual Information

Let $X\in\{0,1\}^d$ be a Boolean vector and $Y, Z\in\{0,1\}$ are Boolean variables. Assume that there is a joint distribution $\mathcal{D}$ over $Y, Z$ and we'd like to find a joint distribution $\...
Han Zhao's user avatar
1 vote
0 answers
366 views

Minimum number of hours of speech needed to train a neural net to recognize speech [closed]

From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
Lars Ericson's user avatar
1 vote
1 answer
1k views

Chain rule for KL divergence

Is there an inequality to relate the KL divergence of two joint distribution and the sum of the KL divergence of their marginals? Or in particular, is there a proof or a counter example for the ...
Dawei Huang's user avatar

1
2 3 4 5