10
\$\begingroup\$

Write a program or function, that given a success probability p, a number n and a number of trials m returns the chance of at least n successes out of m trials.

Your answer must be precise to at least 5 digits after the decimal.

Test cases:

 0.1, 10, 100 -> 0.54871
 0.2, 10, 100 -> 0.99767
 0.5, 13,  20 -> 0.13159
 0.5,  4,   4 -> 0.06250
0.45, 50, 100 -> 0.18273
 0.4, 50, 100 -> 0.02710
   1,  1,   2 -> 1.00000
   1,  2,   1 -> 0.00000
   0,  0,   1 -> 1.00000
   0,  0,   0 -> 1.00000
   0,  1,   1 -> 0.00000
   1,  1,   0 -> 0.00000
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Would you care to include a formula to those of us who haven't studied binomial distribution? \$\endgroup\$
    – Leaky Nun
    May 3 '16 at 11:09
  • 2
    \$\begingroup\$ @KennyLau Sorry, that is part of the challenge. \$\endgroup\$
    – orlp
    May 3 '16 at 11:15

15 Answers 15

9
\$\begingroup\$

Mathematica, 29 bytes

BetaRegularized[#3,#,1+#2-#]&

Takes input in the order n,m,p. Mathematica is so good, it even golfs your code for you:

enter image description here

BetaRegularized is the regularised incomplete beta function.

\$\endgroup\$
6
\$\begingroup\$

R, 32 31 bytes

function(p,n,m)pbeta(p,m,1+n-m)

edit - 1 byte switching to beta distribution (along the lines of @Sp3000 Mathematica Answer)

\$\endgroup\$
3
\$\begingroup\$

Python, 57 bytes

f=lambda p,n,m:m and(1-p)*f(p,n,m-1)+p*f(p,n-1,m-1)or n<1

The recursive formula for binomial coefficients, except the base case m==0 indicates whether the remaining number of required successes n is nonnegative, with True/False for 1/0. Because of its exponential recursion tree, this stalls on large inputs.

\$\endgroup\$
2
  • \$\begingroup\$ To test out this answer for large cases, add caching using from functools import lru_cache; f = lru_cache(None)(f). \$\endgroup\$
    – orlp
    May 3 '16 at 12:15
  • \$\begingroup\$ @orlp Thanks, I confirmed the large test cases. \$\endgroup\$
    – xnor
    May 3 '16 at 12:23
3
\$\begingroup\$

Haskell, 73 bytes

g x=product[1..x];f p n m=sum[g m/g k/g(m-k)*p**k*(1-p)**(m-k)|k<-[n..m]]
\$\endgroup\$
3
\$\begingroup\$

MATLAB, 78 71 bytes

Saved 7 bytes thanks to Luis Mendo!

@(m,k,p)sum(arrayfun(@(t)prod((1:m)./[1:t 1:m-t])*p^t*(1-p)^(m-t),k:m))

ans(100,10,0.1)
0.5487

The arrayfun function is no fun, but I haven't found a way to get rid of it...

\$\endgroup\$
0
3
\$\begingroup\$

Jelly, 15 14 bytes

2ṗ’S<¥ÐḟCạ⁵P€S

Reads m, n and p (in that order) as command-line arguments. Try it online!

Note that this approach requires O(2m) time and memory, so it isn't quite efficient enough for the test cases where m = 100. On my machine, the test case (m, n, p) = (20, 13, 0.5) takes roughly 100 seconds. It requires too much memory for the online interpreter.

How it works

2ṗ              Cartesian product; yield all vectors of {1, 2}^n.
  ’             Decrement, yielding all vectors of {0, 1}^n.
      Ðḟ        Filter; keep elements for which the link to the left yields False.
     ¥          Combine the two links to the left into a dyadic chain.
   S              Sum, counting the number of ones.
    <             Compare the count with n. 
        C       Complement; map z to 1 - z.
         ạ⁵     Compute the absolute difference with p.
           P€   Compute the product of each list.
             S  Compute the sum of all products.
\$\endgroup\$
1
\$\begingroup\$

Pyth, 26 bytes

AQJEsm**.cHd^Jd^-1J-HdrGhH

Try it online!

Uses standard cumulative binomial distribution.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 20 bytes

JEKEcsmgsm<O0QKJCGCG

Try it online!

Note: CG is a very large number which the interpreter cannot handle. Therefore, the number of trials have been lowered to ^T3 which is one thousand. Therefore, the link produces an inaccurate result.

Uses pure probabilistic approach.

\$\endgroup\$
14
  • \$\begingroup\$ I don't think a probabilistic approach would be valid for this question, but we'd have to ask @orlp \$\endgroup\$
    – Sp3000
    May 3 '16 at 11:21
  • \$\begingroup\$ You need on the order of 1/c^2 trials to get within accuracy c with high probability, so that would be ~10^10 for five decimal places. \$\endgroup\$
    – xnor
    May 3 '16 at 11:24
  • \$\begingroup\$ CG is a very large number. In fact, it is the string "abc...z" converted from base-256 to decimal. \$\endgroup\$
    – Leaky Nun
    May 3 '16 at 11:26
  • 2
    \$\begingroup\$ If "probabilstic" means random, you can't guarante an accurate value, no matter how many realizations you average. In fact, the result is different every time. \$\endgroup\$
    – Luis Mendo
    May 3 '16 at 14:29
  • 2
    \$\begingroup\$ There is always a nonzero probability that the result is not accurate to 5 decimal places. Therefore it doesn't fulfill the requirement Your answer must be precise to at least 5 digits \$\endgroup\$
    – Luis Mendo
    May 3 '16 at 14:38
1
\$\begingroup\$

JavaScript (ES7), 82 bytes

(p,n,m)=>[...Array(++m)].reduce((r,_,i)=>r+(b=!i||b*m/i)*p**i*(1-p)**--m*(i>=n),0)

Saved 1 byte by using reduce! Explanation:

(p,n,m)=>               Parameters
 [...Array(++m)].       m+1 terms
  reduce((r,_,i)=>r+    Sum
   (b=!i||b*m/i)*       Binomial coefficient
   p**i*(1-p)**--m*     Probability
   (i>=n),              Ignore first n terms
   0)
\$\endgroup\$
1
\$\begingroup\$

Octave, 26 bytes

@(p,n,m)1-binocdf(n-1,m,p)

This is an anonymous function. To use it, assign it to a variable.

Try it here.

\$\endgroup\$
1
\$\begingroup\$

MATL, 23 bytes

y2$:Xni5M^1IG-lG7M-^**s

Inputs are in the order m, n, p.

Try it online!

This does a direct computation summing the terms from n to m of the binomial probability (mass) function.

\$\endgroup\$
0
1
\$\begingroup\$

Jelly, 18 17 bytes

⁵C*ạ×⁵*¥×c@
R’çSC

Reads n, m and p (in that order) as command-line arguments. Try it online!

\$\endgroup\$
0
\$\begingroup\$

TI-Basic, 17 bytes

Precise to 10 decimals, could be adjusted anywhere from 0-14 decimals with more code.

Prompt P,N,M:1-binomcdf(M,P,N-1
\$\endgroup\$
0
\$\begingroup\$

Haskell, 54 bytes

(p%n)m|m<1=sum[1|n<1]|d<-m-1=(1-p)*(p%n)d+p*(p%(n-1))d

Defines a function (%). Call it like (%) 0.4 2 3.

\$\endgroup\$
1
  • \$\begingroup\$ n<1 instead of n<=0. \$\endgroup\$
    – Damien
    May 4 '16 at 6:49
0
\$\begingroup\$

Mathematica, 48 bytes

Sum[s^k(1-s)^(#3-k)#3~Binomial~k,{k,##2}]/.s->#&

Uses the binomial distribution probability formula to calculate the chance of k successes for k from n to m. Handles the edge cases by using a symbolic sum where s is a symbolic variable for the probability that is later replaced with the actual value p. (Since s0 = 1 but 00 is indeterminate.)

Example

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.