What was left unclear to my mind was just how one decides whether the "procedure" that was asked for is in fact "statistically indistinguishable" from tossing the biased coin n' times. As Michael points out, a single run of n' (imaginary) tosses won't do the trick. I commented earlier that this made sense to me only if there were infinitely many tosses. I should not have said "only" (and there are subtler objections to this idea, anyway). (I am not a "frequentist", but this earlier suggestion would at least be *one* way to define "statistically indistinguishable . . . with probability 1.) Rather, perhaps one should imagine *all* 2^n ways that the friend's n tosses could come out, and for each of these -- using Warren's procedure -- all n-choose-#(H) ways of ordering the number #(H) of heads among the n tosses. Now consider all the the initial length-n' strings (with multiplicity) of the resulting however-many-bit-strings that is. Call this multiset S. Finally, the procedure was "statistically indistinguishable" from using actual length-n' runs of coin tosses in the first place if each sequence of K heads out of n' tosses occurs in S with the correct frequency. That is, the exact proportion n'-choose-K p^k (1-p)^(n'-k) of all of S. --Dan P.S. I'm still, alas, not yet seeing the connection between this problem and the one of reverse-engineering Galton boards. Jim wrote: << Each time the game is repeated, your friend tosses n real coins and you announce the tosses of n' imaginary coins. It's crucial that your friend generates new tosses (using the same bias, of course). . . . Michael wrote: << What? Maybe I was confused about the problem. Suppose the flip sequence I'm learning from is HH. Then when I predict a single coin flip, I'll predict heads every time, but my friend might well have a fair coin. What am I missing?
. . . [Warren's procedure] is correct. Note that you don't need to know the initial sequenceof 0's and 1's in order to generate a random permutation of it; it'senough to know the number of 0's and 1's The solution I had in mind was an iterative one that successivelycomputes random variables distributed like Binomial(p,n-1),Binomial(p,n-2),...,Binomial(p,n'), where at each stage you throw out one of the bits at random. E.g., at the first stage, you reduce X to X-1 with probability X/n and leave it alone with probability (n-X)/n.Another description of this is Dither(((n-1)/n)X), where Dither(t) denotes a random variable that takes on the values floor(t) and ceiling(t) (and no other values) with expected value exactly t. Then we multiply by (n-1)/(n-2) and dither again, etc.