Distribuição de probabilidade para diferentes probabilidades

36

Se eu quisesse obter a probabilidade de 9 sucessos em 16 tentativas, com cada tentativa tendo 0,6 de probabilidade, eu poderia usar uma distribuição binomial. O que eu poderia usar se cada uma das 16 tentativas tivesse uma probabilidade diferente de sucesso?

Greg
fonte
11
@whuber Na sua explicação sobre a aproximação Normal, os cálculos de média e desvio padrão são diferentes com a descrição na Wikipedia. No Wiki, a média é np e o desvio padrão é np (1-p). Portanto, neste problema, para a aproximação normal de probabilidade variável de sucesso na distribuição binomial, a média é p1 + p2 + p3 + p4 + p5 + ... + pi, e a variação é p1 (1-p1) + p2 ( 1-p2) + ... + pi (1-pi). Estou certo?
David David
11
Veja a Wikipedia sobre a distribuição binomial de Poisson . Também um termo de pesquisa que mostra alguns hits aqui.
Glen_b -Reinstate Monica
@ David Quando todo o pi são iguais a um valor comum p , em seguida, p1+p2++pn=np e p1(1p1)++pn(1pn)=np(1p) , mostrando que a descrição da Wikipedia a que você se refere é apenas um caso especial.
whuber

Respostas:

22

Esta é a soma de 16 ensaios binomiais (presumivelmente independentes). A suposição de independência nos permite multiplicar probabilidades. Portanto, após duas tentativas com probabilidades p1 e p2 de sucesso, a chance de sucesso em ambas as tentativas é p1p2 , a chance de sucesso não é (1p1)(1p2) e a chance de sucesso um sucesso é p1(1p2)+(1p1)p2 . Essa última expressão deve sua validade ao fato de que as duas maneiras de obter exatamente um sucesso são mutuamente exclusivas: no máximo uma delas pode realmente acontecer. Isso significa que suas probabilidadesaumentam.

Por meio dessas duas regras - as probabilidades independentes se multiplicam e as mutuamente exclusivas - você pode descobrir as respostas para, digamos, 16 tentativas com probabilidades p1,,p16 . Para fazer isso, você precisa explicar todas as maneiras de obter cada número determinado de sucessos (como 9). Existem (169)=11440maneiras de alcançar 9 sucessos. Um deles, por exemplo, ocorre quando os ensaios 1, 2, 4, 5, 6, 11, 12, 14 e 15 são sucessos e os outros são fracassos. Os sucessos tiveram probabilidadesp1,p2,p4,p5,p6,p11,p12,p14,ep15 e as falhas tinha probabilidades1p3,1p7,,1p13,1p16 . A multiplicação desses 16 números dá a chancedessa sequência específica de resultados. A soma desse número, juntamente com os 11.439 restantes, fornece a resposta.

Claro que você usaria um computador.

Com muitos mais de 16 ensaios, é necessário aproximar a distribuição. Nenhum fornecido da probabilidade pi e 1pi ficar muito pequeno, uma aproximação normal tende a funcionar bem. Com esse método, você observa que a expectativa da soma de n tentativas é μ=p1+p2++pn e (porque as tentativas são independentes) a variação é σ2=p1(1p1)+p2(1p2)++pn(1pn) . Você então finge que a distribuição de somas é Normal com médiaμ e desvio padrãoσ . As respostas tendem a ser boas para calcular probabilidades correspondentes a uma proporção de sucessos que difere deμ por não mais do que alguns múltiplos deσ . À medida quen cresce, essa aproximação fica ainda mais precisa e funciona para múltiplos ainda maiores deσ deμ .

whuber
fonte
9
Os cientistas da computação chamam esses "ensaios de Poisson" para diferenciá-los dos ensaios de Bernoulli. Além das aproximações do Teorema do Limite Central, também existem bons limites de cauda disponíveis. Aqui está um. As pesquisas do Google em "Limites de Chernoff para ensaios de Poisson" exibirão os resultados que você pode encontrar em um tratamento típico de CS.
cardinal
@ Cardinal Essa nomenclatura é interessante. Seria válido para muito pequeno pi , mas por outro lado parece enganosa, porque a distribuição de outra forma não é bem aproximadas por distribuições de Poisson. (Há uma outra discussão sobre CV sobre esta questão, onde "16" é substituído por 10.000 e fazemos examinar as probabilidades de cauda, mas eu não tenho sido capaz de encontrá-lo novamente.)
whuber
11
sim, eu concordo com o nome. Achei um pouco estranho quando o encontrei. Dei aqui mais como um termo útil para pesquisa. Parece que os cientistas da computação consideram essas probabilidades frequentemente ao lidar com certos algoritmos. Eu estaria interessado em ler essa outra pergunta, se você a encontrar. É este aquiTalvez ?
cardeal
2
@ cardinal está certo que nós, "CS pessoal", os chamamos de ensaios de Poisson. de fato, neste caso, um limite padrão de Chernoff-Hoeffding fornecerá exatamente o limite que o OP está solicitando.
Suresh Venkatasubramanian
11
De acordo com o comentário de @David ontem, há algo errado com sua afirmação da média aproximada Normal como Estamos somando 16 Bernoulli rvs, cada um dos quais pode levar valor 0 ou 1, para que a soma tenha domínio de suporte de 0 a 16, não entre 0 e 1. Vale a pena conferir também o seu sd.
μ=(p1+p2++pn)/n
wolfies
12

