Questions in Information Theory

learn more… | top users | synonyms

-2
votes
0answers
23 views

Mutual information intuition

I was creating an example for a casual talk on Mutual Information. I considered a system of two coins, which with prob 1/2 are copies of each other, and with prob 1/2 are independent. Then ...
-4
votes
0answers
28 views

Entropy of sum of dependent random variables [on hold]

Can you help me find the entropy of the sum of two dependent random variables i.e find $h(X+Y)$ when X and Y are depenendent.
-1
votes
1answer
116 views

How can you prove that all halting probabilites are normal real numbers?

Wikipedia claims that any halting probability (Chaitin's constant) is a normal number. Since Chaitin's constant is uncomputble, how is a proof the the normalcy of the number possible? Computable ...
7
votes
3answers
202 views

Is there a generalization of information theory to polynomially knowable information?

I apologize, this is a bit of a "soft" question. Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating ...
6
votes
0answers
24 views

Different definitions of optimal decompressors

Let $B^{<\omega}$ be the set of finite binary strings. I will only consider functions from $B^{<\omega}$ to $B^{<\omega}$. I recall the definition of the algorithmic complexity of a string ...
9
votes
1answer
242 views

A converse to Fano's inequality ?

Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev: Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ ...
2
votes
1answer
65 views

Sufficient Statistics of $X$ from $Y$

I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger. In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they ...
1
vote
1answer
81 views

description of continuous probability distribution

The minimum description length of the realization of a random variable $x$ is given by the entropy of its probability mass function. Entropy of the representation of a (generic) probability ...
0
votes
0answers
54 views

deterministic randomness extractor and privacy

Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over the channel $P_{Y|X}$ which outputs $Y$ taking ...
6
votes
4answers
492 views

Expected empirical entropy

I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way: ...
4
votes
0answers
57 views

Inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...
5
votes
0answers
91 views

Largest size for randomness extractor

Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an ...
1
vote
1answer
113 views

Good resources to learn loopy belief propagation

What are some of the good references to understand loopy belief propagation and the need for it? I am looking for both theory and applications (for instance in coding/information and learning theory). ...
3
votes
2answers
147 views

The length of non perfect binary 1 error correcting codes

I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other ...
4
votes
0answers
115 views

Lovasz Theta as a short certificate

Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this ...
0
votes
1answer
70 views

grover's algorithm

Grover's algorithm searches an unstructured database (or an unordered list) with N entries. what type of data it works on? will it be possible to search data about some images that is stored in ...
6
votes
0answers
154 views

Physical Proof for P versus BPP

Lipton asks for a physical proof of $P\neq NP$. Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness? ...
0
votes
1answer
62 views

Mutual information and entropy to prove minimal Relevance Maximum Dependency

I'm reading through a paper on feature selection: Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance,and in-Redundancy but I'm unable to understand parts of the ...
4
votes
0answers
91 views

Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?

A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to ...
1
vote
1answer
61 views

Numeral system information density

What is an "informational density" and why numeral system with the base of e (2,71828...) has the maximum informational density? How do you calculate "informational density" of a given numeral system? ...
4
votes
2answers
92 views

Reference Request: Error correction code for a random projection

I'm interested in a variant of the Binary Channel, where the bits aren't flipped with some probability, but rather they are completely erased. Output words therefore vary in length. I'm quite sure ...
0
votes
1answer
335 views

Difference between self-information and entropy

I get a bit confused about different definitions of entropy and/or self-information. Entropy? $$ H(X) = - \sum_{x \in X} P_X(x) \cdot \log{\left(P_X(x)\right)} $$ Self-information? $$ I(x) = - ...
5
votes
0answers
108 views

Information theoretic characterization and consequences of reductions between computational problems

For two computational problems $A$ and $B$ in complexity class C (let say $NP$), the existence of a reduction $A <_m^L B$ computable in class (say $L$) implies that $A$ is not computationally ...
0
votes
0answers
131 views

Can the self-information be infinite?

I was wondering about the self-information, the information content . If I have data and I measure different words in it, their probability and take the average mean of that, what is the lowest and ...
7
votes
2answers
146 views

Smoothly leaking information over time

Say I have a one bit random variable $X \in \{0,1\}$, and let $n$ be a natural number. I want a sequence of random variables $0 = X_0, X_1, \ldots, X_n = X$ s.t. ...
5
votes
0answers
228 views

Explanation of polar decoding?

Polar decoding, according to Arikan's paper, can be decoded using a successive cancellation (SC) decoder, which is based on calculating the likelihood ratio, as seen in the image below. How can I ...
8
votes
3answers
433 views

Kolmogorov Complexity applications in Number Theory

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.) One of ...
1
vote
1answer
43 views

