Вероятность того, что что-то случится хотя бы n из m раз

11

Напишите программу или функцию, которые с учетом вероятности успеха p , числа n и количества испытаний m возвращают шанс по крайней мере n успехов из m испытаний.

Ваш ответ должен быть точным, по крайней мере, до 5 цифр после десятичной дроби.

Тестовые случаи:

 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
источник
3
Не могли бы вы включить формулу для тех из нас, кто не изучал биномиальное распределение?
Утренняя монахиня
2
@KennyLau Извините, это часть проблемы.
orlp

Ответы:

3

Желе , 15 14 байт

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

Читает m , n и p (в этом порядке) в качестве аргументов командной строки. Попробуйте онлайн!

Следует отметить , что такой подход требует O (2 м ) времени и памяти, так что это не вполне достаточно эффективны для тестовых случаев , когда т = 100 . На моей машине контрольный пример (m, n, p) = (20, 13, 0,5) занимает примерно 100 секунд. Это требует слишком много памяти для онлайн-переводчика.

Как это работает

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.
Деннис
источник
6

R, 32 31 байт

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

edit - 1-байтовое переключение на бета-распределение (в соответствии с @ Sp3000 Mathematica Answer)

mnel
источник
3

Python, 57 байт

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

Рекурсивная формула для биномиальных коэффициентов, за исключением базового случая, m==0указывает, является ли оставшееся количество требуемых успехов nнеотрицательным, с True/Falsefor1/0 . Из-за его дерева экспоненциальной рекурсии это останавливается на больших входах.

XNOR
источник
Чтобы проверить этот ответ для больших случаев, добавьте кеширование с помощью from functools import lru_cache; f = lru_cache(None)(f).
orlp
@orlp Спасибо, я подтвердил большие тестовые случаи.
xnor
3

Haskell, 73 байта

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
источник
3

MATLAB, 78 71 байт

Сэкономили 7 байт благодаря Луису Мендо!

@(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

Функция arrayfun неинтересна, но я не нашел способа от нее избавиться ...

Стьюи Гриффин
источник
1

Pyth, 26 байт

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

Попробуйте онлайн!

Использует стандартное кумулятивное биномиальное распределение.

Дрянная Монахиня
источник
1

Pyth, 20 байтов

JEKEcsmgsm<O0QKJCGCG

Попробуйте онлайн!

Примечание: CG - очень большое число, с которым переводчик не может справиться. Поэтому количество испытаний было уменьшено до ^ T3, что составляет тысячу. Таким образом, ссылка дает неточный результат.

Использует чисто вероятностный подход.

Дрянная Монахиня
источник
Я не думаю, что вероятностный подход был бы действительным для этого вопроса, но мы должны были бы спросить @orlp
Sp3000
Вам нужно порядка 1 / c ^ 2 испытаний, чтобы получить точность c с высокой вероятностью, так что это будет ~ 10 ^ 10 для пяти десятичных знаков.
xnor
КГ очень большое количество. Фактически это строка «abc ... z», преобразованная из base-256 в десятичную.
Утренняя монахиня
2
Если «вероятностный» означает случайный, вы не можете гарантировать точное значение, независимо от того, сколько реализаций вы усредняете. На самом деле результат каждый раз разный.
Луис Мендо
2
Всегда существует ненулевая вероятность того, что результат не является точным с точностью до 5 знаков после запятой. Поэтому оно не соответствует требованию. Ваш ответ должен быть точным, по крайней мере, до 5 цифр
Луис Мендо
1

JavaScript (ES7), 82 байта

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

Сохранено 1 байт с помощью reduce! Объяснение:

(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)
Нил
источник
1

Октава, 26 байт

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

Это анонимная функция. Чтобы использовать его, присвойте его переменной.

Попробуй это здесь .

Луис Мендо
источник
0

TI-Basic, 17 байтов

Точность до 10 десятичных знаков, может быть скорректирована в любом месте от 0-14 десятичных знаков с большим количеством кода.

Prompt P,N,M:1-binomcdf(M,P,N-1
Timtech
источник
0

Haskell, 54 байта

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

Определяет функцию (%). Назовите это как (%) 0.4 2 3.

XNOR
источник
n <1 вместо n <= 0.
Дэмиен
0

Mathematica, 48 байтов

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

Использует формулу вероятности биномиального распределения для расчета вероятности k успехов для k от n до m . Обрабатывает крайние случаи, используя символическую сумму, где s - символическая переменная для вероятности, которая впоследствии заменяется фактическим значением p . (Так как s 0 = 1, но 0 0 является неопределенным.)

пример

миль
источник