0
$\begingroup$

Let $n$ be a natural number. Define a function $f(x) := (1-x)^{n-1}x - x^n$, where $0\le x\le 1/n$. How do I maximise this function?

From numerical experiments, the maximiser $x^*$ is very close to $1/n$ (say when $n \ge 8$). I need only the asymptotics of $f(x^*)$ for large $n$.

$\endgroup$
1
  • $\begingroup$ Edited for simpler $\endgroup$ Jun 12, 2022 at 2:45

2 Answers 2

3
$\begingroup$

$$f(x) = (1-x)^{n-1}x - x^n \implies f'(x)=(1-x)^{n-2} (1-n x)-n x^{n-1}$$

Expanding $f'(x)$ as a series around $x=\frac{1}{n}$ gives $$f'(x)=-n^{2-n}-\frac{\left((n-1)^n+(n-1)^3\right) n^{3-n}}{(n-1)^2}\left(x-\frac{1}{n}\right)+O\left(\left(x-\frac{1}{n}\right)^2\right)$$ from which $$\color{blue}{x_* =\frac 1 n \Bigg[1 -\frac{1}{(n-1) \left(1+(n-1)^{n-3}\right)} \Bigg]}\tag 1$$

Some results for small values of $n$

$$\left( \begin{array}{cccc} n & \text{Max}_{\text{est}} & x_{\text{est}} &\text{Max}_{\text{calc}} & x_{\text{calc}} \\ 3 & 0.1250000000 & 0.2500000000 & 0.1250000000& 0.2500000000 \\ 4 & 0.1022041227 & 0.2291666667 & 0.1022044240& 0.2296052348 \\ 5 & 0.0816116932 & 0.1970588235 & 0.0816116941& 0.1970852069 \\ 6 & 0.0669582639 & 0.1664021164 & 0.0669582639& 0.1664024424 \\ 7 & 0.0566515658 & 0.1428387855 & 0.0566515658& 0.1428387874 \\ 8 & 0.0490869284 & 0.1249989376 & 0.0490869284& 0.1249989376 \\ 9 & 0.0433049244 & 0.1111110581 & 0.0433049244& 0.1111110581 \\ 10 & 0.0387420488 & 0.0999999977 & 0.0387420488& 0.0999999977 \end{array} \right)$$

Now, you can neglect the $1$ (except in powers) and get $$\color{red}{x_* \sim \frac 1 n (1-n^{2-n})}\tag 2$$ which, for $n=10$ will give $x_*=0.099999999$.

Concerning $f(x_*)$, before any simplification

$$f(x_*)=\frac{(n-1)^n+(n-2) (n-1)^2}{\left((n-1)^n+(n-1)^3\right) n} \left(1-\frac{(n-1)^n+(n-2) (n-1)^2}{\left((n-1)^n+(n-1)^3\right) n}\right)^{n-1}-$$ $$\left(\frac{(n-1)^n+(n-2) (n-1)^2}{\left((n-1)^n+(n-1)^3\right) n}\right)^n$$

Neglecting again the $1$ and $2$ (except in powers) gives $$\color{red}{f(x_*)=\frac 1 n \left(1-\frac{1}{n}\right)^{n-1}-n^{-n} \sim \frac 1 n \left(1-\frac{1}{n}\right)^{n-1}\quad \to \quad \frac e n}$$

$\endgroup$
9
  • $\begingroup$ There are ones one can neglect and ones one cannot neglect :), $\lim_{n \to \infty} (n - 1)^n/n^n \neq 1$. $\endgroup$
    – Maxim
    Jun 4, 2022 at 17:06
  • $\begingroup$ @Maxim. You are right ! I edit $\endgroup$ Jun 5, 2022 at 1:51
  • 1
    $\begingroup$ what is the asymptotic value of f(x*)? $\endgroup$
    – user630227
    Jun 7, 2022 at 10:43
  • $\begingroup$ why is x* asymptotically equal to the approximation of the root of f'(x) after one iteration of Newton's Method? Why does one iteration give the correct asymptotic? $\endgroup$
    – user630227
    Jun 8, 2022 at 9:33
  • $\begingroup$ @ColinTan. I used what you did observe (which is more than true). We could do the same with Halley or Householder methods or even with Taylor series. If I have time, I shall update. $\endgroup$ Jun 8, 2022 at 9:38
0
$\begingroup$

I don't know if this would help but ...

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.12
Solving Nodes      : 45
Primal Bound       : +1.25000772705644e-01 (26 solutions)
Dual Bound         : +1.25000772705644e-01
Gap                : 0.00 %

primal solution (original space):
=================================

objective value:                    0.125000772705644
i1                                                  2   (obj:0)
x0                                  0.250018487408352   (obj:0)
x2                                  0.125000772705644   (obj:1)
x3                                                0.5   (obj:0)
x5                                                  1   (obj:0)
$\endgroup$
1
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Jun 4, 2022 at 18:51

You must log in to answer this question.