Problem Statement
I have t tokens and p initially empty piles. One after another, I place each token onto a pile chosen uniformly at random. (All choices are mutually independent.)
What is the probability that once I'm done, multiple piles will be tied for being the largest?
Definition
- Class:
- TieForMax
- Method:
- getProbability
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double getProbability(int t, int p)
- (be sure your method is public)
Notes
- Your return value must have an absolute error at most 1e-9.
Constraints
- t will be between 1 and 50, inclusive.
- p will be between 1 and 50, inclusive.
Examples
7
1
Returns: 0.0
I will make a single pile with seven tokens. With just one pile there can be no ties.
2
2
Returns: 0.5
With probability 50% I will get a unique largest pile with two tokens, and with probability 50% I will get a tie: two piles with one token each.
3
3
Returns: 0.2222222222222222
The tie can only happen if I get three piles with one token on each of them. The probability of that event is 6/27 = 2/9.
6
4
Returns: 0.380859375
Now there are multiple configurations in which the maximum isn't unique. For example, the pile sizes can be {1,2,1,2}, {0,3,3,0}, or even {0,2,2,2}.
50
50
Returns: 0.49549217175140714
50
1
Returns: 0.0
50
2
Returns: 0.11227517265921705
44
15
Returns: 0.33001699751934377
5
31
Returns: 0.7263180804767839
50
3
Returns: 0.10878542928411916
9
1
Returns: 0.0
24
17
Returns: 0.42495356805756523
25
5
Returns: 0.21471557428462928
1
17
Returns: 0.0
2
1
Returns: 0.0
3
21
Returns: 0.8616780045351474
15
16
Returns: 0.43585062590862367
19
23
Returns: 0.4571632236266011
22
37
Returns: 0.5345127875026959
3
11
Returns: 0.743801652892562
32
37
Returns: 0.49279229282606474
41
36
Returns: 0.46905235614025453
2
5
Returns: 0.8
17
16
Returns: 0.41542972092942454
1
2
Returns: 0.0
35
25
Returns: 0.42317426811953307
29
39
Returns: 0.4820714816238115
50
15
Returns: 0.31422235926273756
19
7
Returns: 0.2990551413809619
21
50
Returns: 0.6358596072706825
50
4
Returns: 0.13308211101723455
11
22
Returns: 0.5449108970976813
25
39
Returns: 0.5012031087298271
49
3
Returns: 0.09306300267073653
38
24
Returns: 0.4072885789245172
2
2
Returns: 0.5
39
49
Returns: 0.5159893885043945
16
25
Returns: 0.5485650062644534
9
24
Returns: 0.47910243985929457
48
45
Returns: 0.48046472719616595
1
1
Returns: 0.0
25
29
Returns: 0.46365045529584514
10
50
Returns: 0.538429177796902
49
35
Returns: 0.43346326065860097
2
47
Returns: 0.9787234042553191
39
28
Returns: 0.4249141992532032
12
29
Returns: 0.55260438531691
2
17
Returns: 0.9411764705882353
10
41
Returns: 0.5122372788409225
40
25
Returns: 0.409842548427532
19
31
Returns: 0.5428608176924823
47
22
Returns: 0.37808489133629763
45
2
Returns: 0.0
18
3
Returns: 0.14122145718524426
35
35
Returns: 0.4949159314588264
2
50
Returns: 0.98
16
31
Returns: 0.5992335336918639
37
37
Returns: 0.4973596431344657
28
17
Returns: 0.3883386272497261
17
39
Returns: 0.6226721908569057
18
36
Returns: 0.6044374564780673
25
44
Returns: 0.5333603109590493
1
47
Returns: 0.0
28
40
Returns: 0.48449445645313927
50
48
Returns: 0.48501081581934014
24
36
Returns: 0.4946080805982409
49
34
Returns: 0.4314105039475389
5
27
Returns: 0.6934918457552203
30
36
Returns: 0.48433067198672786
36
33
Returns: 0.48139028784653637
34
17
Returns: 0.3785937650583756
33
22
Returns: 0.4090397618953522
50
25
Returns: 0.3920895759176388
15
50
Returns: 0.5779582335024485