1
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ Could you please re-formulate the question? $\endgroup$ – Rasto S. Apr 19 '13 at 15:16
  • 1
    $\begingroup$ 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? $\endgroup$ – Niel de Beaudrap Apr 19 '13 at 15:29
  • 1
    $\begingroup$ 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. $\endgroup$ – MCH Apr 19 '13 at 15:36
  • $\begingroup$ Sry @NieldeBeaudrap and others, I thought asking in prose was easier and more fun. $\endgroup$ – jan-glx Apr 20 '13 at 11:43
  • $\begingroup$ Could the down-voters plz explain why? $\endgroup$ – jan-glx Apr 21 '13 at 11:13
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jan-glx Apr 20 '13 at 11:47
  • $\begingroup$ @YAK - sure, no problem! I'll also modify the answer so it's clear what it is addressing. $\endgroup$ – usul Apr 20 '13 at 14:08

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.