Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please give a protocol to incrementally reveal information.

A politician wishes to make a yes/no announcement with out shocking the economy. They set a date 100 days in the future, and every day reveal more about the announcement so that at the end of the 100 days, there is no uncertainty about the announcement. What should the politician reveal each day?

An example of a (mediocre) protocol is to fill a urn with a ball with the true announcement and 99 randomly chosen announcements and each day the politician removes one of the randomly chosen announcements. This protocol is good because by inspecting the urn each day, the public's uncertainty either decreases or stays the same until at the end there is no uncertainty. However, this protocol is bad because it does not reduce the publics uncertainty by a consistent amount each day. The amount of information revealed is only consistent in expectation. For example if on the third to last day the remaining balls are all yes, then the public already knows the announcement. Further it can happen that the last two balls are yes and no. This means that there was no reduction in uncertainty from the beginning.

Thinking of the announcement as communicating 1 bit on a channel, an optimal protocol is a series of communications that so that after the t of n incremental communication, exactly t/n bits have been communicated. Does such a protocol exist? And if so, what is a straight forward implementation such a protocol?

share|cite|improve this question

Consider a protocol where each day, the political reveals either "0" or "1", with "0" intended to be an approximation to "no", and "1" intended to be an approximation of "yes".

On any particular day, we have

  • P(yes) = the probability the public thinks the politician will announce yes
  • P(no) = the probability the public thinks the politician will announce no

and the politician wants to reveal either "0" or "1" so that

  • P(yes | 0) = q
  • P(yes | 1) = p
  • P(no | 0) = p
  • P(no | 1) = q

where q = 1-p, p > q, and p is chosen so that the entropy is at a desired level.

The politician's strategy is clear:

  • If he wants to announce yes, then
    • He reveals 0 with probability P(0 | yes)
    • He reveals 1 with probability P(1 | yes)
  • If he wants to announce no, then
    • He reveals 0 with probability P(0 | no)
    • He reveals 1 with probability P(1 | no)

If the politician publishes his strategy for choosing whether to reveal "0" or "1" that day, then the public's level of knowledge will be at the desired level.

The resulting equation is easy to solve -- the only challenge is in setting up the problem. The result is

  • P(1 | yes) = p(P(yes) - q) / ((p-q) P(yes))
  • P(0 | yes) = q(p - P(yes)) / ((p-q) P(yes))
  • P(1 | no) = q(p - P(no)) / ((p-q) P(no))
  • P(0 | no) = p(P(no) - q) / ((p-q) P(no))

(unless I've made an error in substituting)

If the entropy is to be increasing, then I'm pretty sure the above probabilities are all within [0,1], so this protocol is well-defined (assuming the public starts with sufficiently uniform priors on the initial day).

share|cite|improve this answer
I think your protocol does not end up with certainty for the public. A minimal change would do it though, just let the last bit equal the politicians's decision and for the rest your protocol should work. – Euclean Jul 3 '12 at 16:14
If the desired level of entropy is certainty, then $p=1$ and $q=0$. – Hurkyl Jul 3 '12 at 21:28
I wrongly assumed that you took your $p$ fixed in the algorithm, good solution! – Euclean Jul 3 '12 at 21:57
up vote 1 down vote accepted

This paper

Gradual Release of Sensitive Data under Differential Privacy
Fragkiskos Koufogiannis, Shuo Han, George J. Pappas

gives a solution using the differential privacy framework.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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