10
$\begingroup$

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,1/2]$ that they can use for choosing $X$ and estimating $x$.

Subtractive dithering is an algorithm that sends $$X = \begin{cases} 1 & \mbox{if $x+h\ge 1/2$}\\ 0 & \mbox{otherwise} \end{cases}. $$ In turn, the subtractive receiver estimated $x$ as $\widehat x=X-h$.

It is possible to show that $\widehat x\sim U[x-1/2,x+1/2]$, and thus $\mbox{Var}[\widehat x]=1/12$.


Is there an unbiased algorithm (i.e., with $\mathbb E[\widehat x]=x$) that uses a single bit and has a variance lower than $1/12$ for all $x\in[0,1]$?

$\endgroup$
2
  • 2
    $\begingroup$ I believe this is one of the questions explored in this very recent paper by Ben Basat, Mitzenmacher, and Vargaftik (are you one of the authors?) Mentioning that paper here as it seems relevant. $\endgroup$
    – Clement C.
    Feb 1 at 9:53
  • 2
    $\begingroup$ It is not answered there :). @ClementC. $\endgroup$
    – R B
    Feb 1 at 10:57
4
$\begingroup$

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 variance, as follows. We interpret the shared randomness as a uniformly random point $(s,t)$ from the disk with radius $1/2$ and center $(1/2,0)$. The sender sends a $1$ if $x > s$ and a $0$ otherwise, while the receiver takes $\hat{x} = 1/2 + \frac{\pi}{8}\sqrt{s/(1-s)}$ if they receive a $1$, and $\hat{x} = 1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}$ if they receive a $0$. To see that this is unbiased, note that $s$ has probability density function $\frac{8}{\pi}\sqrt{s(1-s)}$, so the expected value of $\hat{x}$ is

$$\int_0^x \Big(1/2 + \frac{\pi}{8}\sqrt{s/(1-s)}\Big)\frac{8}{\pi}\sqrt{s(1-s)}\ ds + \int_x^1 \Big(1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}\Big)\frac{8}{\pi}\sqrt{s(1-s)}\ ds\\ = \int_0^1 \frac{4}{\pi}\sqrt{s(1-s)} + s\ ds - \int_x^1 1\ ds = x.$$

To see that this is optimal for the average-case variance, let's first make a framework to describe the most general possible algorithm. For every possible value of the shared randomness $h$, the receiver will estimate $\hat{x}$ as one value $a(h)$ if they receive a $0$ bit, and will estimate $\hat{x}$ as a different value $b(h)$ if they receive a $1$ bit. We may as well assume that $a(h) \le b(h)$ for all $h$.

On the sender's side, imagine that the functions $a, b$ are fixed and $x$ is known, but that the sender hasn't yet peeked at the randomness $h$. The sender has to divide the possible values of $h$ into disjoint sets $A(x)$ and $B(x)$, with the plan of sending a $0$ bit if $h \in A(x)$ and sending a $1$ bit if $h \in B(x)$, subject to the constraint

$\mathbb{E}_h[a(h)\cdot\mathbf{1}_{h \in A(x)} + b(h)\cdot\mathbf{1}_{h \in B(x)}] = x$,

such that the variance of the random variable $a(h)\cdot\mathbf{1}_{h \in A(x)} + b(h)\cdot\mathbf{1}_{h \in B(x)}$ is minimized. Since the mean is fixed, minimizing the variance is equivalent to minimizing the second moment

$\mathbb{E}_h[a(h)^2\cdot\mathbf{1}_{h \in A(x)} + b(h)^2\cdot\mathbf{1}_{h \in B(x)}]$.

Since $\frac{b^2 - a^2}{b - a} = a+b$, and since we assumed that $a(h) \le b(h)$ for all $h$, the optimal strategy for the sender is to greedily set

$A(x) = \{h \mid a(h) + b(h) > t(x)\}, B(x) = \{h \mid a(h) + b(h) < t(x)\}$

for some threshold $t(x)$ which is chosen to satisfy the constraint on the mean:

$\mathbb{E}_h[a(h)\cdot\mathbf{1}_{a(h) + b(h) > t(x)} + b(h)\cdot\mathbf{1}_{a(h) + b(h) < t(x)}] = x.$

(If $a(h) + b(h) = t(x)$ with positive probability, then we divide the set of $h$s with $a(h) + b(h) = t(x)$ in any way we like to make the constraint on the mean work out.)

By rearranging the internals of the algorithm, we may now assume that $a(h) + b(h)$ is an increasing function of the random variable $h$, so the sender's strategy can be expressed as: send $0$ if $x < s(h)$ and send $1$ if $x > s(h)$, where $s$ is another threshold function, which satisfies

$\mathbb{E}_h[a(h)\cdot \mathbf{1}_{x < s(h)} + b(h)\cdot \mathbf{1}_{x > s(h)}] = x$.

From this, we can deduce that

