5
$\begingroup$

I'm interested in solving the following equation in $[0,1]$ $$px^n - x + (1-p)=0$$

where $p \in [0,1]$ and $n \in \mathbb N -\{1,2 \} $ both constant.

To start with, we can easily see that $x=1$ is a solution and I also know there is another solution in $[0,1]$ for every $n \in \mathbb N -\{1,2 \}$ and for all $p> p_c (n)$ . I've tried using the Horner method with $(x-1)$ we get :

$$(x-1)(px^{n-1} + px^{n-2}+..+ px^2 + px+p-1)=0 $$

So we get $(px^{n-1} + px^{n-2}+..+ px^2 + px+p-1)=0 $ . Then we can do : $$ x^{n-1} + x^{n-2}+..+ x=\frac{1-p}{p}$$

or $$\frac{x^n-1}{x-1}=\frac{1-p}{p}+1 $$

But this doesn't seem to give anything useful. Any ideas on how we can solve this?

$\endgroup$
  • $\begingroup$ You mean to do it numerically? An analytical solution in terms of radicals I think will collide with Abel-Ruffini pretty quick (I suspect when $n \geq 6$). $\endgroup$ – Ian Sep 4 '18 at 17:39
  • $\begingroup$ I'm pretty sure there is an analytical solution, I've seen the root somewhere, but not the way you can solve it. $\endgroup$ – Dimitris Sep 4 '18 at 17:40
  • $\begingroup$ You've found how to solve $y=\sum_{k=0}^{n-1} x^k$ for $x$ when $y$ is an arbitrary number in $(-\infty,1]$ and $n>2$ is arbitrary? $\endgroup$ – Ian Sep 4 '18 at 17:41
  • $\begingroup$ Come to think of it you are right, seems like it can't be solved. This equation comes from solving percolation (en.wikipedia.org/wiki/Percolation_theory) in a Bethe lattice (en.wikipedia.org/wiki/Bethe_lattice). And I've read in lecture notes the second solution (for n=z-1) : $x=1- \frac{2p(z-1)-2}{p(z-1)(z-2)}$. Maybe it's wrong? $\endgroup$ – Dimitris Sep 4 '18 at 17:47
  • 1
    $\begingroup$ @Dimitris, don't give up to early, even if there are no (known) closed form solutions, there might be someone with insights that might help you nevertheless. It's only been 40 minutes since you asked. $\endgroup$ – Ennar Sep 4 '18 at 18:16
1
$\begingroup$

If $x\in (0,1)$ then for $n\in\mathbb{N}-\{1,2\}$ large we have $p\cdot x^n\approx 0$. We have $px^n-x+(1-p)=0$ and $p\cdot x^n\approx 0$ implies $$ -x+(1-p)\approx 0 $$ Then $x\approx 1-p$.

$\endgroup$
  • $\begingroup$ I think the interesting question is: how to derive corrections to this leading order large-n asymptotic? A related easier question is: what is the simultaneous scaling of $n,p$ such that this approximation breaks down if we send $p \to 0$ and $n \to \infty$ simultaneously in accordance with this scaling? Presumably it is $p \sim 1/n$... $\endgroup$ – Ian Sep 5 '18 at 0:59
1
$\begingroup$

Let's write $$ \left\{ \matrix{ f(x) = p\,x^{\,n} - x + \left( {1 - p} \right) \hfill \cr g(x) = {{f(x)} \over {x - 1}} = p{{x^{\,n} - 1} \over {x - 1}} - 1 = \hfill \cr = p\left( {1 + x + \cdots + x^{\,n - 1} } \right) - 1 \hfill \cr} \right. $$

We have that $g(x)$ is continuous, and $$ \left\{ \matrix{ g(0) = p - 1 \le 0\quad \left| {\;p \le 1} \right. \hfill \cr 0 \le g(1) = n\,p - 1\quad \left| {\;1/n \le p} \right. \hfill \cr 0 \le g'(x) = p\left( {1 + 2x + \cdots + \left( {n - 1} \right)x^{\,n - 2} } \right)\quad \left| \matrix{ \;0 \le p \hfill \cr \;2 \le n \hfill \cr} \right. \hfill \cr} \right. $$ so that, for $1/n <p \le 1$ and $2 \le n$:
$g(0)$ is non-positive, $g(1)$ is positive, g(x) is strictly increasing in the interval,
then you will have one (and only one) real root in the interval $[0,1)$, which confirms what you already know.

px^n_1

As for calculating the root, I do not see any other method than to use Newton- Raphson or the secant approximation, starting with $P_0,P_1$ as from the sketch.

$\endgroup$

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.