Uma alternativa à aproximação normal do @ whuber é usar probabilidades de "mistura" ou um modelo hierárquico. Isso se aplica quando o são similares de alguma maneira, e você pode modelar este por uma distribuição de probabilidade p i ~ D i s t ( θ ) com uma função de densidade de g ( p | θ ) indexados por algum parâmetro θ . você obtém uma equação integral:pipiDist(θ)g(p|θ)θ

Pr(s=9|n=16,θ)=(169)01p9(1p)7g(p|θ)dp

A probabilidade binomial vem da configuração , a aproximação normal vem da (acho) configuração g ( p | θ ) = g ( p | μ , σ ) = 1g(p|θ)=δ(pθ)(comμeσconforme definido na resposta do @ whuber) e, em seguida, observando que as "caudas" deste PDF caem acentuadamente em torno do pico.g(p|θ)=g(p|μ,σ)=1σϕ(pμσ)μσ

Você também pode usar uma distribuição beta, o que levaria a uma forma analítica simples e que não precisará sofrer do problema do "pequeno p" que a aproximação normal faz - já que o beta é bastante flexível. Usando uma distribuição com α , β definida pelas soluções para as seguintes equações (estas são as estimativas de "divergência mínima de KL"):beta(α,β)α,β

ψ(α)ψ(α+β)=1ni=1nlog[pi]
ψ(β)ψ(α+β)=1ni=1nlog[1pi]

Where ψ(.) is the digamma function - closely related to harmonic series.

We get the "beta-binomial" compound distribution:

(169)1B(α,β)01p9+α1(1p)7+β1dp=(169)B(α+9,β+7)B(α,β)

This distribution converges towards a normal distribution in the case that @whuber points out - but should give reasonable answers for small n and skewed pi - but not for multimodal pi, as beta distribution only has one peak. But you can easily fix this, by simply using M beta distributions for the M modes. You break up the integral from 0<p<1 into M pieces so that each piece has a unique mode (and enough data to estimate parameters), and fit a beta distribution within each piece. then add up the results, noting that making the change of variables p=xLUL for L<x<U the beta integral transforms to:

B(α,β)=LU(xL)α1(Ux)β1(UL)α+β1dx
probabilityislogic
fonte
+1 This answer contains some interesting and clever suggestions. The last one looks particularly flexible and powerful.
whuber
Just to take something very simple and concrete, suppose (i) pi=i17 and (ii) pi=i/17, for i=1 to 16. What would be the solution to your α and β estimates, and thus your estimates for P(X=9) given n=16, as per the OP's problem?
wolfies
Great answer and proposal, especially the beta! It'd be cool to see this answer written in its general form with n and s.
pglpm
8

Let Xi ~ Bernoulli(pi) with probability generating function (pgf):

pgf=E[tXi]=1pi(1t)

Let S=i=1nXi denote the sum of n such independent random variables. Then, the pgf for the sum S of n=16 such variables is:

pgfS=E[tS]=E[tX1]E[tX2]E[tX16] (... by independence)=i=116(1pi(1t))

We seek P(S=9), which is:

19!d9pgfSdt9|t=0

ALL DONE. This produces the exact symbolic solution as a function of the pi. The answer is rather long to print on screen, but it is entirely tractable, and takes less than 1100th of a second to evaluate using Mathematica on my computer.

Examples

If pi=i17,i=1 to 16, then: P(S=9)=964794185433480818448661191875666868481=0.198268

If pi=i17,i=1 to 16, then: P(S=9)=0.000228613

More than 16 trials?

With more than 16 trials, there is no need to approximate the distribution. The above exact method works just as easily for examples with say n=50 or n=100. For instance, when n=50, it takes less than 110th of second to evaluate the entire pmf (i.e. at every value s=0,1,,50) using the code below.

Mathematica code

Given a vector of pi values, say:

n = 16;   pvals = Table[Subscript[p, i] -> i/(n+1), {i, n}];

... here is some Mathematica code to do everything required:

pgfS = Expand[ Product[1-(1-t)Subscript[p,i], {i, n}] /. pvals];
D[pgfS, {t, 9}]/9! /. t -> 0  // N

0.198268

To derive the entire pmf:

Table[D[pgfS, {t,s}]/s! /. t -> 0 // N, {s, 0, n}]

... or use the even neater and faster (thanks to a suggestion from Ray Koopman below):

CoefficientList[pgfS, t] // N

For an example with n=1000, it takes just 1 second to calculate pgfS, and then 0.002 seconds to derive the entire pmf using CoefficientList, so it is extremely efficient.

wolfies
fonte
1
It can be even simpler. With[{p = Range@16/17}, N@Coefficient[Times@@(1-p+p*t),t,9]] gives the probability of 9 successes, and With[{p = Range@16/17}, N@CoefficientList[Times@@(1-p+p*t),t]] gives the probabilities of 0,...,16 successes.
Ray Koopman
@RayKoopman That is cool. The Table for the p-values is intentional to allow for more general forms not suitable with Range. Your use of CoefficientList is very nice! I've added an Expand to the code above which speeds the direct approach up enormously. Even so, CoefficientList is even faster than a ParallelTable. It does not make much difference for n under 50 (both approaches take just a tiny fraction of a second either way to generate the entire pmf), but your CoefficientList will also be a real practical advantage when n is really large.
wolfies
5

@wolfies comment, and my attempt at a response to it revealed an important problem with my other answer, which I will discuss later.

Specific Case (n=16)

There is a fairly efficient way to code up the full distribution by using the "trick" of using base 2 (binary) numbers in the calculation. It only requires 4 lines of R code to get the full distribution of Y=i=1nZi where Pr(Zi=1)=pi. Basically, there are a total of 2n choices of the vector z=(z1,,zn) that the binary variables Zi could take. Now suppose we number each distinct choice from 1 up to 2n. This on its own is nothing special, but now suppose that we represent the "choice number" using base 2 arithmetic. Now take n=3 so I can write down all the choices so there are 23=8 choices. Then 1,2,3,4,5,6,7,8 in "ordinary numbers" becomes 1,10,11,100,101,110,111,1000 in "binary numbers". Now suppose we write these as four digit numbers, then we have 0001,0010,0011,0100,0101,0110,0111,1000. Now look at the last 3 digits of each number - 001 can be thought of as (Z1=0,Z2=0,Z3=1)Y=1, etc. Counting in binary form provides an efficient way to organise the summation. Fortunately, there is an R function which can do this binary conversion for us, called intToBits(x) and we convert the raw binary form into a numeric via as.numeric(intToBits(x)), then we will get a vector with 32 elements, each element being the digit of the base 2 version of our number (read from right to left, not left to right). Using this trick combined with some other R vectorisations, we can calculate the probability that y=9 in 4 lines of R code:

exact_calc <- function(y,p){
    n       <- length(p)
    z       <- t(matrix(as.numeric(intToBits(1:2^n)),ncol=2^n))[,1:n] #don't need columns n+1,...,32 as these are always 0
    pz      <- z%*%log(p/(1-p))+sum(log(1-p))
    ydist   <- rowsum(exp(pz),rowSums(z))
    return(ydist[y+1])
}

Plugging in the uniform case pi(1)=i17 and the sqrt root case pi(2)=i17 gives a full distribution for y as:

yPr(Y=y|pi=i17)Pr(Y=y|pi=i17)00.00000.055810.00000.178420.00030.265230.00260.243040.01390.153650.04910.071060.11810.024870.19830.006780.23530.001490.19830.0002100.11810.0000110.04910.0000120.01390.0000130.00260.0000140.00030.0000150.00000.0000160.00000.0000

So for the specific problem of y successes in 16 trials, the exact calculations are straight-forward. This also works for a number of probabilities up to about n=20 - beyond that you are likely to start to run into memory problems, and different computing tricks are needed.

Note that by applying my suggested "beta distribution" we get parameter estimates of α=β=1.3206 and this gives a probability estimate that is nearly uniform in y, giving an approximate value of pr(y=9)=0.06799117. This seems strange given that a density of a beta distribution with α=β=1.3206 closely approximates the histogram of the pi values. What went wrong?

General Case

I will now discuss the more general case, and why my simple beta approximation failed. Basically, by writing (y|n,p)Binom(n,p) and then mixing over p with another distribution pf(θ) is actually making an important assumption - that we can approximate the actual probability with a single binomial probability - the only problem that remains is which value of p to use. One way to see this is to use the mixing density which is discrete uniform over the actual pi. So we replace the beta distribution pBeta(a,b) with a discrete density of pi=116wiδ(ppi). Then using the mixing approximation can be expressed in words as choose a pi value with probability wi, and assume all bernoulli trials have this probability. Clearly, for such an approximation to work well, most of the pi values should be similar to each other. This basically means that for @wolfies uniform distribution of values, pi=i17 results in a woefully bad approximation when using the beta mixing distribution. This also explains why the approximation is much better for pi=i17 - they are less spread out.

The mixing then uses the observed pi to average over all possible choices of a single p. Now because "mixing" is like a weighted average, it cannot possibly do any better than using the single best p. So if the pi are sufficiently spread out, there can be no single p that could provide a good approximation to all pi.

One thing I did say in my other answer was that it may be better to use a mixture of beta distributions over a restricted range - but this still won't help here because this is still mixing over a single p. What makes more sense is split the interval (0,1) up into pieces and have a binomial within each piece. For example, we could choose (0,0.1,0.2,,0.9,1) as our splits and fit nine binomials within each 0.1 range of probability. Basically, within each split, we would fit a simple approximation, such as using a binomial with probability equal to the average of the pi in that range. If we make the intervals small enough, the approximation becomes arbitrarily good. But note that all this does is leave us with having to deal with a sum of indpendent binomial trials with different probabilities, instead of Bernoulli trials. However, the previous part to this answer showed that we can do the exact calculations provided that the number of binomials is sufficiently small, say 10-15 or so.

To extend the bernoulli-based answer to a binomial-based one, we simply "re-interpret" what the Zi variables are. We simply state that Zi=I(Xi>0) - this reduces to the original bernoulli-based Zi but now says which binomials the successes are coming from. So the case (Z1=0,Z2=0,Z3=1) now means that all the "successes" come from the third binomial, and none from the first two.

Note that this is still "exponential" in that the number of calculations is something like kg where g is the number of binomials, and k is the group size - so you have Yj=1gXj where XjBin(k,pj). But this is better than the 2gk that you'd be dealing with by using bernoulli random variables. For example, suppose we split the n=16 probabilities into g=4 groups with k=4 probabilities in each group. This gives 44=256 calculations, compared to 216=65536

By choosing g=10 groups, and noting that the limit was about n=20 which is about 107 cells, we can effectively use this method to increase the maximum n to n=50.

If we make a cruder approximation, by lowering g, we will increase the "feasible" size for n. g=5 means that you can have an effective n of about 125. Beyond this the normal approximation should be extremely accurate.

probabilityislogic
fonte
@momo - I think this is ok, as my answers are two different ways to approach the problem. This answer is not an edited version of my first one - it is just a different answer
probabilityislogic
1
For a solution in R that is extremely efficient and handles much, much larger values of n, please see stats.stackexchange.com/a/41263. For instance, it solved this problem for n=104, giving the full distribution, in under three seconds. (A comparable Mathematica 9 solution--see @wolfies' answer--also performs well for smaller n but could not complete the execution with such a large value of n.)
whuber
5

The (in general intractable) pmf is

Pr(S=k)=A{1,,n}|A|=k(iApi)(j{1,,n}A(1pj)).
R code:
p <- seq(1, 16) / 17
cat(p, "\n")
n <- length(p)
k <- 9
S <- seq(1, n)
A <- combn(S, k)
pr <- 0
for (i in 1:choose(n, k)) {
    pr <- pr + exp(sum(log(p[A[,i]])) + sum(log(1 - p[setdiff(S, A[,i])])))
}
cat("Pr(S = ", k, ") = ", pr, "\n", sep = "")

For the pi's used in wolfies answer, we have:

Pr(S = 9) = 0.1982677

When n grows, use a convolution.

Zen
fonte
1
Doing that with R code was really helpful. Some of us are more concrete-thinkers and it greatly helps to have an operational version of the generating function.
DWin
@DWin I provide efficient R code in the solution to the same problem (with different values of the pi) at stats.stackexchange.com/a/41263. The problem here is solved in 0.00012 seconds total computation time (estimated by solving it 1000 times) compared to 0.53 seconds (estimated by solving it once) for this R code and 0.00058 seconds using Wolfies' Mathematica code (estimated by solving it 1000 times).
whuber
So P(S=k) would follow a Poisson-Binomial Distribution.
fccoelho
+1 Very useful post in my attempt at answering this question. I was wondering if using logs is more of a cool mathematical formulation than a real need. I am not too concerned about running times...
Antoni Parellada