Prawdopodobieństwo, że coś się wydarzy co najmniej n spośród m razy

11

Napisz program lub funkcję, która przy prawdopodobieństwie sukcesu p , liczbie n i liczbie prób m zwraca szansę na co najmniej n sukcesów spośród m prób.

Twoja odpowiedź musi być dokładna do co najmniej 5 cyfr po przecinku.

Przypadki testowe:

 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
orlp
źródło
3
Czy chciałbyś załączyć formułę do tych z nas, którzy nie badali rozkładu dwumianowego?
Leaky Nun
2
@KennyLau Przepraszamy, to część wyzwania.
lub

Odpowiedzi:

3

Galaretka , 15 14 bajtów

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

Odczytuje m , n i p (w tej kolejności) jako argumenty wiersza poleceń. Wypróbuj online!

Należy zauważyć, że to podejście wymaga O (2 m ), czas i pamięć, tak więc nie jest całkiem skuteczne wystarcza do testów, w którym M = 100 . Na mojej maszynie przypadek testowy (m, n, p) = (20, 13, 0,5) zajmuje około 100 sekund. Wymaga zbyt dużej pamięci dla tłumacza online.

Jak to działa

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.
Dennis
źródło
9

Mathematica, 29 bajtów

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

Pobiera dane wejściowe w kolejności n,m,p. Mathematica jest tak dobra, że ​​nawet dla ciebie gra w golfa:

wprowadź opis zdjęcia tutaj

BetaRegularizedjest uregulowaną niepełną funkcją beta .

Sp3000
źródło
6

R, 32 31 bajtów

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

edycja - 1 bajt przełącza się na dystrybucję beta (zgodnie z @ Sp3000 Mathematica Answer)

mnel
źródło
3

Python, 57 bajtów

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

Formuła rekurencyjna dla współczynników dwumianowych, z wyjątkiem przypadku podstawowego, m==0wskazuje, czy pozostała liczba wymaganych sukcesów njest nieujemna, True/Falsedla1/0 . Ze względu na wykładnicze drzewo rekurencji, zatrzymuje się na dużych nakładach.

xnor
źródło
Aby przetestować tę odpowiedź dla dużych przypadków, dodaj buforowanie za pomocą from functools import lru_cache; f = lru_cache(None)(f).
lub
@orlp Dzięki, potwierdziłem duże przypadki testowe.
xnor
3

Haskell, 73 bajty

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]]
Damien
źródło
3

MATLAB, 78 71 bajtów

Zaoszczędź 7 bajtów dzięki Luisowi 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

Funkcja arrayfun nie jest zabawna, ale nie znalazłem sposobu, aby się jej pozbyć ...

Stewie Griffin
źródło
1

Pyth, 26 bajtów

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

Wypróbuj online!

Wykorzystuje standardowy skumulowany rozkład dwumianowy.

Leaky Nun
źródło
1

Pyth, 20 bajtów

JEKEcsmgsm<O0QKJCGCG

Wypróbuj online!

Uwaga: CG jest bardzo dużą liczbą, której tłumacz nie jest w stanie obsłużyć. Dlatego liczba prób została obniżona do ^ T3, czyli tysiąc. Dlatego link daje niedokładny wynik.

Wykorzystuje podejście czysto probabilistyczne.

Leaky Nun
źródło
Nie sądzę, by podejście probabilistyczne było właściwe dla tego pytania, ale musielibyśmy zapytać @orlp
Sp3000
Potrzebujesz rzędu 1 / c ^ 2 prób, aby osiągnąć dokładność c z dużym prawdopodobieństwem, więc byłoby to ~ 10 ^ 10 dla pięciu miejsc po przecinku.
xnor
CG jest bardzo dużą liczbą. W rzeczywistości jest to ciąg „abc ... z” przekształcony z base-256 na dziesiętny.
Leaky Nun
2
Jeśli „probabilstic” oznacza losowy, nie możesz zagwarantować dokładnej wartości, bez względu na liczbę uśrednionych realizacji. W rzeczywistości wynik jest za każdym razem inny.
Luis Mendo
2
Zawsze istnieje niezerowe prawdopodobieństwo, że wynik nie jest dokładny z dokładnością do 5 miejsc po przecinku. Dlatego nie spełnia wymogu Twoja odpowiedź musi zawierać co najmniej 5 cyfr
Luis Mendo
1

JavaScript (ES7), 82 bajty

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

Zapisano 1 bajt za pomocą reduce! Wyjaśnienie:

(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)
Neil
źródło
1

Oktawa, 26 bajtów

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

To anonimowa funkcja. Aby go użyć, przypisz go do zmiennej.

Wypróbuj tutaj .

Luis Mendo
źródło
1

Galaretka , 18 17 bajtów

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

Odczytuje n , m oraz p (w tej kolejności) jako argumenty wiersza poleceń. Wypróbuj online!

Dennis
źródło
0

TI-Basic, 17 bajtów

Dokładny do 10 miejsc po przecinku, można go dostosować w dowolnym miejscu od 0-14 miejsc po przecinku z większym kodem.

Prompt P,N,M:1-binomcdf(M,P,N-1
Timtech
źródło
0

Haskell, 54 bajty

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

Definiuje funkcję (%). Nazwij to jak (%) 0.4 2 3.

xnor
źródło
n <1 zamiast n <= 0.
Damien
0

Mathematica, 48 bajtów

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

Wykorzystuje wzór prawdopodobieństwa rozkładu dwumianowego do obliczenia szansy k sukcesów dla k od n do m . Obsługuje przypadki brzegowe za pomocą sumy symbolicznej, gdzie s jest zmienną symboliczną dla prawdopodobieństwa, które później jest zastępowane rzeczywistą wartością p . (Ponieważ s 0 = 1, ale 0 0 jest nieokreślone.)

Przykład

mile
źródło