6

Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively. Consider the extreme case of $\mu = +1$. In this case $Y = +1$ for sure, and you are outputting a sample from $P$, which means that $P$ should be an $\mathcal{N}(\nu, 1)$ ...


5

The relevance of Shannon entropy is to repeated sampling: Given $n$ independent samples from a source with binary Shannon Entropy $k$, you can extract $nk(1+o(1)$ i.i.d. uniform bits as $n$ tends to infinity with probability tending to 1. This follows e.g. from the Keane-Smorodinsky [1] finitary isomorphism theorem. See also [2]-[5] below. [1] M. Keane and M....


5

Maybe not so math oriented but with math rigor: Elements of Information Theory by Thomas M. Cover, Joy A. Thomas Essential Coding Theory by Venkatesan Guruswami, Atri Rudra and Madhu Sudan


4

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$. We can at least prove that if $x$ is chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case ...


3

Let $f(n,s)$ denote the answer. Claim: We have $f(n,s) = \frac{n}{2}+\Theta(\sqrt{sn})$ for any fixed $s$ as $n \to \infty$. More precisely, $\lim_{n \to \infty} \frac{f(n,s)-\frac{n}{2}}{\sqrt{n}} = \Theta(\sqrt{s})$ for $s \ge 1$. Proof: For the lower bound, have the compressor divide into $s$ (nearly) equal pieces and output the (string of length $s$ ...


3

Both texts in the other answer are great texts, and the Guruswami, Rudra, Sudan book is more based in the TCS approach to coding theory, which may be relevant to the potential reader. The books below have been split into the "mainly information theory" and "mainly coding theory" subsets. Information Theory: For mathematical rigour, the ...


1

This is called "output entropy". Suppose you have a communications channel that takes a string and then outputs a random string within a relative $\delta$ radius of it. If you use the input distribution $X$ for communicating over this channel, the entropy of the output distribution would be the quantity you are after.


Only top voted, non community-wiki answers of a minimum length are eligible