<p><em>The question this response was trying to answer, roughly: "What is a way to reveal information about the outcome of $n$ i.i.d. coin flips that helps you learn the bias of the coin, but wihout revealing too much about the individual bits?"</em></p>

<p>Since the bits are i.i.d., the numbers $h$ and $t$ (number each of heads and tails) are completely sufficient to describe what the sequence tells you about the bias of the coin. (Or if you know $n$, either number alone.) This follows because, for each possible parameter $p$, all sequences resulting in a particular count $(h,t)$ are equally likely. So revealing the individual bits adds no information about the bias of the coin once $h$ and $t$ are known. On the other hand, presumably you don't mind releasing $h$ and $t$ as they do not give too much information about any one bit flip.</p>

<p>As a sidenote, one way to approach this general sort of problem is <em>differential privacy</em>. I'm not sure that it's a good fit for your setting, but it formalizes the notion of how much one learns about data from computing some function on the data. The idea is that, if I have two sequences $x$ and $x'$ that differ only on a single bit (say the $i$th bit), then my function, which is randomized, should produce approximately the same distribution over outputs:</p>

<p>\begin{equation}
\Pr[f(x) = a] \leq e^{\varepsilon} \Pr[f(x') = a]
\end{equation}
for all $a$.</p>

CC BY-SA 3.0
2013-04-20T11:47:15.553Z
usul thanks for answering! Unfortunately @Niels edit changed the meaning of my question slightly, thus I cannot accept your answer. And thanks for the hint to differential privacy, seems to be an interesting topic.
jan-glx
CC BY-SA 3.0
2013-04-20T14:08:22.337Z
@YAK - sure, no problem! I'll also modify the answer so it's clear what it *is* addressing.
usul
CC BY-SA 3.0
2013-04-20T01:22:20.420Z
2013-04-20T14:10:05.953Z
2013-04-20T14:10:05.953Z
usul
<p>Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability $(1-p)$.  Now repeat this experiment $n$ times, and let the total number of positive outcomes (heads) be $k$.</p>

<p>Now, given $n$ and $k$ but not $p$ what is the probability that the Bernoulli experiment (flipping the coin) again will result in a positive outcome (head)?</p>

<p>If $n$ and $k$ were 0 this would be an easy task: as there is no further information and the outcomes could be defined the other way around, it is symmetric and thus $p=0.5$.</p>

<p>Otherwise it's a little more complicated (the dependency on n ($|n$) is omitted for clarity).
The expected probability is:
$\langle p |k\rangle = \int _0 ^1 p\cdot f(p|k) \,\mathrm{d} p$.</p>

<p>Using Bayes' theorem gives
$f(p|k) = p(k|p) \frac{f(p)}{p(k)}  $
and marginalization gives $p(k)=\int_0^1 p(k|p) \cdot f(p) \,\mathrm{d} p$. The Binomial distribution further tells us that $p(k|p)=\binom{n}{k}\cdot p^k \cdot (1-p)^{n-k}$. But what is the correct term for the prior of $p$, $f(p)$?</p>

<p>Jaynes &amp; co. tell me to use a maximum Entropy prior.
To maximize entropy of $p$  ($H(p)=-\int_0^1 f(p) \cdot ln(f(p)) \,\mathrm{d} p$), set $f(p)=1$. But this would not maximize the entropy of $k$; the entropy of $k$ would be maximal if $p$ was $0.5$ thus if $f(p)=0$ but infinity at 0.5 (integrating to 1).</p>

<p>So, what is the correct prior to choose for $f(p)$? Does it depend on $n$?</p>

CC BY-SA 3.0
2013-04-19T15:16:58.783Z
Could you please re-formulate the question?
Rasto S.
CC BY-SA 3.0
2013-04-19T15:29:32.520Z
I have attempted to reformulate the question to make it clearer. But it is possible that I have changed the meaning of the question: YAK, could you please check that the question is the one you would like to ask?
Niel de Beaudrap
CC BY-SA 3.0
2013-04-19T15:36:18.377Z
Can't you simply use the empirical bias? If we know that the bias of each coin is $p$, then each individual bit has entropy $h(p)$. If $n$ is large, by the law of large numbers the empirical bias of the coins would be close to $p$, and conditioned on that information the entropy of each individual bit is still close to $h(p)$. So the empirical mean does not provide any further information than the bias of the coins.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-04-20T11:43:42.080Z
Sry @NieldeBeaudrap and others, I thought asking in prose was easier and more fun.
jan-glx
CC BY-SA 3.0
2013-04-21T11:13:08.103Z
Could the down-voters plz explain why?
jan-glx
<it.information-theory><st.statistics><shannon-entropy>
How to choose a correct prior
jan-glx
# How to choose a correct prior

(Asked by: username_0 on 2013-04-19)

Consider a Bernoulli experiment, such as flipping a not necessarily fair coin, which results in a positive outcome (heads) with probability $p$ and with a negative outcome (tails) with probability $(1-p)$. Now repeat this experiment $n$ times, and let the total number of positive outcomes (heads) be $k$.

Now, given $n$ and $k$ but not $p$ what is the probability that the Bernoulli experiment (flipping the coin) again will result in a positive outcome (head)?

If $n$ and $k$ were 0 this would be an easy task: as there is no further information and the outcomes could be defined the other way around, it is symmetric and thus $p=0.5$.

Otherwise it's a little more complicated (the dependency on n ($|n$) is omitted for clarity).
The expected probability is:
$\langle p |k\rangle = \int \_0 ^1 p\cdot f(p|k) \,\mathrm{d} p$.

Using Bayes' theorem gives
$f(p|k) = p(k|p) \frac{f(p)}{p(k)} $
and marginalization gives $p(k)=\int\_0^1 p(k|p) \cdot f(p) \,\mathrm{d} p$. The Binomial distribution further tells us that $p(k|p)=\binom{n}{k}\cdot p^k \cdot (1-p)^{n-k}$. But what is the correct term for the prior of $p$, $f(p)$?

Jaynes & co. tell me to use a maximum Entropy prior.
To maximize entropy of $p$ ($H(p)=-\int\_0^1 f(p) \cdot ln(f(p)) \,\mathrm{d} p$), set $f(p)=1$. But this would not maximize the entropy of $k$; the entropy of $k$ would be maximal if $p$ was $0.5$ thus if $f(p)=0$ but infinity at 0.5 (integrating to 1).

So, what is the correct prior to choose for $f(p)$? Does it depend on $n$?

**Tags:** it.information-theory, st.statistics, shannon-entropy

> **Comments:**
> **username_1**: Could you please re-formulate the question?  
> **username_2**: I have attempted to reformulate the question to make it clearer. But it is possible that I have changed the meaning of the question: YAK, could you please check that the question is the one you would like to ask?  
> **username_3**: Can't you simply use the empirical bias? If we know that the bias of each coin is $p$, then each individual bit has entropy $h(p)$. If $n$ is large, by the law of large numbers the empirical bias of the coins would be close to $p$, and conditioned on that information the entropy of each individual bit is still close to $h(p)$. So the empirical mean does not provide any further information than the bias of the coins.  
> **username_0**: Sry @NieldeBeaudrap and others, I thought asking in prose was easier and more fun.  
> **username_0**: Could the down-voters plz explain why?  

---

## 1 answers

### Answer by username_4 on 2013-04-20. Score: 5

*The question this response was trying to answer, roughly: "What is a way to reveal information about the outcome of $n$ i.i.d. coin flips that helps you learn the bias of the coin, but wihout revealing too much about the individual bits?"*

Since the bits are i.i.d., the numbers $h$ and $t$ (number each of heads and tails) are completely sufficient to describe what the sequence tells you about the bias of the coin. (Or if you know $n$, either number alone.) This follows because, for each possible parameter $p$, all sequences resulting in a particular count $(h,t)$ are equally likely. So revealing the individual bits adds no information about the bias of the coin once $h$ and $t$ are known. On the other hand, presumably you don't mind releasing $h$ and $t$ as they do not give too much information about any one bit flip.

As a sidenote, one way to approach this general sort of problem is *differential privacy*. I'm not sure that it's a good fit for your setting, but it formalizes the notion of how much one learns about data from computing some function on the data. The idea is that, if I have two sequences $x$ and $x'$ that differ only on a single bit (say the $i$th bit), then my function, which is randomized, should produce approximately the same distribution over outputs:

\begin{equation}
\Pr[f(x) = a] \leq e^{\varepsilon} \Pr[f(x') = a]
\end{equation}
for all $a$.

> **Comments:**
> **username_0**: username_4 thanks for answering! Unfortunately @Niels edit changed the meaning of my question slightly, thus I cannot accept your answer. And thanks for the hint to differential privacy, seems to be an interesting topic.  
> **username_4**: @YAK - sure, no problem! I'll also modify the answer so it's clear what it *is* addressing.  

---

