Approximation of polynomial solutions for a large $N$

61 Views Asked by At

I am studying two equations of the form (they are the first-order conditions of a problem of interest):

$$f(x)\triangleq x-a(1-x)^{N-1} =0,$$

$$g(x)\triangleq x^2-\frac{a}{N}\left[1-(1-x)^{N}\right] =0.$$

were $x\in [0,1)$, $a>0$, and $N \in \mathbb{N}$. I am interested in obtaining solutions to the two equations above, comparing them, and potentially letting $N\to \infty$. More precisely, define $x^{*}_f$ and $x^{*}_g$ as solutions to the above equations. This means that:

$$f(x^{*}_f)=0, \text{ and } g(x^{*}_g)=0. $$

For a large $N$, I am interested in establishing conditions under which $x^{*}_f<x^{*}_g$, and potentially studying this relationship as $N\to \infty$. For instance, when $N=2$ is is easy to verify that: $$x^{*}_f=\frac{a}{a+1} \text{ and } x^{*}_g=\frac{a}{a/2+1} . $$

Which implies that: $x^{*}_f<x^{*}_g$.

For a general $N$, since the problems above do not have closed-form solutions, some approximation is needed. My informal guess is that the terms $a(1-x)^{N-1}$ and $a(1-x)^{N}$ above quickly go to zero when $N$ is large, at a much faster rate than the term $a/N$. This makes me guess that solutions look something like:

$$x^{*}_f=0 \text{ and } x^{*}_g=\sqrt{a/N} . $$

But I understand that letting $N\to \infty$ only in the terms the terms $a(1-x)^{N-1}$ and $a(1-x)^{N}$ above quickly go to zero when $N$ is largeand not in $a/N$ is somewhat imprecise.

I have also tried using Taylor expansions, but since I have a polynomial of a high order, this does not really make my life much easier. Do you have any suggestions of other approximations I could try?

Graphical inspection: Notice that graphically, it is clear that the above equations have a unique solution each, and that it is such that $x^*_f<x^*_g$. To see this we can graph the curves $x$, $a(1-x)^{N-1}$, and $\frac{a}{N}\left[1-(1-x)^{N}\right]$ in the first quadrant. I did so here:

Graphical inspection

1

There are 1 best solutions below

3
On BEST ANSWER

To analyze $x_f$ it will be convenient to make the change of variables $M = N-1$ and $x_f = \frac{z_f}{M}$. Then we want to analyze $\frac{z_f}{M} = a \left( 1 - \frac{z_f}{M} \right)^M$. As $M$ gets large we have the exponential approximation

$$\left( 1 - \frac{z_f}{M} \right)^M \approx \exp(-z_f)$$

(this is the key step in the argument!) so for $M$ large we get $z_f \approx M a \exp( - z_f) \Leftrightarrow z_f \exp(z_f) \approx Ma$. This lets us express $z_f$ approximately in terms of the Lambert W function as $z_f \approx W(Ma) \approx \log Ma - \log \log Ma + o(1)$ which gives

$$\boxed{ x_f \approx \frac{W(Ma)}{M} \approx \frac{\log Ma - \log \log Ma + o(1)}{M} }.$$

So $x_f$ grows roughly like $\frac{\log M}{M}$. To numerically check the accuracy of this approximation we can check it for, say, $a = 1, M = 100$, which gives $x_f = 0.0334 \dots$ numerically while the Lambert W approximation gives $x_f \approx \frac{W(100)}{100} = 0.033\color{red}{9} \dots$ and the rougher logarithmic approximation gives $x_f \approx \frac{\log 100 - \log \log 100}{100} = 0.03\color{red}{08} \dots$.

The Lambert W function approximation is in fact an upper bound, since we in fact have an inequality $\left( 1 - \frac{z_f}{M} \right)^M \le \exp(-z_f)$, which gives $z_f \exp(z_f) \le Ma$ and hence, since $W$ is an increasing function, $z_f \le W(Ma)$ and so

$$\boxed{ x_f \le \frac{W(Ma)}{M} }.$$

We also have $W(x) \le \log x$ for $x \ge e$ so for $Ma \ge e$ we have the simpler bound $x_f \le \frac{\log Ma}{M}$.

To analyze $x_g$ it will similarly be convenient to make a change of variables, this time $x_g = z_g \sqrt{ \frac{a}{N} }$. Then we want to analyze

$$z_g^2 = \left( 1 - \left( 1 - z_g \sqrt{ \frac{a}{N} } \right)^N \right).$$

Here the exponential approximation gives $\left( 1 - z_g \sqrt{ \frac{a}{N} } \right)^N \approx \exp \left( - z_g \sqrt{aN} \right)$. We can see from the above that we'll end up having $z_g \approx 1$ which makes this exponential term decay rapidly. Here we want a lower bound, and happily the exponential approximation points in the correct direction here; we have $\left( 1 - z_g \sqrt{\frac{a}{N}} \right)^N \le \exp \left( - z_g \sqrt{aN} \right)$ which gives

$$z_g^2 \ge 1 - \exp \left( - z_g \sqrt{aN} \right).$$

From here we can use the bound $\exp(-x) = \frac{1}{\exp(x)} \le \frac{1}{1+x}$ to get

$$z_g^2 \ge 1 - \frac{1}{1 + z_g \sqrt{aN}}.$$

From here we can get a weak lower bound by going all the way back to analyzing $g(x)$, and then we can bootstrap our weak lower bound to get a better one. We have $g(0) < 0$ and $g(1) = 1$ so $x_g$ is the unique real root between $0$ and $1$ and it lies between a sign change from negative to positive; this tells us that if $g(x) \le 0$ then $x \le x_g$. The bounds above applied to $g(x)$ give

$$\begin{align*} g(x) &\le x^2 - \frac{a}{N} \left( 1 - \exp \left( -Nx \right) \right) \\ &\le x^2 - \frac{a}{N} \left( 1 - \frac{1}{1 + Nx} \right) \end{align*}$$

and substituting in $x = \frac{\sqrt{a}}{N}$ gives that

$$g \left( \frac{a}{N} \right) \le \frac{a}{N^2} - \frac{a}{N} \frac{\sqrt{a}}{1 + \sqrt{a}}$$

which is $\le 0$ as long as $N \ge 1 + \frac{1}{\sqrt{a}}$. So, assuming this from now on, we conclude that $x_g \ge \frac{\sqrt{a}}{N}$ and hence that $z_g \ge \frac{1}{\sqrt{N}}$. This gives

$$z_g^2 \ge 1 - \frac{1}{1 + z_g \sqrt{aN}} \ge 1 - \frac{1}{1 + \sqrt{a}} = \frac{\sqrt{a}}{1 + \sqrt{a}}$$

which gives

$$\boxed{ x_g \ge \frac{\sqrt{a}}{(1 + \sqrt{a}) \sqrt{N}} }.$$

This is not sharp; we can now bootstrap a second time to get

$$z_g^2 \ge 1 - \exp \left( - z_g \sqrt{aN} \right) \ge 1 - \exp \left( - \frac{a}{1 + \sqrt{a}} \sqrt{N} \right)$$

so $z_g$ is in fact exponentially close to $1$. In any case, we've established that for fixed $a$ and $N$ sufficiently large, $x_f$ is bounded from above by something which grows like $\frac{\log N}{N}$ while $x_g$ is bounded from below by something which grows like $\frac{1}{\sqrt{N}}$ and this is enough to conclude that $x_f < x_g$ for $N$ sufficiently large.

To numerically check the accuracy of this approximation we can take $a = 1, N = 101$ (to match the $M = 100$ we tested earlier) which gives $x_g = 0.0995025 \dots$ while our estimate, ignoring the exponential term because it is already quite small by this point, gives $x_g \approx \frac{1}{\sqrt{101}} = 0.09950\color{red}{37} \dots$.