Questions tagged [it.information-theory]

Questions in Information Theory

Filter by
Sorted by
Tagged with
-2
votes
0answers
40 views

What is the information content of unit tests?

Suppose I have a piece of code which solves a quadratic equation. I solve $x^2 -1 = 0$ using my code, and I verify that it spits out $x_0 = 1$, $x_1 = -1$. I've learned something from that, and ...
1
vote
0answers
96 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 ...
0
votes
0answers
139 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 ...
1
vote
0answers
89 views

On the equivalence of incompressibility and incompleteness in machine learning

Motivation: Motivated by the question of what problems are suitably addressed using methods in machine learning, I decided to formulate this general problem using Algorithmic Information Theory. My ...
10
votes
1answer
331 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,...
0
votes
1answer
98 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 ...
3
votes
1answer
112 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 "...
0
votes
0answers
10 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 ...
2
votes
1answer
146 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,...
2
votes
0answers
45 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 ...
1
vote
0answers
62 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:\...
1
vote
1answer
128 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 ...
1
vote
1answer
97 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)...
2
votes
1answer
96 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 ...
5
votes
1answer
152 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 ...
-1
votes
1answer
51 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 (...
0
votes
1answer
117 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 $\...
0
votes
1answer
99 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 ...
7
votes
1answer
191 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 ...
4
votes
0answers
81 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, ...
2
votes
0answers
102 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 ...
4
votes
1answer
397 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 $\...
1
vote
0answers
157 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 ...
1
vote
1answer
437 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 ...
2
votes
1answer
145 views

Why not include private randomness in internal communication information definition?

I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference. This isn't exactly a research question but I can't find a good place to ask it. Suppose ...
4
votes
0answers
105 views

Expected vs actual amount of information leaked by an $l$-bits message

Say we have a random variable $X$ that contains $k$ bits of information, and a message $M = f(X)$ ($M$ is deterministic given $X$) that is $l$ bits long, where $l<k$. This implies $H(X) = k$ and $...
1
vote
1answer
142 views

Uniqueness of the distribution maximizing the channel capacity

Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$....
6
votes
1answer
318 views

Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity. Background/Motivation: Coming ...
5
votes
1answer
183 views

Minimal information needed for determine some function

From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
10
votes
1answer
328 views

Is algorithmic information theory still evolving?

I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory. The field seems very interesting for me, but it seems everything is the field was done ...
3
votes
2answers
232 views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
1
vote
0answers
62 views

Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?

I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation ...
-1
votes
1answer
160 views

Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph

I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{...
6
votes
1answer
247 views

Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$. A bitstring $B$ is generated by drawing 0s and 1s ...
-1
votes
1answer
72 views

Relationship between worst case length of transcript and entropy of transcript

Consider the two party model of communication complexity where Alice and Bob are given inputs $X$ and $Y$ sampled from some distribution $\mu$, and their goal is to solve some problem $P$ (the details ...
6
votes
2answers
2k views

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission. Popular Bloom filter instead of marking just 1 hash ...
13
votes
1answer
1k views

Entropy and computational complexity

There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, ...
4
votes
1answer
106 views

Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise

There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we ...
4
votes
1answer
285 views

The Maxwell's Demon and Computer Science

What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I ...
0
votes
1answer
83 views

Error correction that adapts to different error rates

Say we have $N$ bits that we'd like to store in an $M$-bit error correcting code, where $M > N$. Given $\epsilon > 0$, as long as $N > N_0(\epsilon)$ we can recover the original bits as long ...
4
votes
1answer
677 views

Autoencoders and information compression

Disclaimer: I know very (very) little about deep nets, besides what an introductory course on machine learning would teach on neural networks, and skimming some paper abstracts and introductions. If ...
1
vote
0answers
53 views

Problem dependent lower bound for stochastic bandits with full information

Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
1
vote
0answers
56 views

Parametrically-relaxed Kolmogorov complexity

Consider the following problem: Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation. Output: The encoding of some kind of automaton (say, a Turing machine) which ...
4
votes
1answer
529 views

Relation between variance and mutual information

Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$ This bound may be ...
1
vote
0answers
132 views

Connection between diamond norm and output purity norm

Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register ...
-1
votes
1answer
100 views

Does a code need at least two symbols to be defined as a code? [closed]

I am wondering whether you could still call a code something that, if transmitting, only transmits one symbol. Or does the formal definition of code require 2 or more symbols? (and would the answer ...
2
votes
1answer
269 views

Entropy of a byte in a compression algorithm?

I have a (fixed, long) string of bytes that I want to compress, $C$. I use a typical (good) lossless compression algorithm on it, to generate a compressed string of bytes, $C^*$. Then I define a ...
1
vote
0answers
133 views

Information theoretic lower-bound on object graph serialization

This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding ...
1
vote
1answer
62 views

Families of LDPC codes with constant error fraction corrected

I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm. For example, I know that Sipser and Spielman proved that there is an ...
4
votes
1answer
390 views

Word length using entropy : Maximum entropy criteria

The question is based on research paper titled, Markovian language model of the DNA and its information content In the supplementary document, the Authors show how they determine the word length of ...