All Questions
Tagged with lower-bounds it.information-theory
5 questions
3
votes
2
answers
233
views
Lower bounding decoding error in a noisy adversarial channel
Problem description
Suppose we have a finite alphabet $\mathcal{X}$, where each letter $X \in \mathcal{X}$ indexes into some fixed set of distributions, $\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For ...
3
votes
0
answers
68
views
Does this information theoretical thought experiment have a name or corresponding area of research?
I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
3
votes
0
answers
299
views
Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric
Slight extension of cross posting from
https://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there)
The ...
1
vote
0
answers
62
views
Cramer Rao bound for relative estimation
I have an observed vector ${\bf y}$ from which I would like to estimate a parameter vector ${\bf c}$ (denote the estimate $\hat{{\bf c}}$).
A feature of our estimation problem is that the involved ...
0
votes
0
answers
52
views
Classifier-specific lower bounds on the misclassification rate in binary classification
Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on ...