Find the minimum integer satisfying an inequality

Question

Let $\alpha \in (0,1)$ and $\beta \in (0,1)$. I want to compute the smallest integer $n > 0$ such that: $$ 1 - \alpha^n - [1 - \alpha]^n \geq \beta. $$ For example, with $\alpha = 0.75$ and $\beta = 0.99$, we find $n = 17$.

I know that a dichotomy search for n in a wide range, say $[0,10^7]$ is doable. Another method is to let $n$ be temporarily real, find the solution of the equation $1 - \alpha^x - [1 - \alpha]^x = \beta$ for $x > 0$ a real number, then round to the upper integer. But i feel that this equation might be more deep than these algorithms and I search for a better solution. Is there one?

Answer 1

I think there should be no 'better' solution.

The function $f(n) = (1-\alpha^n - (1-\alpha)^n)$ is monotonuously increasing in $n$ as both exponential terms are in $(0,1)$, so if you find a solution to $f(n) = \beta$ for $n\in\mathbb{R}^+$, then you can indeed round up $n$ and this should give you the optimal solution for $n\in\mathbb{Z}^+$, given that $\alpha$ and $\beta$ are constants.

Methodology wise, both a dichotomy search and some sort of exact method should be sufficient to solve this question. I am not sure if the equation you posted has a closed-form solution, but I would expect it to be ugly if it exists.

Answer 2

As pointed by Ivan Kaznacheyeu in the comments, we can find bounds of the solution. One of the ways is by using the LogSumExp function: $$ LSE(x_1, x_2) = \log\left(\exp(x_1) + \exp(x_2)\right) $$ for any $x_1, x_2 \in \mathbb{R}$. This can be used to compute bounds of the required integer. If $n$ satisfies the following inequality: $$ \left\lceil \frac{\log(1 - \beta)}{\log(\gamma)} \right\rceil \leq n \leq \left\lceil \frac{\log\left(\frac{1 - \beta}{2}\right)}{\log(\gamma)} \right\rceil \qquad (1) $$ where $\gamma = \max(\alpha, 1 - \alpha)$, then: $$ \alpha^n + (1 - \alpha)^n \geq 1 - \beta. \qquad (2) $$

Proof

The LSE function satisfies the following inequality: $$ \max(x_1, x_2) \leq LSE(x_1,x_2) \leq \max(x_1, x_2) + \log(2). $$ But $$ \begin{aligned} \log(\alpha^n + (1 - \alpha)^n) & = \log \left[ \exp(n \log(\alpha)) + \exp(n \log(1 - \alpha)) \right] \\ & = LSE(n \log(\alpha), n \log(1 - \alpha)). \end{aligned} $$ Hence, $$ \max(n\log(\alpha), n\log(1 - \alpha)) \leq \log(\alpha^n + (1 - \alpha)^n) \leq \max(n\log(\alpha), n\log(1 - \alpha)) + \log(2). $$ Since the log function is increasing, this implies: $$ \max \left[ n\log(\alpha), n\log(1 - \alpha) \right] = n \log \left[ \max(\alpha, 1 - \alpha) \right] = n \log(\gamma). $$ Hence, $$ n \log(\gamma) \leq \log(\alpha^n + (1 - \alpha)^n) \leq n \log(\gamma) + \log(2). \qquad (3) $$

We want to find $n$ such that the inequality (2) is satisfied. This is equivalent to: $$ \log \left[ \alpha^n + (1 - \alpha)^n \right] \geq \log(1 - \beta). \qquad (4) $$ since $\log$ is a nondecreasing function. Temporarily assuming that $n$ is a real number, we solve the equation: $$ \log \left[ \alpha^n + (1 - \alpha)^n \right] = \log(1 - \beta). $$ All in all, if $n$ satisfies the following inequality: $$ n \log(\gamma) \leq \log(1 - \beta) \leq n \log(\gamma) + \log(2) $$ then the equation (2) is satisfied. This is equivalent to: $$ \log\left(\frac{1 - \beta}{2}\right) = \log(1 - \beta) - \log(2) \leq n \log(\gamma) \leq \log(1 - \beta). $$ We can divide the previous inequality by $\log(\gamma) < 0$ and get: $$ \frac{\log(1 - \beta)}{\log(\gamma)} \leq n \leq \frac{\log\left(\frac{1 - \beta}{2}\right)}{\log(\gamma)}. $$ Returning back to an integer solution, we get that the required integer is defined by the inequality (1). ■