A theorem regarding statistically-hiding commitment schemes

Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends ...
3
votes
1answer
141 views

On the Shannon Capacity of Cycles

Let $\alpha(C_{n}^{\boxtimes k})$ be independence number of $k$-fold strong product of an $n$-vertex cycle graph $C_{n}$. $\forall n > 6$, is $\alpha(C_{n}^{\boxtimes (k+r)})^{\frac{1}{k+r}} \geq ...
5
votes
1answer
184 views

Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. — known problem?

Consider the following problem. Let $X$ and $Y$ be discrete random variables. The goal is to find a random variable $Z$ such that, informally, $I(Z;X)$ is high and $I(Z;Y)$ is low. More precisely, ...
3
votes
2answers
440 views

Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense ...
13
votes
0answers
139 views

Fano's inequality in the high error regime

Fano's inequality says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More ...
1
vote
1answer
187 views

How to choose a correct prior

Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability ...
7
votes
1answer
316 views

Can Polar Codes (or any other efficient codes) reach the second order capacity?

In channel coding, it is known (e.g. Yury Polyanskiy's thesis, and the arxiv article A Tight Upper Bound for the Third-Order Asymptotics of Discrete Memoryless Channels) that certain codes, for ...
2
votes
0answers
40 views

Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: ...
1
vote
0answers
53 views

Finding Most Compressible Vector Within Bounds?

Given large positive integers $m$ and $n$: Let $S$ be the set of integers $\{1,2,\dots,m\}$ We are given as input two vectors $L$ and $U$ both over $S^n$ such that: $$\bigwedge_{i=1}^{n}{L_i \le ...
7
votes
1answer
192 views

Conditional Kolmogorov Complexity: $K(y|x^*)$ vs $K(y|x)$

In "The Similarity Metric" Li, et al give the first definition of the normalized information distance as $\displaystyle d(x,y) = \frac{\max \left \{ K(x|y^*), K(y|x^*) \right \}}{\max \left \{ K(x), ...
0
votes
1answer
421 views

How can I prove that Hamming distance is upper bound for Levenshtein distance?

We have a spellchecker software. And one of it crucial parts is hypothesis generator which use Levenshtein distance as a measure of distance between words. The problem with Levenshtein distance is ...
3
votes
0answers
143 views

Is “normalized distance” (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?

In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the ...
6
votes
1answer
152 views

Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation ...
7
votes
2answers
158 views

Guessing a low entropy value in multiple attempts

Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice ...
7
votes
3answers
2k views

Are Shannon entropy and Boltzmann entropy mutually convertible?

Are Shannon entropy and Boltzmann entropy mutually convertible, much like mass and energy according to Einstein's formula?
10
votes
3answers
940 views

On the entropy of a sum

I am looking for a bound on the entropy $H(X+Y)$ of the sum of two independent discrete random variables $X$ and $Y$. Naturally, $$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$$ However, applied to the sum of ...
10
votes
1answer
244 views

The entropy of a noisy distribution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$ such that $$\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},$$ and $f$ is a ...
12
votes
1answer
460 views

The entropy of a convolution over the hypercube

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
8
votes
2answers
477 views

High probability events without low probability coordinates

Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small ...
4
votes
2answers
111 views

Gift bits when encoding a sequence of messages, how is that?

Recently a friend of mine asked a question I couldn't give immediate answer to. Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n * m $ ...
10
votes
0answers
116 views

Threshold for non-zero quantum capacity of depolarizing channels

In "Quantum-channel capacity of very noisy channels", DiVincenzo, Shor and Smolin showed that it is possible to perform quantum communication over depolarizing channels provided that the fidelity was ...
10
votes
2answers
312 views

Subset Numbering

Fix $k\ge5$. For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$. We would like this labelling to satisfy the following ...
5
votes
2answers
628 views

Transposition of any characters in Damerau–Levenshtein edit distance computation

Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters? Maybe some ...