3 ms·
Yes, that is covered in this half paragraph: > Randomized rounding, where the sender sends 1 with probability x and 0 otherwise, and the receiver uses the rece
by rav 5y ago
Yes, that is covered in this half paragraph:
> Randomized rounding, where the sender sends 1 with probability x and 0 otherwise, and the receiver uses the received bit X as the estimate x', has the property that E[x'] = x. Unbiased estimators are arguably more natural for many estimation problems. Here the measure of performance would be the maximum variance for the estimate over all inputs x, so for randomized rounding the cost is 1/4 (when x = 1/2).
The "cost"/"variance" of 1/4 in the above paragraph is talked about later in the article as the "expected squared error"; the main result is a scheme that has a cost of just 0.04599, which is better than the "send a 1 with a probability x" scheme, which has a cost of 1/4 = 0.25.
- IanCal 5y agoThank you, I found it tricky to read things as I usually do as I had less to latch on to.