Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For x in reals and K some positive integer, can you find the maximum of this function analytically?

$f(x) = x(1 - (1 - \frac{1}{x})^K)$

share|improve this question

4 Answers 4

up vote 2 down vote accepted

Alphabet soup: Imagine a sequence $(a_1, a_2,\dots, a_K)$ over the alphabet $\{1,2,\dots,x\}$ chosen uniformly at random among the $x^K$ possibilities. What is the expected size of the set $\{a_1,a_2,\dots,a_K\}$?

Solution: Let $A_i$ be the event that the letter $i$ is present in the random sequence. The size of the set is just $X=\sum_{i=1}^x 1_{A_i}$ which has expected value $$\mathbb{E}(X)=\sum_{i=1}^x \mathbb{P}(A_i)=x\left[1-\left(1-{1\over x}\right)^K\right].$$

But the size of the set cannot exceed $K$, so $X\leq K$ with full probability and therefore also $\mathbb{E}(X)\leq K$. On the other hand, $K\mathbb{P}(X=K)\leq \mathbb{E}(X)$ but this probability is easily calculated, giving the bounds $$K\left({x\over x}{x-1\over x}\cdots{x-K+1\over x}\right) \leq x\left[1-\left(1-{1\over x}\right)^K\right]\leq K.$$ This shows that the expression converges to its upper bound $K$ as $x\to\infty$. Of course, all of this assumes that $x$ and $K$ are natural numbers.

share|improve this answer
    
I first saw this idea here: math.stackexchange.com/questions/5775/… but then I couldn't remember where I'd seen it. –  Byron Schmuland Mar 4 '12 at 18:31

Seems unlikely. If you differentiate, set to zero, and simplify, you get a polynomial equation of degree $k-1$. If $k\ge6$ I wouldn't expect there to be a formula for $x$ in terms of radicals and the four arithmetical operations.

share|improve this answer

We'll show that for $K$ even there is no extreme value on $(0,\infty)$. Behaviour to the left of $0$ is similar. However, we won't show how to find the extreme values when they exist (i.e. for $K>1$ odd). However, I think this argument partially answers the question so I decided to post it.

First assume $x\ge 1$. Set $g(x) = \left(1+\frac{K-1}{x}\right)\left(1-\frac{1}{x}\right)^{K-1}$, so that $f^\prime(x) = 1 - g(x)$. Make the substitution $v = 1 - 1/x$ and note that $x\ge 1$ implies $0\le v<1$. Then $$ g(v) = (v+K(1-v))v^{K-1}= v^{K-1}(v(1-K) + K)\le v^{K-1}(1-K+K) < 1. $$ The second to last inequality holds since $v<1$. Therefore the derivative is positive on $(1,\infty)$.

Now assume $0<x<1$. This case is trickier. If $K$ is even then the derivative is also positive on $(0,1)$ because $v<0$ and $K-1$ is odd. In this case $f(x)$ has no extreme values on $(0,\infty)$. But $K$ odd will lead to $$ g(v) \le v^{K-1}(1-K+K) = v^{K-1} $$ and we can make the right side as large as we like ($v$ is unbounded below). Therefore $f^\prime(x) = 1 - g(x)$ will be negative somewhere on $(0,1)$ so there's a minimum somewhere in $(0,1)$. But I can't solve for it which was probably what the OP wanted to know, but on the other hand, we can see it doesn't always have a max. In fact, the only extreme values on $(0,\infty)$ are minumums (when $K >1$ is odd), and lie in $(0,1)$.

share|improve this answer

When $K = 1$, $f(x) = 1$. So assume $K > 1$ (not necessarily an integer).

The derivative of your function is $$ 1 - \left(1 - \frac{1}{x}\right)^K - \frac{K}{x}\left(1 - \frac{1}{x}\right)^{K-1} = 1 -\left(1 + \frac{K-1}{x}\right)\left(1 - \frac{1}{x}\right)^{K-1} . $$ The derivative approaches $1$. In particular, when $x$ is large enough, this derivative is at least $1/2$ (say). Therefore the function grows to infinity with $x$.

Edit: In fact, as André points out, the derivative approaches $0$, and what is even worse, it's not even clear whether it remains positive. In fact, approximately $(1-1/x)^{K-1} = 1-(K-1)/x+(K-1)(K-2)/2x^2$ and so the derivative is approximately $$1 - \left(1 + \frac{K-1}{x}\right)\left(1 - \frac{K-1}{x} + \frac{(K-1)(K-2)}{2x^2}\right) = \frac{K(K-1)}{2x^2} + \frac{(K-1)^2(K-2)}{2x^3}.$$ So it does appear that the function is ever-increasing. At the limit, we get the value $K$, as mentioned in the comments.

share|improve this answer
    
As $x$ gets large, the derivative appears to approach $1 - 1(1) = 0$. But it's hard to tell if the second term is greater than 1 or less than 1. –  Patrick Mar 1 '12 at 23:07
    
@Yuval Filmus: I have trouble with this argument, since for huge $x$ the exponential is roughly $1-\frac{K}{x}$. –  André Nicolas Mar 1 '12 at 23:16
    
Playing around with a graphing program, $f$ looks to be increasing on the positive axis with limit $K$ as $x$ increases without bound. Similar behavior to the left of $0$. –  Patrick Mar 1 '12 at 23:30
    
@Patrick: The limit is indeed $K$, easy proof. –  André Nicolas Mar 1 '12 at 23:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.