The Bruss-Yor conjecture about an iterated integral

Question

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).

Answer 1

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.

Answer 2

Here is a sketch of a full proof that can be (at least, in principle) verified by a human.

Claim 1. $\gamma_n=(\frac{n-1}{n})^{n-1}$ is a decreasing sequence.

This is well known and easy to prove.

Claim 2. The integral in question is just $\frac n{n+1}$ times the probability $P_n$ that $Y_k\le \frac k{k+1}$ for all $k=1,\dots,n-1$ where $Y_k$ is the $k$-th value in the list obtained by sampling $n-1$ independent random variables uniformly distributed on $[0,1]$ and putting them in the increasing order.

This has already be mentioned by the OP.

Claim 3. The joint distribution of $Y_{n-1},\dots,Y_1$ is the same as of $X_1^{\frac 1{n-1}},X_1^{\frac 1{n-1}}X_2^{\frac 1{n-2}},\dots,X_1^{\frac 1{n-1}}X_2^{\frac 1{n-2}}\cdots X_{n-1}$ where $X_j$ are i.i.d. random variables uniformly distributed on $[0,1]$.

Just condition on the maximum and use induction. From now on, we will just assume that $Y_k=X_1^{\frac 1{n-1}}\dots X_{n-k}^{\frac 1{k}}$.

Claim 4. For all $k\ge 2$, we have $$ (\frac{k-1}{k})^{\frac{k-1}k}(\frac{k}{k+1})^{\frac 1{k(k+1)}}\le \frac{k}{k+1} $$

Rewrite it as $(\frac{k^2-1}{k^2})^{k^2-1}\le (\frac{k}{k+1})^{k}$ and use Claim 1.

Claim 5. Let $2\le k\le n-2$. If $X_1^{\frac 1{n-2}}\dots X_{n-k}^{\frac 1{k-1}}\le \frac{k-1}{k}$ and $X_1^{\frac 1{n-2}}\dots X_{n-k-1}^{\frac 1{k}}\le \frac{k}{k+1}$, then $X_1^{\frac 1{n-1}}\dots X_{n-k}^{\frac 1{k}}\le \frac{k}{k+1}$.

Raise the first inequality to the power $\frac{k-1}{k}$, the second to the power $\frac 1{k(k+1}$, multiply, use the fact that $X^t$ is decreasing in $t$ for $0<X<1$, and apply Claim 4.

Claim 6. $$ P_n\ge \frac{\gamma_n}{\gamma_{n-1}}P_{n-1}-(1-\frac 2n)^{n-1}2^{-(n-1)} $$

Claim 5 allows one to conclude that replacing a sample $X_1,X_2,\dots$ satisfying the desired set of inequalities for $n-1$ instead of $n$ by $X_1'=\frac{\gamma_n}{\gamma_{n-1}}X_1, X_2'=X_2, X_3'=X_3,\dots$, we get a sample satisfying all the desired inequalities for $n$ except, perhaps, the very last one. Thus, the probability $Q_n$ that all inequalities except the last one are satisfied is at least $\frac{\gamma_n}{\gamma_{n-1}}P_{n-1}$ (the factor comes from the bound for the density of $X_1'$ relative to the density of $X_1$). What we need to subtract is at most the probability that the minimum of $n-1$ independent random variables uniformly distributed on $[0,1]$ is at least $1/2$ while their maximum is at most $\frac{n-1}n$. This is the last term in the inequality.

Claim 7. We have $$ \frac{n}{n+1}P_n\ge \frac{n}{n+1}\frac{n}{n-1}\frac{\gamma_n}{\gamma_{n-1}}\frac{n-1}n P_{n-1}-\frac{n}{n+1}(1-\frac 2n)^{n-1}2^{-(n-1)} $$

This is just Claim 6 rewritten.

Assuming that $\frac{n-1}nP_{n-1}\ge\frac 5{16}$, we conclude that we will be able to run the induction if $$ [\frac{n}{n+1}(1+\frac{1}{n(n-2)})^{n-2}-1]*\frac{5}{16}\ge \frac{n}{n+1}(1-\frac 2n)^{n-1}2^{-(n-1)} $$

Using the first three terms in the Newton's formula on the left, we see that to pass from $n-1$ to $n$, it is enough to have $$ \frac{5}{16}\frac{n-3}{2n^2(n-2)}\ge (1-\frac 2n)^{n-1}2^{-(n-1)} $$

Claim 8. This inequality holds for $n\ge 7$.

For $n=7$, it reduces to $8\cdot 7^4>5^6$, i.e., $(2-\frac 1{25})^2>4-\frac 78$, which is fairly obvious by Bernoulli. It remains to note that when $n$ goes up by $1$, the left hand side is multiplied by at least $(\frac 78)^2$\ge $\frac 34$ while the right hand side is multiplied by $1/2$ because of the power of $2$ and at most $(1-\frac{n-1}{n(n-2})^{-1}\le \frac{35}{29}$, which is the Bernoulli bound for the factor by which $(1-\frac 2n)^{n-1}$ differs from the decreasing sequence $(\frac{n-1}{n})^2(n-1)$. Now, $\frac 12\cdot\frac {35}{29}\le \frac{18}{29}\le \frac 34$, so we can run the induction.

The most difficult (=time and effort consuming) part of this proof is

Claim 9. $P_1$ through $P_6$ are fine for the base of induction.

I managed to compute $P_4$ by hand without an arithmetic error, but not $P_5$. That's why I would still prefer to see an argument that doesn't require a direct computation of any value beyond $P_3$.