Statistics

Problem Statement for "NestedRandomness"

Problem Statement

Consider a function randomInt(integer N) that takes an integer N and returns an integer uniformly at random in the range 0 to N-1. If that function is nested, as in randomInt(randomInt(N)), the probability distribution changes, and some numbers are more likely than others. Given an int nestings defining the number of times the function is nested (1 indicates randomInt(N), 2 indicates randomInt(randomInt(N)), and so on), an int N and an int target, return the probability that the result of nestings nested calls to randomInt with the parameter N will result in target.

Definition

Class:
NestedRandomness
Method:
probability
Parameters:
int, int, int
Returns:
double
Method signature:
double probability(int N, int nestings, int target)
(be sure your method is public)

Notes

  • Calling randomInt(0) causes an error to occur, and hence can never cause an outcome of target.
  • Your return must have a relative or absolute error less than 1E-9.

Constraints

  • N will be between 1 and 1000, inclusive.
  • nestings will be between 1 and 10, inclusive.
  • target will be between 0 and N-nestings, inclusive.

Examples

  1. 5

    2

    1

    Returns: 0.21666666666666667

    There are 3 ways of ending up with a 1 after calling randomInt(randomInt(5)). The inner call can result in a 4, 3, or a 2. Each of these possibilities occurs with a probability of 1/5. The probabilities of achieving a 1 with each of those results are 1/4, 1/3, and 1/2, respectively. This gives us a final probability of (1/5)*(1/4+1/3+1/2) = 13/60.

  2. 10

    4

    0

    Returns: 0.19942680776014104

  3. 1000

    10

    990

    Returns: 1.0461776397050886E-30

  4. 1000

    7

    0

    Returns: 0.165676656915066

  5. 1

    1

    0

    Returns: 1.0

  6. 50

    4

    0

    Returns: 0.23479574692949326

  7. 10

    10

    0

    Returns: 2.7557319223985894E-7

  8. 1000

    10

    1

    Returns: 0.03398906538272463

  9. 752

    6

    0

    Returns: 0.1606392598541192

  10. 886

    2

    170

    Returns: 0.001859385756588236

  11. 864

    8

    2

    Returns: 0.04212393830217547

  12. 798

    2

    355

    Returns: 0.0010124765930278965

  13. 830

    6

    6

    Returns: 0.025216352825259428

  14. 651

    6

    7

    Returns: 0.021204722771317422

  15. 727

    2

    559

    Returns: 3.5927771815528114E-4

  16. 101

    5

    0

    Returns: 0.21102403501960595

  17. 822

    2

    45

    Returns: 0.003519950789012786

  18. 101

    6

    0

    Returns: 0.1770581054773769

  19. 843

    8

    2

    Returns: 0.04183288821011043

  20. 910

    5

    1

    Returns: 0.06962979389097596

  21. 412

    6

    3

    Returns: 0.04392173956932056

  22. 92

    5

    0

    Returns: 0.2125206500658938

  23. 590

    5

    107

    Returns: 5.830311972571039E-4

  24. 466

    2

    76

    Returns: 0.003875138258831273

  25. 222

    2

    58

    Returns: 0.005997227522082085

  26. 461

    5

    20

    Returns: 0.008233315372095562

  27. 696

    3

    33

    Returns: 0.006588342463832896

  28. 102

    2

    2

    Returns: 0.03624782850724145

  29. 785

    5

    8

    Returns: 0.021499005838689945

  30. 987

    4

    155

    Returns: 0.0010598056951279617

  31. 891

    5

    12

    Returns: 0.015088303689213713

  32. 643

    1

    203

    Returns: 0.0015552099533437014

  33. 605

    1

    501

    Returns: 0.001652892561983471

  34. 581

    6

    0

    Returns: 0.1694783864302501

  35. 486

    7

    14

    Returns: 0.0049344330846180515

  36. 959

    3

    46

    Returns: 0.004763085306245051

  37. 916

    1

    506

    Returns: 0.001091703056768559

  38. 57

    3

    9

    Returns: 0.02710388150689797

  39. 837

    5

    16

    Returns: 0.011553253411289367

  40. 606

    7

    5

    Returns: 0.0219060047961402

  41. 659

    1

    410

    Returns: 0.0015174506828528073

  42. 759

    2

    72

    Returns: 0.0030932126252227452

  43. 240

    4

    3

    Returns: 0.04987453610310109

  44. 57

    1

    19

    Returns: 0.017543859649122806

  45. 284

    3

    15

    Returns: 0.014762373236258163

  46. 917

    3

    31

    Returns: 0.006177665025348897

  47. 376

    6

    1

    Returns: 0.09147638310634992

  48. 528

    6

    1

    Returns: 0.08993321318420815

  49. 201

    4

    10

    Returns: 0.02061285910905523

  50. 586

    3

    146

    Returns: 0.0016333814602099218

  51. 86

    4

    2

    Returns: 0.07738026823537242

  52. 516

    7

    0

    Returns: 0.17027991841332316

  53. 74

    5

    0

    Returns: 0.21417148361882282

  54. 192

    2

    5

    Returns: 0.018483183731115113

  55. 631

    3

    212

    Returns: 9.347776807777669E-4

  56. 476

    5

    13

    Returns: 0.01361167995370354

  57. 804

    8

    2

    Returns: 0.04126063836425293

  58. 222

    5

    0

    Returns: 0.18471389957699386

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: