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$
11
  • $\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
    Commented Sep 4, 2018 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$
    – Arbiter
    Commented Sep 4, 2018 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
    Commented Sep 4, 2018 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$
    – Arbiter
    Commented Sep 4, 2018 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
    Commented Sep 4, 2018 at 18:16

2 Answers 2

Reset to default
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$
1
  • $\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
    Commented Sep 5, 2018 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .