2

I have the equation:

\begin{equation} 1 - (1 - p)(1 - p^2)^{n - 2} = f(n) \end{equation}

where $p$ is a probability (thus $0\le p\le 1$ and, in fact, the l.h.s. of the equation is a probability function on $p$), and $f(n)$ is some function of $n$ such that $0\le f(n)\le 1$; it can be any function. If you want, you can instantiate it to, for example, $f(n)=1/n$. Lastly, $n$ can be any natural value larger than or equal to $2$.

I would like to solve the equation above for $p$. Since I could not manage to find an exact solution myself, I decided to find an upper bound. The value of $p$ that satisfies the equation above is such that

\begin{align} p &\le \sqrt{1 - \exp{\left(\frac{\log{(1 - f(n))}}{n - 1}\right)}} \\ &= \sqrt{1 - \sqrt[n-1]{1 - f(n)}} \end{align}

The proof is short \begin{align*} f(n) &= 1 - (1 - p)(1 - p^2)^{n - 2} \\ 1 - f(n) &= (1 - p)^{n - 1}(1 + p)^{n - 2} \\ \log{(1 - f(n))} &= (n - 1)\log{(1 - p)} + (n - 2)\log{(1 + p)} \\ &\le (n - 1)\log{(1 - p)} + (n - 1)\log{(1 + p)} \end{align*} It follows that \begin{equation*} \frac{\log{(1 - f(n))}}{n - 1} \le \log{(1 - p)} + \log{(1 + p)} = \log{(1 - p^2)} \end{equation*} and thus the inequality above after a few more steps.

How can I find an exact solution of the equation for $p$? If exact solutions are too difficult to obtain, how can I obtain tighter upper bounds?

Thanks!

Lluís Alemany-Puig
  • 254
  • Don't think you can. The best you can do, in my opinion, is to get bounds on p. It might be a little simpler if you let q=1-p and solve for q. – marty cohen Jul 13 '23 at 14:36
  • What cdf is this equation from? – Тyma Gaidash Jul 13 '23 at 15:35
  • Is $f(n)$ supposed to be a pdf of some distribution on ${ 2, 3, 4, 5, ... }$? That is, are we also supposed to assume that $\sum_{n \geq 2}^\infty f(n) = 1$? – Rivers McForge Jul 13 '23 at 20:17
  • The following slowly converges near the root of $f(w)-x=w(1-(1-w)^2)^{n-2}-x$. The Mellin transform of $f^{-1}(w),0\le w\le 1$ is $\int_0^1 f^{-1}(t) t^{s-1}dt=\frac1s-\frac1s\int_0^1 f(t)^s dt$, so using the inverse Mellin transform, $1-p=w\mathop=\limits^?\frac1{2\pi i}\int_{c-i\infty}^{c+i\infty}\frac{x^{-s}}s\left(B_\frac12((n-2)s+1,(n-1)s+1))+\frac{\pi\csc(\pi (n-1)s)((n-2)s+1)!}{((n-2)s+1)((2n-3)s+1)!\Gamma(s(1-n))}+1\right)ds$ with incomplete beta function. Maybe it works? – Тyma Gaidash Jul 14 '23 at 01:21
  • @RiversMcForge, the function $f(n)$ is not supposed to be any function in particular. I've updated the post – Lluís Alemany-Puig Jul 14 '23 at 10:57
  • @TymaGaidash, the l.h.s. of the equation is a probability on Erdos-Renyi graphs; the space for comments is too little to contain the precise definition of the probability and the proof to reach it ;). – Lluís Alemany-Puig Jul 14 '23 at 10:59

4 Answers4

2

Particularly if $n$ is well more than $2$, $p$ will have to be very small. You can get a pretty good approximation by ignoring the $1-p$ factor, which will be quite close to $1$. We can then solve it analytically $$1 -(1 - p^2)^{n - 2} = f(n)\\ (1-p^2)^{n-2}=1-f(n)\\ 1-p^2=\sqrt[n-2]{1-f(n)}\\ p=\sqrt{1-\sqrt[n-2]{1-f(n)}}$$ This should be a good starting value for your favorite root finding method. The factor we ignored can be put back in in the fashion of fixed point iteration as $\frac 1{\sqrt[n-2]{1-p}}$ giving the bounds $$\sqrt{1-\sqrt[n-2]{1-f(n)}}\lt p \lt \sqrt{1-\sqrt[n-2]{1-f(n)}}\frac 1{\sqrt[n-2]{1-\sqrt{1-\sqrt[n-2]{1-f(n)}}}}$$ If these are close enough for your purposes you are done.

Ross Millikan
  • 374,822
2

If $n=2,$ the equation is trivial to solve.
Let's look for a suitable method for $n\ge 3.$ I don't have an exact formula for $p$ as a function of $n,$ but it's not hard to show that the classical Newton's method can be used. The method is fast and provides the closest approximation to $p(n)$ as desired.

Set $t=1-p,$ as suggested in a comment. Clearly, $$0\le p\le1\quad \iff \quad 1\ge t\ge0$$ and $$1 - (1 - p)(1 - p^2)^{n - 2} = f(n) \quad \iff \quad 1 - t^{n-1}(2 -t)^{n - 2} = f(n).$$ For $n\ge 3$ and $t\in[0,1]$ consider $$g_n(t)= - t^{n-1}(2 -t)^{n - 2}+1-f(n).$$

Let us show that each of these functions satisfies the requirements for using Newton's method on $[0,1].$ Assume $0< f(n)< 1.$

  • $g_n$ is continuos and differentiable on $[0,1]$
  • $g_n(0)g_n(1)<0\;,$ because $\;g_n(0)=1-f(n)>0\;$ and $\;g_n(1)=-f(n)<0$
  • the sign of the first derivative is constant on $[0,1]$ as$g_n'(t)=\underbrace{t^{n-2}}_+\underbrace{(2-t)^{n-3}}_+\bigg(\underbrace{t(2n-3)-(2n-2)}_-\bigg)<0$

Therefore, $g_n$ is strictly decreasing and the equation $g_n(t)=0$ has exactly one solution $t(n)$ in the considered interval. Then $p(n)=1-t(n).$

user376343
  • 8,311
2

If we take into account the bounds, the solution is such that $$p ~< ~\sqrt{1-(1-f(n))^{\frac{1}{n-1}}}=p_0$$ So, considering that we look for the zero of function $$F(p)=1 - (1 - p)(1 - p^2)^{n - 2} - f(n)$$ $$F'(p)=\frac{((2 n-3) p+1) \left(1-p^2\right)^{n-2}}{p+1}$$ The first iterate of Newton method $$p_1=p_0-\frac{F(p_0)}{F'(p_0)}$$ would be a rather good approximation.

Some numbers for illustration

  • For $f(n)=0.25$

$$\left( \begin{array}{cccc} n & p_0 & p_1 & \text{solution}\\ 10 & 0.177367 & 0.134584 & 0.133658 \\ 20 & 0.122585 & 0.100773 & 0.100298 \\ 30 & 0.099353 & 0.084589 & 0.084287 \\ 40 & 0.085728 & 0.074533 & 0.074317 \\ 50 & 0.076510 & 0.067479 & 0.067315 \\ \end{array} \right)$$

  • For $f(n)=0.50$

$$\left( \begin{array}{cccc} n & p_0 & p_1 & \text{solution}\\ 10 & 0.272260 & 0.227473 & 0.229416 \\ 20 & 0.189272 & 0.166470 & 0.167175 \\ 30 & 0.153682 & 0.138308 & 0.138692 \\ 40 & 0.132725 & 0.121104 & 0.121353 \\ 50 & 0.118517 & 0.109166 & 0.109344 \\ \end{array} \right)$$

  • For $f(n)=0.75$

$$\left( \begin{array}{cccc} n & p_0 & p_1 & \text{solution}\\ 10 & 0.377831 & 0.334198 & 0.338432 \\ 20 & 0.265263 & 0.242461 & 0.244160 \\ 30 & 0.216052 & 0.200584 & 0.201553 \\ 40 & 0.186873 & 0.175154 & 0.175800 \\ 50 & 0.167019 & 0.157580 & 0.158050 \\ \end{array} \right)$$

It could be better if, instead of Newton, we use the first iterate of Halley or Householder methods.

Claude Leibovici
  • 260,315
0

Why would this solution be useful to you?
In case $n=3$, we should solve $$ 1-(1-p)(1-p^2)=f(3) . \tag1$$ The answer is \begin{align} x &= {\frac{1}{3}} + {\frac {\sqrt [3]{44-108\,f \left( 3 \right) +12\,\sqrt {-15-66\,f \left( 3 \right) +81\, \left( f \left( 3 \right) \right) ^{2}}}}{6}} \\&\qquad\qquad+{\frac {8}{3\,\sqrt [3]{44-108\,f \left( 3 \right) +12\,\sqrt {-15-66 \,f \left( 3 \right) +81\, \left( f \left( 3 \right) \right) ^{2}}}}} \tag2\end{align} Is that helpful to you? I think $(1)$ is much more useful than $(2)$.

GEdgar
  • 111,679