Szukając $p$ binomcdf $(n,p,k)$= $x$

Question

W przypadku prawdopodobieństwa dwumianowego z nieznanym p jest to wykonywane dla przypadku, w którym$n=0$, co ostatecznie okazuje się prostym rozwiązaniem. Z$n > 0$, rzeczy nie są takie proste, próba naiwnego bezpośredniego rozwiązania prowadzi do coraz wyższych równań mocy.

Np. Rozwiązywanie $\text{binomcdf}(17,p,8) = 0.3$ (Prawdopodobieństwo 8 lub mniej sukcesów wynosi dokładnie 0,3) jest wypisane;

$$\sum^{8}_{n=0}\binom{17}{n} p^n(1-p)^{17-n} = 0.3$$

To jest wielomian bardzo wysokiego stopnia. Jaki byłby dobry sposób na rozwiązanie lub w sposób stabilny numerycznie przybliżenie rozwiązania z dowolną dokładnością takiego równania?

W szczególności motywuje mnie następujący problem:

Niech będzie $n$członków parlamentu. Istnieją 3 środki zaproponowane tej władzy ustawodawczej. Pierwsza miara, która przeszła, unieważnia pozostałe. Ustawodawca jednogłośnie pragnie, aby do każdego środka był wprowadzony jeden środek, aby mieć równe szanse na przyjęcie, ale każdy członek ma kontrolę tylko nad własnym głosem. W przypadku parlamentu o numerach parzystych głosowanie zawieszone oznacza nieudany środek.

Członkowie decydują o pewnym prawdopodobieństwie nash $p_1$ dla których szansa na zaliczenie miary jest $\frac{1}{3}$ i kolejny $p_2$ na szansę $\frac{1}{2}$, przy czym ostatni środek zawsze jest jednomyślny. Jakie to wartości?

Rozwiązaniem byłoby rozwiązanie równań

$$\text{binomcdf}(n,p_1,\lfloor\frac{n}{2}\rfloor) = \sum^{\lfloor\frac{n}{2}\rfloor}_{k=0} \binom{n}{k}p_1^k(1-p_1)^{n-k} = \frac{1}{3}$$

$$\text{binomcdf}(n,p_2,\lfloor\frac{n}{2}\rfloor) = \sum^{\lfloor\frac{n}{2}\rfloor}_{k=0} \binom{n}{k}p_2^k(1-p_2)^{n-k} = \frac{1}{2}$$

odpowiednio $p_1$ i $p_2$.

Dla nieparzystych wartości $n$ oraz przypadek, w którym istnieje prawdopodobieństwo docelowe $\frac{1}{2}$istnieje proste rozwiązanie, $p_2 = 0.5$i to jest jedyna odpowiedź.

Do tej pory po prostu zastosowałem arkusz kalkulacyjny, bawiąc się wartością $p_1$ dopóki nie zbliżę się do upragnionej szansy, ale zastanawiam się, czy istnieje bardziej ogólna metoda.

Answer 1

Będą metody numeryczne, ale jeśli chcesz przybliżenia, w którym chcesz uzyskać docelowe prawdopodobieństwo $t$ [$t=0.3$ w Twoim $\text{binomcdf}(17,p,8) = 0.3$ przykład] z $k$ lub mniej sukcesów z $n$ [$k=8$ i $n=17$ w twoim przykładzie], możesz wypróbować normalne przybliżenie z poprawką ciągłości do rozwiązania

$$\Phi\left(\frac{k+\frac12-np}{\sqrt{np(1-p)}}\right)=t$$ co daje kwadrat z rozwiązaniem $$p \approx \frac{2\left(k+\frac12\right)+\Phi^{-1}(t)^2 \pm \sqrt{\left(2\left(k+\frac12\right)+\Phi^{-1}(t)^2\right)^2-4\left(n+\Phi^{-1}(t)^2\right)\frac{\left(k+\frac12\right)^2}{n}}}{2\left(n+\Phi^{-1}(t)^2\right)}$$

W twoim przykładzie to daje $ p \approx 0.4369153$ lub $0.5630847$. Chcesz większą wartość (wybierając$+$ dla $\pm$), ponieważ drugi jest fałszywy i odpowiada przypadkowi zaczynającemu się od $t=0.7$ .

Jak dobrze $p \approx 0.5630847$? Umieszczenie go z powrotem w sumie dwumianowej daje około$0.2980416$ zamiast $0.3$, więc nieźle w tym przypadku. Dokładna żądana wartość$p$ to koniec $0.56241865$ więc znowu przybliżenie nie jest dalekie.

Answer 2

Jeśli chodzi o pierwsze pytanie, mając nadzieję, że rozwiązanie, którego szukasz, nie jest bliskie granic, wypróbuj rozszerzenie serii wokół $p=\frac 12$. To dałoby za$$f(p)=\sum^{8}_{n=0}\binom{17}{n} p^n(1-p)^{17-n}$$ $$f(p)=\frac{1}{2}-\frac{109395 }{32768}\left(p-\frac{1}{2}\right)+\frac{36465 }{1024} \left(p-\frac{1}{2}\right)^3-\frac{153153}{512} \left(p-\frac{1}{2}\right)^5+\frac{109395}{64} \left(p-\frac{1}{2}\right)^7-\frac{425425}{64} \left(p-\frac{1}{2}\right)^9+O\left(\left(p-\frac{1}{2}\right)^{11}\right)$$Teraz, używając odwrócenia serii, przybliżenie $$p_{(m)}=\frac 1 2+\sum_{n=1}^m \frac {a_n}{b_n}\left(k-\frac{1}{2}\right)^{2n-1}$$

Próbuję $k=\frac 3{10}$ dałoby to następujące szacunki $$\left( \begin{array}{cc} m & p_{(m)} \\ 1 & 0.559908 \\ 2 & 0.562201 \\ 3 & 0.562395 \\ 4 & 0.562416 \end{array} \right)$$ podczas gdy „dokładne” rozwiązanie jest $0.562419$.

Answer 3

Jak wskazuje Felix Marin , mamy ograniczenia, kiedy mamy$\operatorname{binomcdf}(n,p,k)-t$ znak zmian nadany przez $p=0$ i $p=1$, więc można bezpiecznie wypróbować metody tworzenia nawiasów, aby uzyskać szybką i gwarantowaną zbieżność. Możesz chcieć wypróbować metodę Brenta, metodę Chandrupatli, a nawet metodę Newtona-Raphsona, ponieważ pochodna jest znana.

Jedynym pozostałym problemem jest to, że możesz uzyskać powolną zbieżność, jeśli pożądana wartość jest blisko granicy, gdzie cdf staje się bardzo płaski. Można to zrobić za pomocą symetrii wraz z asymptotycznym zachowaniem w pobliżu obu$0$ lub $1$. Dla$0<k<n-1$:

$$\operatorname{binomcdf}(n,p,k)\approx\binom nk(1-p)^{n-k},\quad p\approx1\\\operatorname{binomcdf}(n,p,k)\approx1-\binom n{k+1}p^{k+1},\quad p\approx0$$

Na przykład $\operatorname{binomcdf}(17,p,8)=0.3$, te przybliżenia można rozwiązać, aby dać

$$0.313\le p\le0.715$$

która jest bliższa dokładniejszej $p=0.56241865$.

Zobacz tutaj implementację przy użyciu metody Chandrupatli.