$\mathbb{E}_h[a(h)s(h)^n + b(h)(1-s(h)^n)] = \mathbb{E}_{x,h}[a(h)\cdot nx^{n-1}\mathbf{1}_{x < s(h)} + b(h)\cdot nx^{n-1} \mathbf{1}_{x > s(h)}] = \mathbb{E}_x[nx^n] = \frac{n}{n+1}$

for every $n$, and that $b(h) - a(h) = s'(h)$.

Using the above identities, we can check that the expected variance is

$$\mathbb{E}_{x,h}[a(h)^2\cdot \mathbf{1}_{x < s(h)} + b(h)^2\cdot \mathbf{1}_{x > s(h)} - x^2]\\ = \mathbb{E}_{h}[a(h)^2s(h) + b(h)^2(1-s(h)) - 1/3]\\ = \mathbb{E}_h[(a(h)s(h) + b(h)(1-s(h)) - 1/2)^2 + (b(h) - a(h))^2s(h)(1-s(h)) - 1/12]\\ \ge \mathbb{E}_h[(b(h) - a(h))^2s(h)(1-s(h)) - 1/12].$$

By Cauchy-Schwarz, we have

$$\mathbb{E}_h[(b(h) - a(h))^2s(h)(1-s(h))]\\ \ge \mathbb{E}_h[(b(h) - a(h))\sqrt{s(h)(1-s(h))}]^2\\ = \mathbb{E}_h[s'(h)\sqrt{s(h)(1-s(h))}]^2\\ = \Big(\int_0^1 \sqrt{s\cdot (1-s)}\ ds\Big)^2 = \frac{\pi^2}{64},$$

which finishes the proof.

Edit: We can actually combine the disk-based example algorithm above (with the least possible average variance) and the subtractive dithering algorithm to create a dithering algorithm which has variance strictly less than $1/12$ for every $x$. The main idea is that the set of functions

$x \mapsto \operatorname{Var}[\hat{x}]$

coming from unbiased dithering algorithms is a convex set: given any pair of dithering algorithms, we can use shared randomness to randomly choose between them. Our plan is to first perturb the subtractive dithering algorithm in a way which keeps its average variance (for $x$ uniformly in $[0,1]$) approximately the same but which makes the variance lower for $x$ closer to $0$ and $1$ and higher for $x$ close to $1/2$, and then to take a weighted combination of this perturbed subtractive dithering algorithm with the disk-based example algorithm described above.

To perturb the subtractive dithering algorithm, we will stick with the choice of threshold $s(h) = h$, but we will perturb the functions $a(h), b(h)$. The perturbed functions will be given by

$$a(h) = h - 1/2 + \delta'(h)\\ b(h) = h + 1/2 + \delta'(h)$$

for some small function $\delta(h)$ - as long as $\delta(1) - \delta(0) = \mathbb{E}_h[\delta'(h)] = 0$, this perturbed algorithm will be unbiased. The variance of the perturbed subtractive dithering algorithm is then given by

$$\operatorname{Var}[\hat{x}] = \mathbb{E}_h[a(h)^2\cdot \mathbf{1}_{x < h} + b(h)^2\cdot \mathbf{1}_{x > h} - x^2]\\ = \tfrac{1}{12} + \mathbb{E}_h[(2h-1)\delta'(h)\cdot \mathbf{1}_{x < h} + (2h+1)\delta'(h)\cdot\mathbf{1}_{x > h} + \delta'(h)^2]\\ = \tfrac{1}{12} + 2\delta(x) - 2\int_0^1 \delta(h)\ dh + \int_0^1 \delta'(h)^2\ dh.$$

As you can see, the average value of $\operatorname{Var}[\hat{x}]$ increases by only $\int_0^1 \delta'(h)^2\ dh$, so by taking $\delta(x)$ a sufficiently small multiple of the difference of the two variance functions for the two algorithms in question, we get the perturbation we need. (While the resulting combination of the perturbed dithering algorithm and the disk-based algorithm outperforms subtractive dithering for all $x$, it is almost certainly not optimal, so I won't work out the gory details.)

$\endgroup$
3
  • $\begingroup$ Thanks for the answer, but I am not sure that the suggested algorithm is unbiased. Consider $x=0$ (or a small $\epsilon>0$). Then the sender will send $0$, making the estimate $1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}$. But this has a negative expectation(?). $\endgroup$
    – R B
    Feb 8 at 15:04
  • $\begingroup$ Keep in mind that $s$ is not uniformly distributed: in the example algorithm, the probability density function for $s$ is given by $\frac{8}{\pi}\sqrt{s(1-s)}$. If $s$ is sampled from this distribution, then the expectation of $1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}$ is $\int_0^1 \frac{4}{\pi}\sqrt{s(1-s)} - (1-s)\ ds = 0$. $\endgroup$
    – zeb
    Feb 8 at 17:14
  • $\begingroup$ Ah, Got it now, thanks. We were able to prove a $1/16$ bound using completely different arguments, but yours is better :). $\endgroup$
    – R B
    Feb 8 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.