Memecahkan $p$ binomcdf $(n,p,k)$= $x$

Question

Dalam Probabilitas Binomial dengan p Tidak Diketahui , ini dilakukan untuk kasus di mana$n=0$, yang akhirnya menjadi solusi sederhana. Dengan$n > 0$, segala sesuatunya tidak sesederhana itu, mencoba menyelesaikan secara naif secara langsung membuat Anda mendapatkan persamaan pangkat yang semakin tinggi.

Misalnya pemecahan $\text{binomcdf}(17,p,8) = 0.3$ (Probabilitas 8 keberhasilan atau kurang tepat 0,3) ditulis;

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

Itu polinomial dengan derajat yang sangat tinggi. Apa cara yang baik untuk menyelesaikannya atau dengan cara yang stabil secara numerik mendekati solusi untuk presisi sembarang dari persamaan semacam itu?

Secara khusus, saya termotivasi oleh masalah berikut:

Biarkanlah terjadi begitu $n$anggota legislatif. Ada 3 langkah yang disarankan untuk legislatif ini. Langkah pertama untuk lulus membatalkan yang lain. Badan legislatif dengan suara bulat ingin satu langkah lulus dengan setiap langkah memiliki peluang yang sama untuk lulus, tetapi setiap anggota hanya memiliki kendali atas suara mereka sendiri. Dalam badan legislatif bernomor genap, pemungutan suara yang digantung berarti tindakan yang gagal.

Anggota memutuskan kemungkinan nash tertentu $p_1$ yang mana peluang untuk lolos suatu ukuran adalah $\frac{1}{3}$ dan lainnya $p_2$ untuk kesempatan $\frac{1}{2}$, dengan ukuran terakhir selalu mendapatkan suara bulat. Apakah nilai-nilai ini?

Solusinya adalah menyelesaikan persamaan

$$\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}$$

untuk masing-masing $p_1$ dan $p_2$.

Untuk nilai ganjil $n$ dan kasus di mana probabilitas targetnya $\frac{1}{2}$, ada solusi sederhana, $p_2 = 0.5$, dan ini satu-satunya jawaban.

Sejauh ini saya hanya menerapkan spreadsheet, mengutak-atik nilai $p_1$ sampai saya mendekati peluang yang diinginkan, tetapi saya bertanya-tanya apakah ada metode yang lebih umum.

Answer 1

Akan ada metode numerik tetapi jika Anda menginginkan perkiraan di mana Anda ingin probabilitas target $t$ [$t=0.3$ di Anda $\text{binomcdf}(17,p,8) = 0.3$ contoh] dengan $k$ atau lebih sedikit keberhasilan dari $n$ [$k=8$ dan $n=17$ dalam contoh Anda], Anda dapat mencoba pendekatan normal dengan koreksi kontinuitas untuk diselesaikan

$$\Phi\left(\frac{k+\frac12-np}{\sqrt{np(1-p)}}\right)=t$$ yang memberikan kuadrat dengan solusi $$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)}$$

Dalam contoh Anda ini memberi $ p \approx 0.4369153$ atau $0.5630847$. Anda menginginkan nilai yang lebih besar (memilih$+$ Untuk $\pm$), karena yang lainnya palsu dan sesuai dengan kasus yang dimulai $t=0.7$ .

Seberapa baik $p \approx 0.5630847$? Menempatkannya kembali dalam jumlah binomial akan menghasilkan$0.2980416$ daripada $0.3$, jadi lumayan dalam kasus ini. Nilai tepat yang diinginkan untuk$p$ sudah berakhir $0.56241865$ jadi sekali lagi perkiraannya tidak jauh.

Answer 2

Mengenai pertanyaan pertama, berharap bahwa solusi yang Anda cari tidak mendekati batas, coba ekspansi seri di sekitar $p=\frac 12$. Ini akan memberi$$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)$$Sekarang, menggunakan pendekatan pengembalian seri $$p_{(m)}=\frac 1 2+\sum_{n=1}^m \frac {a_n}{b_n}\left(k-\frac{1}{2}\right)^{2n-1}$$

Mencoba untuk $k=\frac 3{10}$ ini akan memberikan perkiraan berikut $$\left( \begin{array}{cc} m & p_{(m)} \\ 1 & 0.559908 \\ 2 & 0.562201 \\ 3 & 0.562395 \\ 4 & 0.562416 \end{array} \right)$$ sedangkan solusi "tepat" adalah $0.562419$.

Answer 3

Seperti yang Felix Marin tunjukkan, kami memiliki batasan kapan kami punya$\operatorname{binomcdf}(n,p,k)-t$ perubahan tanda yang diberikan oleh $p=0$ dan $p=1$, sehingga metode bracketing dapat dengan aman dicoba untuk mendapatkan konvergensi yang cepat dan terjamin. Anda mungkin ingin mencoba metode Brent, metode Chandrupatla, atau bahkan metode Newton-Raphson karena turunannya diketahui.

Satu-satunya masalah yang tersisa adalah Anda mungkin mendapatkan konvergensi yang lambat jika nilai yang diinginkan dekat dengan batas, di mana cdf menjadi sangat datar. Ini dapat dilakukan dengan menggunakan simetri bersama dengan perilaku asimtotik di dekatnya$0$ atau $1$. Untuk$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$$

Untuk contoh Anda $\operatorname{binomcdf}(17,p,8)=0.3$, pendekatan ini dapat dipecahkan untuk memberi

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

yang lebih dekat ke lebih tepat $p=0.56241865$.

Lihat di sini untuk implementasi menggunakan metode Chandrupatla.