We have to make a uniform random decision among k
possible outcomes, but all we have available is an
unfair coin.
The coin has a probability pH of
giving Heads and pT = 1 - pH of giving
Tails in the first throw. Subsequent throws are
dependent on the previous throw, and there is a probability
pHT of throwing Tails after a Heads throw and
pTH of throwing Heads after a Tails throw. Note
that either Heads or Tails always comes out, so the probability
of throwing Tails after a Tails throw is
pTT = 1 - pTH and the probability of throwing
Heads after a Heads throw is pHH = 1 - pHT.
In order to make a fair decision, we throw the coin
n times. If there are k coin result sequences
that are equally probable (independent of pH, pHT and
pTH), we can map each of these sequences to one
of the k original decision outcomes. We repeat this
with further coin result sequences, mapping as many of them
as possible to the k original decision outcomes. At
the end, some of the coin result sequences may remain unmapped.
After we throw the coin n times, either one of the
mapped sequences will come out, in which case we can
directly make the fair decision by choosing the mapped
outcome, or one of the unmapped sequences will come out,
in which case we still cannot make a fair decision
(we could then repeat making n further throws, until
one of the mapped sequences comes out).
For example, let's say k = 3, and n = 6 (we
have to choose among three outcomes, and throw the coin 6 times).
In this case, the sequences "HTHHHH", "HHTHHH",
"HHHTHH" and "HHHHTH" are equally probable
(the given strings show the outcome of the 6 coin throws in order,
with H representing Heads and T representing Tails; each of these
sequences has a probability of pH * pHH * pHH
* pHT * pTH). So we can map three of these sequences
to the three outcomes, and one sequence will remain unmapped. Similarly,
we can map the sequences "HTTHHH", "HHTTHH" and
"HHHTTH" to the three outcomes. We get similarly six further mappings
if we exchange "H" and "T" in these sequences.
It turns out that these are the only mappings that we can find
in this case, meaning that we have mapped 12 of the 26=64
possible sequences, with 52 sequences remaining unmapped.
Note also that sequences that remain unmapped in
one mapping step can still be used in further steps - i.e., if in the example above k was 2 instead of 3, and we mapped 2 of the first 4 mentioned sequences above to the 2 outcomes, the remaining 2 would also get mapped, since they still have the same probability. In general, if we have m equally probable outcomes,
m % k of them will remain unmapped, while the other
m - (m % k) outcomes will get mapped to some of the
original decisions.
You will be given k, the number of outcomes in the decision
you have to make, n, the number of coin throws you perform,
and pH, pHT and pTH, the initial and
subsequent conditional probabilities of the coin outcome (pH,
pHT and pTH from the above description, respectively).
You are to return the probability that the n
throws will be sufficient to make a decision - i.e., the probability that
we will get one of the outcomes that we have mapped to one of the original
decision outcomes.
|