Questions in Information Theory
-1
votes
0answers
10 views
Information content associated with an outcome [migrated]
I have the following exam question for a multimedia exam in college:
Assume that you roll a single ordinary six-sided die twice, and
observe that the second number rolled is greater than the ...
12
votes
0answers
79 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
166 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
177 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 ...
0
votes
0answers
35 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
44 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 ...
6
votes
1answer
146 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
263 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
74 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 ...
3
votes
0answers
90 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
120 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 ...
6
votes
3answers
1k 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?
8
votes
3answers
462 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
218 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
373 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
420 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
105 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 $ ...
9
votes
0answers
99 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
276 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
394 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 ...
10
votes
1answer
252 views
Distinguishing between $N$ quantum states
Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$?
This problem can be ...
14
votes
1answer
387 views
Bloom filter hashes: more or bigger?
In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as ...
3
votes
0answers
185 views
Efficient synchronization of two instances of an ordered list
What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move ...
5
votes
1answer
124 views
Minimal bandwidth required to synchronize two sets of values
We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the ...
5
votes
0answers
202 views
Applications of Theoretical Computer Science in Information Theory
Inspired by this question:
Information Theory used to prove neat combinatorial statements?
Are there any nice applications of theoretical computer science in information theory (the other way has ...
0
votes
0answers
114 views
norms of compressible and incompressible vector
Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$
I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case ...
15
votes
0answers
300 views
Looking for an operator on polynomials
I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc).
I wonder ...
1
vote
0answers
166 views
Information channel with symmetric channel matrix
It took me a while to figure out that a "symmetric channel" does not mean a channel with a symmetric channel matrix. (Rather, "symmetric channel" means that the rows of the matrix are all permutations ...
1
vote
2answers
495 views
Arithmetic coding, the termination symbol, and the empty string
Suppose the source alphabet is $a, b, c$ with $a$ as the termination symbol and so the unit interval is correspondingly divided as
$[0, P(a), P(a)+P(b), 1]$.
Strings consisting of a bunch of $b$'s ...
1
vote
1answer
112 views
Landauer's principle internals - how it works
I attached a picture, where the energy dissipation (entropy increase) on information erasure is explained. Is the explanation correct?
"RESTORE TO ONE" - is it correct to identify the operation as ...
0
votes
0answers
98 views
Tractability of mutual information-augmented ensemble classification algorithms
I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an ...
4
votes
2answers
212 views
Combinations with symbols
Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than ...
-4
votes
2answers
351 views
Covering Codes with Game Theory Application
Here is a question I came up with and i have been pondering for a while. It relates to covering codes, a subset of coding theory. I could not come up with an adequate solution, so here I am, asking ...
9
votes
4answers
391 views
Relation between computational complexity and information
I work in a computational neuroscience lab that quantifies the mutual information between pairs or groups of neurons. Recently, the boss his shifted focus to measuring the "complexity of neural ...
14
votes
0answers
185 views
Mutual information vs. Product sets
Suppose we have two dependent random variables $X$ and $Y$, each of which is uniform over $\{0,1\}^n$, such that their mutual information $I(X;Y)$ is small, say, at most $\sqrt{n}$. Does this imply ...
8
votes
1answer
259 views
Determine the minimum number of coin-weighings
In the paper On two problems of information theory, Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.
...
7
votes
1answer
236 views
Applications of Spectral Graph Theory in Information and Coding Theory
I wanted to find out what are some application of SGT in the area of information and coding theory and maybe communications. The most related that comes to mind is the work on Expander Codes
Michael ...
18
votes
4answers
423 views
Efficiently computable variants of Kolmogorov complexity
Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:
It corresponds to an intuition of giving strings with patters or ...
5
votes
1answer
1k views
Comparing Shannon-Fano and Shannon coding
I am interested in a few algorithms for creating prefix codes:
Shannon coding: we take $l_i=\lceil -\log p_i\rceil$.
Shannon-Fano coding: list probabilities in decreasing order and then split them ...
5
votes
0answers
118 views
Channel coding results using Kolmogorov complexity
Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov ...
0
votes
0answers
69 views
High Dimensional Volume (HDV) estimator for Entropy estimation
I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data ...
5
votes
1answer
123 views
Long-term data encoding, Phoenix Mars DVD
While browsing I've stumbled over the Phoenix Mars lander
http://en.wikipedia.org/wiki/Phoenix_(spacecraft)#Phoenix_DVD
and it says that the craft contains a DVD with all kinds of information on it.
...
1
vote
0answers
93 views
Information theory and Tsfasman-Manin's problem
Yuri Manin recently posted an interesting paper on computability of boundary regions of distance-rate trade-offs for error correction codes.
http://arxiv.org/PS_cache/arxiv/pdf/1107/1107.4246v1.pdf
I ...
11
votes
5answers
1k views
Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?
The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.
In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it ...
8
votes
4answers
492 views
Surveys on Network Coding
I want to start learning about Network Coding:
http://en.wikipedia.org/wiki/Network_coding
Do you know any good survey (e.g. from IEEE Surveys and Tutorials) on the above subjects. I found some ...
3
votes
1answer
138 views
Relation between Code Length and Symbol Weight in a Huffman Code
I'm not sure if I should ask this here or over at StackOverflow (sorry if this is not the right place).
I'm constructing a Huffman code for a series of symbols with associated weights. I have a list ...
8
votes
0answers
586 views
A simple(?) funny combinatorial problem!
Let we fix $0<E<1$ and an integer $t>0$.
for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\sum_{i\in [n]} c_i \geq E \times n$
$A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i ...
8
votes
5answers
631 views
Which is the limit of lossless compression data? (if there exists such a limit)
Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression.
So far, the only source I ...
5
votes
1answer
184 views
Quantum Channel Decoding
Let a quantum channel $\Phi(\cdot)$ between two Hilbert spaces $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$.
What is the quantum channel $\Phi_{inv}(\cdot)$ that best reverses $\Phi(\cdot)$ ?
$\forall ...
8
votes
0answers
198 views
Approximation of Quantum Channels
Background:
In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels:
A quantum channel is a linear, ...
