TopCoder problem "RandomChoice" used in TCO05 Semi 2 (Division I Level Three)



Problem Statement

    

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.

 

Definition

    
Class:RandomChoice
Method:decisionProbability
Parameters:int, int, double, double, double
Returns:double
Method signature:double decisionProbability(int k, int n, double pH, double pHT, double pTH)
(be sure your method is public)
    
 

Notes

-When checking if two coin result sequences are equally probable, we don't take the given probabilities into account - i.e. the person performing the described procedure does not have any information about the probabilities. The probabilities are given in the method input since they are needed to compute the return value - i.e., after having decided which sequences are still unmapped, to compute the probability of one of these sequences coming up.
-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-k will be between 2 and 1000, inclusive.
-n will be between 1 and 1000, inclusive.
-pH will be between 0.01 and 0.99, inclusive.
-pHT will be between 0.01 and 0.99, inclusive.
-pTH will be between 0.01 and 0.99, inclusive.
 

Examples

0)
    
2
4
0.5
0.5
0.5
Returns: 0.25

With n=4 we can get the following outcomes, each with the given probability:

HHHH  (pH * pHH * pHH * pHH)    THHH  (pT * pTH * pHH * pHH)
HHHT  (pH * pHH * pHH * pHT)    THHT  (pT * pTH * pHH * pHT)
HHTH  (pH * pHH * pHT * pTH)    THTH  (pT * pTH * pHT * pTH)
HHTT  (pH * pHH * pHT * pTT)    THTT  (pT * pTH * pHT * pTT)
HTHH  (pH * pHT * pTH * pHH)    TTHH  (pT * pTT * pTH * pHH)
HTHT  (pH * pHT * pTH * pHT)    TTHT  (pT * pTT * pTH * pHT)
HTTH  (pH * pHT * pTT * pTH)    TTTH  (pT * pTT * pTT * pTH)
HTTT  (pH * pHT * pTT * pTT)    TTTT  (pT * pTT * pTT * pTT)

The outcomes HHTH and HTHH are equally probable (independent of how the individual probabilities pH, pHT, pTH are chosen), so they can be mapped to the k=2 original outcomes. The same is true for the outcomes TTHT and THTT. The rest remains unmapped (there is no other pair with equal probabilities). To compute the return value, we now insert the given values for pH, pHT, pTH, and add the probabilities for the mapped outcomes (4 mapped outcomes, each with probability 0.54, which gives the result 0.25).

1)
    
2
4
0.1
0.8
0.6
Returns: 0.3648
The same as the previous examples, but with different probabilities. The final result is now: 2 * pH * pHH * pHT * pTH + 2 * pT * pTT * pTH * pHT = 2 * 0.1 * (1.0 - 0.8) * 0.8 * 0.6 + 2 * (1.0 - 0.1) * (1.0 - 0.6) * 0.6 * 0.8 = 0.3648.
2)
    
2
6
0.5
0.5
0.5
Returns: 0.625

With n=6, we get the following equally probable outcome n-tuples:

 1: (HHHHTH, HHHTHH, HHTHHH, HTHHHH)
 2: (HHTHTT, HHTTHT, HTHHTT, HTTHHT)
 3: (TTTTHT, TTTHTT, TTHTTT, THTTTT)
 4: (TTHTHH, TTHHTH, THTTHH, THHTTH)
 5: (HHHTHT, HHTHHT, HTHHHT)
 6: (HHHTTH, HHTTHH, HTTHHH)
 7: (HHTHTH, HTHHTH, HTHTHH)
 8: (HTHTTT, HTTHTT, HTTTHT)
 9: (TTTHTH, TTHTTH, THTTTH)
10: (TTTHHT, TTHHTT, THHTTT)
11: (TTHTHT, THTTHT, THTHTT)
12: (THTHHH, THHTHH, THHHTH)
13: (HHTTTH, HTTTHH)
14: (HTHTTH, HTTHTH)
15: (TTHHHT, THHHTT)
16: (THTHHT, THHTHT)

Since here k=2, we can map all outcomes in all quadruples (1 - 4) and all pairs (13 - 16) and from each triple (5 - 12) we map a pair and leave one element unmapped. So in total we have mapped 40 outcomes. Since we have pH=pHT=pTH=0.5, the probability of each outcome is 0.56, and the final result is 40 * 0.56 = 0.625.

3)
    
3
6
0.5
0.5
0.5
Returns: 0.5625

The same example as the last one, but now with k=3. Now we can map all triples (5 - 12 from the previous example) to the k=3 outcomes and 3 elements from each quadruple (1 - 4), for a total of 36 mapped outcomes, giving 36 * 0.56 = 0.5625.

4)
    
5
1
0.5
0.5
0.5
Returns: 0.0
With just one throw we can never be sure to make a fair decision.
5)
    
1000
1000
0.5
0.01
0.01
Returns: 0.9972747235292863
Be sure not to timeout.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4819

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8092&pm=4819

Writer:

gepa

Testers:

PabloGilberto , lbackstrom , vorthys , Olexiy

Problem categories:

Math