17
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ What do the numerical values for the first "few" $n$ look like? $\endgroup$ Jun 26, 2012 at 3:28
  • $\begingroup$ Bruss and Yor checked the conjecture with Mathematica until $n=25$, here are the (rounded) values they report: $w_1=1/2$, $w_2=1/3$, $w_3=5/16$, $w_4=0.31667$, $w_5 = 0.32542$, $w_6 = 0.33345$, $\dots$ $w_{12} = 0.35289$, $\ldots$ $w_{25} = 0.36066$. $\endgroup$ Jun 26, 2012 at 7:10
  • $\begingroup$ The numbers do not appear to be a clue. Here are the first 1/2, 1/3, 5/16,19/60, 1687/5184, 2881/8640, 625961/1843200, 96314839/279936000, 302440148467/870912000000, 84408107137219/241416806400000, 2798993904047397389/7964120973312000000, 7033234035651624556939/19930212735713280000000 $\endgroup$
    – juan
    Jun 27, 2012 at 20:57
  • 1
    $\begingroup$ @juan: Thomas Bruss would like to ask you whether you have a kind of recursion to calculate the values up to $n=100$. This might be interesting for the general case. $\endgroup$ Jul 3, 2012 at 7:26
  • 1
    $\begingroup$ I just used Mathematica and the definition you give in this post. I give you here my definition, because certainly 100 is not the limit of my definition. And what I do not see in the numbers other can see. w[n_] := w[n] = Module[{Y, x, y, k}, Y = 1/(n + 1); Clear[x, y]; For[k = n - 1, k >= 1, k--, Y = (Y /. {x -> y}); (Print["Y = ", Y];) Y = Integrate[Y, {y, x, k/(k + 1)}]; (Print[k/(k+1)])]; n! (Y /. x -> 0) ] The last integral is also interesting when you do not compute it to 0. I do not saw your query before. $\endgroup$
    – juan
    Jul 12, 2012 at 18:33

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Whew! Really messy. Nevertheless, I will try to check it. $\endgroup$ Jul 16, 2012 at 12:24
  • $\begingroup$ Except for the numerical values ($n=169$ etc.) I am convinced! (my own differentiation of the terms of the sum in the upper bound of $E(n)$ and of $U(n)$ yields something slightly different which does not affect the proof). $\endgroup$ Jul 16, 2012 at 15:17
  • $\begingroup$ For those who want to check the proof without entering into the interpretation of the last arrival problem: As written in the OP $w_n$ can be expressed in terms of order statistics, and then $U(n)$ is the (up to the factor $n/(n+1)$ the probability where only $X_{\langle n-1;n-1\rangle}$ and $X_{\langle n-2;n-1\rangle}$ satisfy the required conditions. For me it was also easier to see the estimate for $E(n)$ in these terms. $\endgroup$ Jul 16, 2012 at 15:23
  • $\begingroup$ Since Johan's arguments rely on numerical values I want to acknowledge the comments of Juan (as well as his messages by email). $\endgroup$ Jul 16, 2012 at 15:26
  • $\begingroup$ Many thanks also from Thomas Bruss to Johan and Juan. Very impressing! (Thomas Bruss told me that he indeed does not remember that Johan told him about the proof.) $\endgroup$ Jul 16, 2012 at 15:28
9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you very much. Even though one still needs some computations your proof seems to me much simpler than Johan's. $\endgroup$ Aug 15, 2012 at 8:23
  • $\begingroup$ We would like to thank again all the discussants for their contribution and, in particular Johan and Fedja for having succeeded in finding a proof where we ourselves (and many many others) have failed. Even though both Johan and Fedja are not perfectly happy with their proofs, essentially because of some annoying computations to do, we are very to see that the conjecture is true. By the way, dear Fedja, who is behind your name? For Bruss and Yor, Thomas Bruss cc: Jochen Wengenroth $\endgroup$
    – user31088
    Feb 1, 2013 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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