1
$\begingroup$

I have the following function I want to be able to feed into the Newton-Rhapson root solving algorithm (C++ boost), since an analytical solution is not possible:$$f(p, k, n, Pr)=\left(\sum_{i = 0}^{\lfloor k \rfloor} \binom{n}{i}p^i(1 - p)^{n-i}\right)-Pr$$ $k, n, Pr$ are known values to be plugged in, and $p$ will be found by finding for what value of $p$ does $f(p,k,n,Pr) = 0$.

I know there are several methods of root finding, some use derivatives and some don't. I want to try to use the Newton algorithm as it's one I understand and one I believe works for this purpose. If you plot the function, the x axis goes between 0 and 1, and the line looks something like a backwards s, which can be stretched or squashed and so on depending on what values are fed into it.

For the root finder I need to be able to calculate the first derivative of the function, which I understand the method uses to make it's next 'guess' as it homes in on the root. Calculus has always eluded me quite a bit - I understand in principle from reading the derivative is the instantaneous rate of change and can be visualized as a tangent line that touches the point on the curve. I've read texts that deal with examples and present simple rules like if $f(x) = x^2$, then the derivative is $2x$. However with a function this complex I'm really not sure where to begin figuring out the first derivative. What's the best way to do this?

Thanks, Ben W.

$\endgroup$
  • $\begingroup$ If you want to learn more about the math, have a look at Binomial theorem wiki. It looks like your function $f$ "selects" values up to order $k$ from the expansion of $(x+y)^n$, where $x=p$, and $y=1-p$. Especially, for $n=k$, you get $f(p,k,k,Pr) = \sum_{i=0}^k{k \choose i}p^i(1-p)^{k-1} - Pr = (p+(1-p))^k - Pr = 1-Pr$. Is $f$ perhaps some function describing the probability distribution between two possible outcomes? $\endgroup$ – fromGiants Jun 23 '14 at 15:51
  • $\begingroup$ In any manner, when you cannot have the analytical derivative or when its cost is much higher than the cost of the function, you can compute numerical derivatives. However, in the presnt case, it is not necessary from the answers. $\endgroup$ – Claude Leibovici Jun 23 '14 at 16:02
  • $\begingroup$ The function is simply the CDF of the binomial probability distribution but subtracting the $Pr(X\leq{k})$ from the result such that finding the 0 with a root finder returns $p$. $\endgroup$ – Ward9250 Jun 23 '14 at 17:57
2
$\begingroup$

Your expression is a sum of terms. Derivative of a sum is the sum of the derivatives.

Every term is a constant times the product of two factors, $p^i$ and $(1-p)^{n-i}$. The derivative of a product given by the product rule $(UV)'=U'V+UV'$.

Both factors are powers of $p$. The rule for powers is $(p^n)'=np^{n-1}$. (More generally, $((ap+b)^n)'=na(ap+b)^{n-1}$).

Put together, you get $$\sum_{i = 0}^{\lfloor k \rfloor} \binom{n}{i}[ip^{i-1}(1 - p)^{n-i}-(n-i)p^i(1 - p)^{n-i-1}].$$

$\endgroup$
  • $\begingroup$ I think I follow you almost all the way, the two factors are $p^i$ and $(1-p)^{n-i}$, so for the product rule $U = p^i$ and $V=(1-p)^{n-i}$, therefore $U'=ip^{i-1}$ and $V' = (1-p)^{n-i-1}$ therefore $U'V = ip^{i-1}(1-p)^{n-i}$, but after the - sign I start to get lost, I follow that $UV' = (1-p)^{n-i-1}p^i$ or in the answer you give $p^i(1-p)^{n-i-1}$, but then I get a bit lost as to where the $(n-i)$ comes from between the minus sign and $p^i(1-p)^{n-i-1}$ I'm also uncertain as to why there is a $-$ and not a $+$ but I have a feeling it's because the second factor has a minus in it. $\endgroup$ – Ward9250 Jun 23 '14 at 17:38
  • 1
    $\begingroup$ In $(1-p)$, you have $a=-1, b=1$. Just apply all transforms mechanically. $\endgroup$ – Yves Daoust Jun 23 '14 at 17:54
  • $\begingroup$ This is where I might start to look stupid; so for the general rule you list above $((ap + b)^n)$ for $(1-p)^n$ is $(-1p + 1)^n$ and becomes $n-1(-1p+1)^{n-i}$ ? $\endgroup$ – Ward9250 Jun 23 '14 at 18:22
  • 1
    $\begingroup$ Take $n\rightarrow n-i, a\rightarrow -1, b\rightarrow 1$ and substitute. $\endgroup$ – Yves Daoust Jun 23 '14 at 22:32
  • 1
    $\begingroup$ "$(-1p+1)^{n-i-1}$ can be rewritten as $(1-p)^{n-i-1}$ ": isn't it plain obvious ? $\endgroup$ – Yves Daoust Jun 24 '14 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.