
> 
> Is the sequence $$w\_n=n! \int\_0^{1/2} \int\_{x\_1}^{2/3} \cdots\int\_{x\_{n-2}}^{\frac{n-1}{n}} \int\_{\frac{n}{n+1}}^1 dx\_n dx\_{n-1} \cdots dx\_1$$ increasing for $n\ge 3$?
> 
> 
> 


This is a conjecture of F. Thomas Bruss and Marc Yor in a recent paper *Stochastic Processes with Proportional Increments and The Last-Arrival Problem*. It is presented here with the permission of them.


Background
----------


In the mentioned paper Bruss and Yor introduce stochastic processes with *proportional increments* to deal with the so called *last arrival problem* (l.a.p.) where an *unknown* number of independent random random variables $X\_1,\ldots,X\_N$ (which are uniformly distributed on the interval $[0,1]$) is observed and "our objective is to
stop online with exactly one stop on the very last of these points, i.e. at their
largest order statistics $X\_{\langle N;N\rangle}$" (cited from Bruss and Yor).
Bruss and Yor give an interpretation of the problem (it is not so obvious what it means that $N$ is *unknown*) and then provide the optimal strategy. The numbers $w\_n$ are then
the win probability conditioned on $N=n$. Bruss and Yor state that $w\_n \to 1/e$.


Some relations
--------------


The inner integral clearly is $1/(n+1)$ and the remaining integral is thus up to the factor $n/(n+1)$ the probability that the order statistic $X\_{\langle 1;n-1\rangle},\ldots,X\_{\langle n-1;n-1\rangle}$ of $n-1$ independent on $[0,1]$ uniformly distributed random variables has values in $[0,1/2] \times [0,2/3] \times \cdots \times [0,\frac{n-1}{n}]$. It would be thus natural if a similar problem had appeared in some statistical context.


One can write down the latter probability using multinomial sums (which looks very
ugly). Nevertheless this suggests that some clever combinatorial arguments might help.


Finally the order statistics are closely related to Poisson processes (however, as the authors are experts in stochastic processes they have most probably checked that area).



The Bruss-Yor conjecture about an iterated integral
Update on the background of the problem:


The multiple integral in question is related to the last-arrival problem: A selector wants to pick, online, the last of an unknown number of items that arrive at independent times uniformly chosen in $[0,1]$. The number $w\_n$ is the probability of success (with $n$ items) for the strategy where the selector accepts the $k$:th item if it arrives after time $1-1/(k+1)$. 


The last-arrival problem was a byproduct of an attempt to improve a lower bound by John Preater for the so-called partially ordered secretary problem. I have described how I came up with it in my arXiv paper ``When only the last one will do'', <http://arxiv.org/abs/1104.3049>. The initial conjecture was that there exist policies with winning probability at least $1/e$ for every $n$, but this turned out not to be true (together with Ragnar Freij, we later got the bound in the partially ordered secretary problem up to the optimal $1/e$ by another method, see <http://arxiv.org/abs/1008.3310> or Elect. Comm. in Probab. 15 (2010), 504--507). 


At a conference in 2008 I went out for a beer with Thomas Bruss, and we came to discuss various problems of optimal stopping. I mentioned the last-arrival problem, and his initial thought was that his odds-theorem should give the answer. As it turns out, the conditions for the odds-theorem are slightly violated, but it still suggests a reasonably good strategy for the selector, namely the one just described, to accept the $k$:th item after time $1-1/(k+1)$. 


When I visited Bruss in 2009, the iterated integral in the OP was on the blackboard in the coffee room. Before I left I think I showed him a set of coffee-stained pages of notes that I claimed was a proof that $w\_n$ is increasing for $n\geq 3$, but I certainly can't blame him for not remembering this. I might have said only that $w\_n\geq 5/16$ for all $n$, which seemed to me to be the most interesting part of it. Edit: Looking back at some of our email correspondence, it seems I promised to send a proof, and never did. 


Now to those messy details. I have to apologize to everyone who expected a neat way to peal off one integral sign from the expression for $w\_n$. What I have is simply some upper and lower bounds on $w\_n$ that eventually prove the sequence to be increasing.


It turns out that $w\_n$ is asymptotically $1/e - constant\cdot n^{-1}$, and that consequently the difference $w\_{n+1}-w\_n$ is of order $1/n^2$. To prove the sequence to be increasing, we therefore need to estimate $w\_n$ with an error smaller than that.


In order for the selector to succeed, there has to be exactly one item arriving in the interval $[1-1/(n+1), 1]$. Moreover, there can be no item arriving in the interval $[1-1/n, 1-1/(n+1)]$, and at most one in the interval $[1-1/(n-1), 1-1/n]$, since otherwise an earlier item will be accepted. Let's call this the Main Condition.


The probability that the main condition is satisfied is
$$U(n) = n\cdot \frac1{n+1}\cdot \left[\left(1-\frac1{n-1}\right)^{n-1} + \frac1n\cdot \left(1-\frac1{n-1}\right)^{n-2}\right].$$
Explanation: There are $n$ ways to choose the item to be accepted, and that item has to be in the interval $[1-1/(n+1), 1]$ of length $1/(n+1)$. This gives the factor $n/(n+1)$. For the remaining $n-1$ items there are two possibilities, either they are all in the interval $[0, 1-1/(n-1)]$, which gives the first term within brackets, or one of them is in the interval $[1/(n-1), 1/n]$ of length $1/(n(n-1))$ and the remaining ones are in $[0, 1-1/(n-1)]$. In the latter case there are $n-1$ ways of choosing the special item, and after canceling a factor $n-1$ we get the second term within brackets.


We have $w\_n \leq U(n)$, and we would like to estimate the error $E(n) = U(n) - w\_n$ in this approximation. 
By the way, Taylor expansion of $U(n)$ with respect to $1/n$ shows that $$U(n) = \frac1e - \frac1{2e}\cdot\frac1n + \frac7{24e}\cdot\frac1{n^2}+O\left(\frac1{n^3}\right),$$ so provided the error $E(n)$ is of order $1/n^3$, things look promising.


If the main condition is met and the policy still fails, there must be some $k\geq 3$ for which exactly (!) $k$ items arrive in the interval $[1-1/(n-k+1), 1-1/(n+1)]$. An upper bound on the error is therefore 


$$E(n) \leq \sum\_{k=3}^{n-1} \binom{n}{k}\left(\frac1{n-k+1}-\frac1{n+1}\right)^k
= \sum\_{k=3}^{n-1} \binom{n}{k}\left(\frac{k}{(n-k+1)(n+1)}\right)^k.$$ 


At this point it is easy to verify by computer that $w\_n$ is increasing for $27\leq n \leq 200$, say. And for $3\leq n \leq 27$, it can be verified by exact integration (indeed up to at least $n=100$, as has been pointed out in earlier comments).


To get an estimate that can be handled for large $n$, we treat the term $k=n-1$ individually, and for the remaining ones we use the elementary inequality $k^k/k! \leq e^{k-1}$. It follows that


$$E(n) \leq \frac{n}{2^{n-1}} + \sum\_{k=3}^{n-2} n^k e^{k-1}\left(\frac1{(n-k+1)(n+1)}\right)^k$$
$$ \leq \frac{n}{2^{n-1}} + e^{-1}\sum\_{k=3}^{n-2} \left(\frac{e}{n-k+1}\right)^k.$$


In the last sum, the second derivative of the summand with respect to $k$ is $$ \left(\frac{e}{n-k+1}\right)^k \cdot \left[\left(\log\left(\frac{e}{n-k+1}\right) + \frac{k}{n-k+1}\right)^2 + \frac{2}{n-k+1}+\frac{k}{(n-k+1)^2}\right],$$ which is clearly nonnegative. Hence the summand is convex, so that in any sequence of consecutive terms, the first or the last must be maximal.


Now we pick out also the term $k=3$, and notice that for $n\geq 169$, the term $k=4$ will be larger than the term $k=n-2$. Therefore


$$E(n) \leq \frac{n}{2^{n-1}} + \frac{e^2}{(n-2)^3} + (n-5) \cdot \frac{e^3}{(n-3)^4}
\leq \frac{n}{2^{n-1}} + \frac{e^2+e^3}{(n-3)^3} \leq \frac{30}{n^3},$$ if $n\geq 169$, as we already assumed.


So we have $$U(n) - \frac{30}{n^3} \leq w\_n \leq U(n).$$


At this point we can verify numerically that $U(n) - U(n-1) > 30/n^3$ for $164\leq n \leq 2000$, say, after which a very rough bound will suffice.


To get such a bound, we can differentiate $U(n)$ with respect to $n$ and get
$$U'(n) = \frac{\left(1-\frac1{n-1}\right)^n}{(n+1)^2(n-2)^2}\cdot \left((n^4-n^3-2n^2+n+1)\log\left(1-\frac1{n-1}\right) + n^3+n^2-2n\right).$$
By Taylor's theorem, $$\log(1-x) \geq -x - \frac89\cdot x^2$$ whenever $0\leq x \leq 1/4$. Also, $$\left(1-\frac1{n-1}\right)^n \geq \frac14,$$ for $n\geq 6$. Plugging in these estimates (with $x = 1/(n-1)$), we get 
$$U'(n) \geq \frac1{36}\cdot \frac{n^3-9n^2+25n-1}{(n-1)(n-2)^2(n+1)^2},$$
which is of order $1/n^2$, and is easily seen to be larger than $30/n^3$ for all $n\geq 2000$. 


It follows that $U(n) - U(n-1)\geq \int\_{n-1}^n 30/x^3\,dx \geq 30/n^3\geq E(n)$, and that $w\_n$ is increasing.


