Statistics

Problem Statement for "RandomChoice"

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

  1. 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).

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

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

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

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

  6. 1000

    1000

    0.5

    0.01

    0.01

    Returns: 0.9972747235292863

    Be sure not to timeout.

  7. 2

    5

    0.99

    0.99

    0.5

    Returns: 0.5049000000000001

  8. 12

    8

    0.31

    0.4

    0.8

    Returns: 0.04777574399999995

  9. 200

    1000

    0.5

    0.02

    0.02

    Returns: 0.9999998907352533

  10. 2

    1000

    0.8

    0.2

    0.02

    Returns: 0.9999999980675841

  11. 1000

    16

    0.5

    0.1

    0.7

    Returns: 0.005207478821999456

  12. 1000

    40

    0.5

    0.5

    0.5

    Returns: 0.9999994053941919

  13. 1000

    100

    0.3

    0.9

    0.9

    Returns: 0.9991989203224404

  14. 997

    1000

    0.1

    0.02

    0.1

    Returns: 0.9999999905967523

  15. 701

    15

    0.5

    0.5

    0.5

    Returns: 0.0

  16. 700

    15

    0.5

    0.5

    0.5

    Returns: 0.1708984375

  17. 30

    209

    0.8934291818868989

    0.8799462635767806

    0.46536867224523193

    Returns: 1.0

  18. 298

    73

    0.6095597760698733

    0.021261400001797215

    0.6576833822264391

    Returns: 0.426055198010142

  19. 111

    946

    0.2995367133191471

    0.4383715703668817

    0.026201077802417982

    Returns: 0.9999999999681852

  20. 811

    528

    0.1330895489820706

    0.018196068302740454

    0.6322256583917844

    Returns: 0.9995197906449049

  21. 57

    78

    0.10690733256094753

    0.013904316560596985

    0.3289626129462452

    Returns: 0.5829436269816803

  22. 648

    311

    0.18888035630727562

    0.9264408727994317

    0.012417043031080821

    Returns: 0.8942294085532045

  23. 770

    43

    0.590471232799397

    0.8302562222905953

    0.046335790162052914

    Returns: 0.40411516029744954

  24. 671

    21

    0.8515962128787526

    0.848357157607038

    0.8201038593857

    Returns: 0.31741518789425516

  25. 53

    31

    0.9590804554804091

    0.8416222421478784

    0.7727116370231436

    Returns: 0.9710038343292585

  26. 929

    16

    0.6743478069480922

    0.8146196890094326

    0.5840044772982261

    Returns: 0.09018012044124313

  27. 697

    7

    0.047718685548700845

    0.3116503845472538

    0.3603219949285743

    Returns: 0.0

  28. 472

    61

    0.7026687110643167

    0.08741270966848791

    0.05921037405512375

    Returns: 0.7217884521498865

  29. 473

    837

    0.25418262532310376

    0.696868368033392

    0.04973163823360882

    Returns: 1.0

  30. 538

    392

    0.6530630062868641

    0.20271780167556364

    0.011640526660319228

    Returns: 0.9662771598351095

  31. 801

    17

    0.9524261545938867

    0.5797055694395395

    0.7320671687260294

    Returns: 0.3989530413297536

  32. 735

    16

    0.43029199007896257

    0.828885065117082

    0.1913086861544837

    Returns: 0.041000652872283716

  33. 333

    28

    0.8379289460258295

    0.5741107732145737

    0.11515488029143839

    Returns: 0.65139827513114

  34. 535

    830

    0.43847633237230743

    0.02814281757653747

    0.5651124230190319

    Returns: 0.9999999996014727

  35. 67

    39

    0.6764558768295295

    0.0991900548959348

    0.11882075083829768

    Returns: 0.7599408256483642

  36. 333

    930

    0.9127092628019957

    0.9881681805122412

    0.01009151112810995

    Returns: 0.9996983564791349

  37. 795

    22

    0.3470259584452423

    0.8070475559399093

    0.23648651217363736

    Returns: 0.6684887789893823

  38. 106

    22

    0.34457535772414494

    0.42385425544447164

    0.8411031431880671

    Returns: 0.9834741107966017

  39. 298

    808

    0.6675201250326502

    0.4024331888628583

    0.013263084423902338

    Returns: 0.9999453294393064

  40. 65

    216

    0.09777973873805723

    0.39358536166409486

    0.06848635426730976

    Returns: 0.9999992962119717

  41. 689

    18

    0.2320376444807032

    0.22597130453100522

    0.7135864379209768

    Returns: 0.33307547500235446

  42. 540

    375

    0.6964771507139836

    0.0282264493679

    0.8509482305900228

    Returns: 0.9997297235744389

  43. 355

    106

    0.16265111364690454

    0.14966297907300774

    0.01838482145984799

    Returns: 0.561703215278857

  44. 399

    41

    0.5534000879492105

    0.8999733359747079

    0.022529831363618857

    Returns: 0.1479316969531117

  45. 162

    65

    0.49528067995055347

    0.014713743759392708

    0.03968331007957718

    Returns: 0.179776192116755

  46. 985

    139

    0.4313443996429023

    0.015550454724917118

    0.9557630305530712

    Returns: 0.6169151309565135

  47. 751

    41

    0.06294636786121566

    0.8408730095621242

    0.9439212055864341

    Returns: 0.7663388933923034

  48. 542

    346

    0.8881271586619132

    0.010778692316502635

    0.9239544358684008

    Returns: 0.885462084229174

  49. 353

    985

    0.4334407968626587

    0.20137372953418398

    0.02087984033390944

    Returns: 0.9999999949066445

  50. 902

    49

    0.7595587450597687

    0.012405400041697545

    0.049491832380878176

    Returns: 0.02433831133405029

  51. 873

    756

    0.6995593424533598

    0.028660094564255667

    0.8870990764025423

    Returns: 0.999999992923696

  52. 820

    47

    0.19972065383541748

    0.31212768257448564

    0.11364296167990029

    Returns: 0.9341910140610156

  53. 333

    983

    0.23142797868142773

    0.012610042418538248

    0.4542761312118807

    Returns: 0.999986975008032

  54. 932

    22

    0.528141089821999

    0.4371866541887016

    0.6398126807033945

    Returns: 0.9403041650753685

  55. 786

    56

    0.01482616105784862

    0.013297203117772494

    0.7282965977168906

    Returns: 0.11967976825267246

  56. 326

    14

    0.825287559312166

    0.6023383883886897

    0.686644231531367

    Returns: 0.17850184457734952

  57. 870

    749

    0.3895295695777058

    0.010319833753601837

    0.042555669725719

    Returns: 0.9976027393690443

  58. 698

    41

    0.3418019208726073

    0.16950795071360358

    0.02005470569149692

    Returns: 0.1002867919243654

  59. 629

    261

    0.8323436395234692

    0.012968964507386271

    0.016871013750779706

    Returns: 0.7124134133626399

  60. 103

    496

    0.9086543649648878

    0.6231390557026762

    0.04410870918721721

    Returns: 0.9999999992637816

  61. 440

    119

    0.8887088318033107

    0.020430033218106103

    0.9012302887664122

    Returns: 0.6816898776640585

  62. 550

    31

    0.04332515131614689

    0.5996957457411082

    0.09027358762127569

    Returns: 0.546424954472212

  63. 738

    22

    0.36558171456575284

    0.8494734263760019

    0.5038260805277306

    Returns: 0.8881339387519045

  64. 7

    93

    0.8655462513082055

    0.914493716826471

    0.024646711319751362

    Returns: 0.8811759916821003

  65. 598

    18

    0.08485292028934932

    0.7413056842254194

    0.9851103866050902

    Returns: 0.015961854728369862

  66. 808

    874

    0.43016048098849824

    0.409366920139818626

    0.012546538182326419

    Returns: 0.9999688348824689

  67. 294

    758

    0.38956090838709645

    0.32807732757343444

    0.01010616650686843254

    Returns: 0.9989424611890119

  68. 697

    19

    0.9508476283710557

    0.8177443153425099

    0.6467079889972004

    Returns: 0.5135613937628484

  69. 190

    17

    0.5303443990450795

    0.8878342165186565

    0.4780295131573151

    Returns: 0.6999059370773111

  70. 56

    14

    0.754613110822644

    0.3978212506504426

    0.45025315610418926

    Returns: 0.7089602660399856

  71. 836

    287

    0.769836470880496

    0.5734428513861176

    0.0102038324670382452

    Returns: 0.825013944083512

  72. 346

    358

    0.8973097535203967

    0.6952091019081079

    0.01015240098501134725

    Returns: 0.9704895108100651

  73. 552

    38

    0.46519984273070925

    0.06782486848412261

    0.6342578928828657

    Returns: 0.6239496210128026

  74. 220

    15

    0.09252357444729786

    0.8862720503479175

    0.5169804665040558

    Returns: 0.24999423551715716

  75. 989

    53

    0.15681177580590622

    0.09961587076293421

    0.027699910128780925

    Returns: 0.22008196997461082

  76. 860

    35

    0.5672443727252698

    0.14307640750559936

    0.9863108362132201

    Returns: 0.8106169122330931

  77. 804

    306

    0.8422291510570434

    0.010193638879750776

    0.48289662897493935

    Returns: 0.8212340852836485

  78. 914

    28

    0.17787927120114544

    0.7100764982342501

    0.8119229284198881

    Returns: 0.9253734614671669

  79. 858

    59

    0.9820631261362436

    0.03793070576976687

    0.6702666882846938

    Returns: 0.5505028441450843

  80. 556

    23

    0.11497802234179244

    0.1743543110363971

    0.944556427914677

    Returns: 0.529782357450213

  81. 373

    956

    0.5764297422412955

    0.01056254879115987

    0.014004288277085

    Returns: 0.9995796654746822

  82. 348

    169

    0.1358304403233247

    0.8624592137246775

    0.010266397247642

    Returns: 0.5067783718730645

  83. 888

    203

    0.1730864107221295

    0.0105430445881538737

    0.8248911270548906

    Returns: 0.6183902767794365

  84. 388

    186

    0.4508717873164426

    0.01038857150109214977

    0.5378032399358923

    Returns: 0.6107652127367942

  85. 164

    58

    0.37367887494184004

    0.0107330615160837661

    0.6637641202917299

    Returns: 0.1268422393159362

  86. 35

    10

    0.2

    0.01

    0.05

    Returns: 3.250685425282285E-7

  87. 1000

    16

    0.1

    0.95

    0.97

    Returns: 7.962395251359666E-6

  88. 1000

    1000

    0.4

    0.01

    0.99

    Returns: 0.9995050683352864

  89. 1000

    1000

    0.98

    0.98

    0.98

    Returns: 0.9999999621746558

  90. 2

    1000

    0.5

    0.99

    0.99

    Returns: 0.9999559477058064

  91. 5

    1000

    0.99

    0.01

    0.57

    Returns: 0.9999545218927101

  92. 10

    1000

    0.01

    0.01

    0.99

    Returns: 0.9999523776775924

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: