Skip to main content
Minor clarification of the background.
Source Link
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

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 itI came aboutup 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).

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.

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 it came about 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).

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.

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

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.

Bounty Ended with 100 reputation awarded by Jochen Wengenroth
Considerably more detailed explanation and background
Source Link
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

I discussed thisUpdate on the background of the problem with Thomas Bruss in 2009 and solved it modulo some numerical details.:

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 it came about 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.

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$, and to show that. To prove the sequence isto be increasing, it sufficeswe therefore need to estimate $w_n$ with an error of order $O(1/n^3)$smaller than that.

To get an upper bound with this precision, we note that inIn 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 these conditionsthe 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 met$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 $$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].$$$[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 this$$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 $$\frac1e - \frac1{2e}\cdot\frac1n + \frac7{24e}\cdot\frac1{n^2}+O\left(\frac1{n^3}\right).$$$1/n^3$, things look promising.

If the selector'smain condition is met and the policy still fails despite these conditions being fulfilled, itthere must be because for some $k\geq 3$ there arefor which exactly (!) $k$ items arrivingarrive in the interval $[1-1/(n-k+1), 1-1/(n+1)]$. ThisAn upper bound on the error is way more likelytherefore

$$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 happenverify by computer that $w_n$ is increasing for $k=3$ than$27\leq n \leq 200$, say. And for any higher$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 only needalready 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 upper bound of order $1/n^3$will suffice.

To wrap upget such a bound, we need explicit bounds on the error terms, combinedcan differentiate $U(n)$ with some numerical resultsrespect 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 small values$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 $n$$1/n^2$, and is easily seen to be larger than $30/n^3$ for all $n\geq 2000$. I will update the answer with the messy details

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.

I discussed this problem with Thomas Bruss in 2009 and solved it modulo some numerical details.

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

It turns out that the difference $w_{n+1}-w_n$ is of order $1/n^2$, and to show that the sequence is increasing, it suffices to estimate $w_n$ with an error of order $O(1/n^3)$.

To get an upper bound with this precision, we note 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]$.

The probability that these conditions are met is $$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].$$

Taylor expansion with respect to $1/n$ shows that this is $$\frac1e - \frac1{2e}\cdot\frac1n + \frac7{24e}\cdot\frac1{n^2}+O\left(\frac1{n^3}\right).$$

If the selector's policy fails despite these conditions being fulfilled, it must be because for some $k\geq 3$ there are $k$ items arriving in the interval $[1-1/(n-k+1), 1-1/(n+1)]$. This is way more likely to happen for $k=3$ than for any higher $k$, and we only need a rough upper bound of order $1/n^3$.

To wrap up, we need explicit bounds on the error terms, combined with some numerical results for small values of $n$. I will update the answer with the messy details.

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 it came about 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.

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.

Source Link
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

I discussed this problem with Thomas Bruss in 2009 and solved it modulo some numerical details.

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

It turns out that the difference $w_{n+1}-w_n$ is of order $1/n^2$, and to show that the sequence is increasing, it suffices to estimate $w_n$ with an error of order $O(1/n^3)$.

To get an upper bound with this precision, we note 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]$.

The probability that these conditions are met is $$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].$$

Taylor expansion with respect to $1/n$ shows that this is $$\frac1e - \frac1{2e}\cdot\frac1n + \frac7{24e}\cdot\frac1{n^2}+O\left(\frac1{n^3}\right).$$

If the selector's policy fails despite these conditions being fulfilled, it must be because for some $k\geq 3$ there are $k$ items arriving in the interval $[1-1/(n-k+1), 1-1/(n+1)]$. This is way more likely to happen for $k=3$ than for any higher $k$, and we only need a rough upper bound of order $1/n^3$.

To wrap up, we need explicit bounds on the error terms, combined with some numerical results for small values of $n$. I will update the answer with the messy details.