Return to Answer

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$.

Edit: I added a more general strategy below, giving a bound that seems likely to be optimal.

Player A will pick some positive constant $c$ and accept the first draw greater than $1-\frac{c}{n}$. The probability A sees such a draw is asymptotic to $1-e^{-c}$, and the value of the first such draw is uniform in $[1-c/n,1]$.

The probability that A wins using this strategy is asymptotic to $$ \left(1-e^{-c}\right)\cdot\frac{n}{c}\int_{1-c/n}^1 t^n\,dt\to \frac{\left(1-e^{-c}\right)^2}{c}. $$ This is maximized by taking $c\approx 1.25643$, giving a probability $\approx 0.407264$.

Variation: As bigO6377 points out in the comments, it's not optimal to choose $c$ to be a constant. We should be more likely to accept a draw that occurs near the end. Here's a strategy that does this.

Player A will choose a continuous function $c:[0,1]\to [0,\infty)$ (not depending on $n$), and will accept the $i$-th draw if its value is at least $1-c(i/n)/n$. This is like the strategy above except the value of $c$ depends on the proportion of draws that have already occurred. For the strategy above $c$ is a constant function.

It can be checked that as $n\to\infty$ the probability A wins approaches $$ \int_0^1 \left(1-e^{-c(x)}\right)\exp\left(-\int_0^x c(t)\,dt\right)\,dx. $$ Doing some variational calculus, $c$ should satisfy the separable ODE $$ c’(x)=e^{c(x)}-c(x)-1, $$ along with the boundary condition $c(1)=\infty$ (I’m going to ignore convergence issues, and let’s index our draws starting at 0 so that we never actually need to evaluate $c(1)$). If we define $$ F(s):=1-\int_{s}^\infty \frac{1}{e^t-t-1}\,dt, $$ then $c=F^{-1}(x)$ (I believe $F$ cannot be expressed in terms of elementary functions). The function $c(x)$ is increasing, and blows up like $-\log(1-x)$ as $x\to 1$.

Plugging everything back into our expression for the probability A wins, and making substitutions to eliminate the inverse functions, we get that the probability A wins is $$ \int_{w}^\infty \frac{\left(1-e^{-x}\right)\exp\left(-\int_w^x\frac{t}{e^t-t-1}\,dt\right)}{e^x-x-1}\,dx, $$ where $w\approx 0.8662746635723$ is the unique positive real root of $F(s)$.

I computed this numerically and got $0.4205151954612$, so based on Robert Israel’s computations it might be reasonable to hope this strategy is asymptotically optimal.

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$.

Edit: I added a more general strategy below, giving a bound that seems likely to be optimal.

Player A will pick some positive constant $c$ and accept the first draw greater than $1-\frac{c}{n}$. The probability A sees such a draw is asymptotic to $1-e^{-c}$, and the value of the first such draw is uniform in $[1-c/n,1]$.

The probability that A wins using this strategy is asymptotic to $$ \left(1-e^{-c}\right)\cdot\frac{n}{c}\int_{1-c/n}^1 t^n\,dt\to \frac{\left(1-e^{-c}\right)^2}{c}. $$ This is maximized by taking $c\approx 1.25643$, giving a probability $\approx 0.407264$.

Variation: As bigO6377 points out in the comments, it's not optimal to choose $c$ to be a constant. We should be more likely to accept a draw that occurs near the end. Here's a strategy that does this.

Player A will choose a continuous function $c:[0,1]\to [0,\infty)$ (not depending on $n$), and will accept the $i$-th draw if its value is at least $1-c(i/n)/n$. This is like the strategy above except the value of $c$ depends on the proportion of draws that have already occurred. For the strategy above $c$ is a constant function.

It can be checked that as $n\to\infty$ the probability A wins approaches $$ \int_0^1 \left(1-e^{-c(x)}\right)\exp\left(-\int_0^x c(t)\,dt\right)\,dx. $$ To maximize this, we do some variational calculus and find that $c$ should satisfy the separable ODE $$ c’(x)=e^{c(x)}-c(x)-1, $$ along with the boundary condition $c(1)=\infty$ (I’m going to ignore convergence issues). If we define $$ F(s):=1-\int_{s}^\infty \frac{1}{e^t-t-1}\,dt, $$ then $c=F^{-1}(x)$ (I believe $F$ cannot be expressed in terms of elementary functions). The function $c(x)$ is increasing, and blows up like $-\log(1-x)$ as $x\to 1$.

Plugging everything back into our expression for the probability A wins, and making substitutions to eliminate the inverse functions, we get that the probability A wins is $$ \int_{w}^\infty \frac{\left(1-e^{-x}\right)\exp\left(-\int_w^x\frac{t}{e^t-t-1}\,dt\right)}{e^x-x-1}\,dx, $$ where $w\approx 0.8662746635723$ is the unique positive real root of $F(s)$.

I computed this numerically and got $0.4205151954612$, so based on Robert Israel’s computations it might be reasonable to hope this strategy is asymptotically optimal.

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$.

Edit: I added a more general strategy below, giving a bound that seems likely to be optimal.

Player A will pick some positive constant $c$ and accept the first draw greater than $1-\frac{c}{n}$. The probability A sees such a draw is asymptotic to $1-e^{-c}$, and the value of the first such draw is uniform in $[1-c/n,1]$.

The probability that A wins using this strategy is asymptotic to $$ \left(1-e^{-c}\right)\cdot\frac{n}{c}\int_{1-c/n}^1 t^n\,dt\to \frac{\left(1-e^{-c}\right)^2}{c}. $$ This is maximized by taking $c\approx 1.25643$, giving a probability $\approx 0.407264$.

Variation: As bigO6377 points out in the comments, it's not optimal to choose $c$ to be a constant. We should be more likely to accept a draw that occurs near the end. Here's a strategy that does this.

Player A will choose a continuous function $c:[0,1]\to [0,\infty)$ (not depending on $n$), and will accept the $i$-th draw if its value is at least $1-c(i/n)/n$. This is like the strategy above except the value of $c$ depends on the proportion of draws that have already occurred. For the strategy above $c$ is a constant function.

It can be checked that as $n\to\infty$ the probability A wins approaches $$ \int_0^1 \left(1-e^{-c(x)}\right)\exp\left(-\int_0^x c(t)\,dt\right)\,dx. $$ Doing some variational calculus, $c$ should satisfy the separable ODE $$ c’(x)=e^{c(x)}-c(x)-1, $$ along with the boundary condition $c(1)=\infty$ (I’m going to ignore convergence issues, and let’s index our draws starting at 0 so that we never actually need to evaluate $c(1)$). If we define $$ F(s):=1-\int_{s}^\infty \frac{1}{e^t-t-1}\,dt, $$ then $c=F^{-1}(x)$ (I believe $F$ cannot be expressed in terms of elementary functions). Plugging everything back into our expression for the probability A wins, and making substitutions to eliminate the inverse functions, we get that the probability A wins is $$ \int_{w}^\infty \frac{\left(1-e^{-x}\right)\exp\left(-\int_w^x\frac{t}{e^t-t-1}\,dt\right)}{e^x-x-1}\,dx, $$ where $w\approx 0.8662746635723$ is the unique positive real root of $F(s)$.

I computed this numerically and got $0.4205151954612$, so based on Robert Israel’s computations it might be reasonable to hope this strategy is asymptotically optimal.

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$.

Edit: I added a more general strategy below, giving a bound that seems likely to be optimal.

Player A will pick some positive constant $c$ and accept the first draw greater than $1-\frac{c}{n}$. The probability A sees such a draw is asymptotic to $1-e^{-c}$, and the value of the first such draw is uniform in $[1-c/n,1]$.

The probability that A wins using this strategy is asymptotic to $$ \left(1-e^{-c}\right)\cdot\frac{n}{c}\int_{1-c/n}^1 t^n\,dt\to \frac{\left(1-e^{-c}\right)^2}{c}. $$ This is maximized by taking $c\approx 1.25643$, giving a probability $\approx 0.407264$.

Variation: As bigO6377 points out in the comments, it's not optimal to choose $c$ to be a constant. We should be more likely to accept a draw that occurs near the end. Here's a strategy that does this.

Player A will choose a continuous function $c:[0,1]\to [0,\infty)$ (not depending on $n$), and will accept the $i$-th draw if its value is at least $1-c(i/n)/n$. This is like the strategy above except the value of $c$ depends on the proportion of draws that have already occurred. For the strategy above $c$ is a constant function.

It can be checked that as $n\to\infty$ the probability A wins approaches $$ \int_0^1 \left(1-e^{-c(x)}\right)\exp\left(-\int_0^x c(t)\,dt\right)\,dx. $$ Doing some variational calculus, $c$ should satisfy the separable ODE $$ c’(x)=e^{c(x)}-c(x)-1, $$ along with the boundary condition $c(1)=\infty$ (I’m going to ignore convergence issues, and let’s index our draws starting at 0 so that we never actually need to evaluate $c(1)$). If we define $$ F(s):=1-\int_{s}^\infty \frac{1}{e^t-t-1}\,dt, $$ then $c=F^{-1}(x)$ (I believe $F$ cannot be expressed in terms of elementary functions). The function $c(x)$ is increasing, and blows up like $-\log(1-x)$ as $x\to 1$.

Plugging everything back into our expression for the probability A wins, and making substitutions to eliminate the inverse functions, we get that the probability A wins is $$ \int_{w}^\infty \frac{\left(1-e^{-x}\right)\exp\left(-\int_w^x\frac{t}{e^t-t-1}\,dt\right)}{e^x-x-1}\,dx, $$ where $w\approx 0.8662746635723$ is the unique positive real root of $F(s)$.

I computed this numerically and got $0.4205151954612$, so based on Robert Israel’s computations it might be reasonable to hope this strategy is asymptotically optimal.

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$.

Edit: I added a more general strategy below, giving a bound that seems likely to be optimal.

Player A will pick some positive constant $c$ and accept the first draw greater than $1-\frac{c}{n}$. The probability A sees such a draw is asymptotic to $1-e^{-c}$, and the value of the first such draw is uniform in $[1-c/n,1]$. For the strategy above $c$ is a constant function.

The probability that A wins using this strategy is asymptotic to $$ \left(1-e^{-c}\right)\cdot\frac{n}{c}\int_{1-c/n}^1 t^n\,dt\to \frac{\left(1-e^{-c}\right)^2}{c}. $$ This is maximized by taking $c\approx 1.25643$, giving a probability $\approx 0.407264$.

Variation: As bigO6377 points out in the comments, it's not optimal to choose $c$ to be a constant. We should be more likely to accept a draw that occurs near the end. Here's a strategy that does this.

Player A will choose a continuous function $c:[0,1]\to [0,\infty)$ (not depending on $n$), and will accept the $i$-th draw if its value is at least $1-c(i/n)/n$. It can be checked that as $n\to\infty$ the probability A wins approaches $$ \int_0^1 \left(1-e^{-c(x)}\right)\exp\left(-\int_0^x c(t)\,dt\right)\,dx. $$ Doing some variational calculus, $c$ should satisfy the separable ODE $$ c’(x)=e^{c(x)}-c(x)-1, $$ along with the boundary condition $c(1)=\infty$ (I’m not going to worry about convergence issues, and let’s index our draws starting at 0 so that we never actually need to evaluate $c(1)$). If we define $$ F(s):=1-\int_{s}^\infty \frac{1}{e^t-t-1}\,dt, $$ then $c=F^{-1}(x)$ (I believe $F$ cannot be expressed in terms of elementary functions). Plugging everything back into our expression for the probability A wins, and making substitutions to eliminate the inverse functions, we get that the probability A wins is $$ \int_{w}^\infty \frac{\left(1-e^{-x}\right)\exp\left(-\int_w^x\frac{t}{e^t-t-1}\,dt\right)}{e^x-x-1}\,dx, $$ where $w\approx 0.8662746635723$ is the unique positive real root of $F(s)$.

I computed this numerically and got $0.4205151954612$, so based on Robert Israel’s computations it might be reasonable to hope this strategy is asymptotically optimal.

Not a complete solution, but a strategy showing that $\liminf F(n,n)>0.4$.

Edit: I added a more general strategy below, giving a bound that seems likely to be optimal.

Player A will pick some positive constant $c$ and accept the first draw greater than $1-\frac{c}{n}$. The probability A sees such a draw is asymptotic to $1-e^{-c}$, and the value of the first such draw is uniform in $[1-c/n,1]$.

The probability that A wins using this strategy is asymptotic to $$ \left(1-e^{-c}\right)\cdot\frac{n}{c}\int_{1-c/n}^1 t^n\,dt\to \frac{\left(1-e^{-c}\right)^2}{c}. $$ This is maximized by taking $c\approx 1.25643$, giving a probability $\approx 0.407264$.

Variation: As bigO6377 points out in the comments, it's not optimal to choose $c$ to be a constant. We should be more likely to accept a draw that occurs near the end. Here's a strategy that does this.

Player A will choose a continuous function $c:[0,1]\to [0,\infty)$ (not depending on $n$), and will accept the $i$-th draw if its value is at least $1-c(i/n)/n$. This is like the strategy above except the value of $c$ depends on the proportion of draws that have already occurred. For the strategy above $c$ is a constant function. 

It can be checked that as $n\to\infty$ the probability A wins approaches $$ \int_0^1 \left(1-e^{-c(x)}\right)\exp\left(-\int_0^x c(t)\,dt\right)\,dx. $$ Doing some variational calculus, $c$ should satisfy the separable ODE $$ c’(x)=e^{c(x)}-c(x)-1, $$ along with the boundary condition $c(1)=\infty$ (I’m going to ignore convergence issues, and let’s index our draws starting at 0 so that we never actually need to evaluate $c(1)$). If we define $$ F(s):=1-\int_{s}^\infty \frac{1}{e^t-t-1}\,dt, $$ then $c=F^{-1}(x)$ (I believe $F$ cannot be expressed in terms of elementary functions). Plugging everything back into our expression for the probability A wins, and making substitutions to eliminate the inverse functions, we get that the probability A wins is $$ \int_{w}^\infty \frac{\left(1-e^{-x}\right)\exp\left(-\int_w^x\frac{t}{e^t-t-1}\,dt\right)}{e^x-x-1}\,dx, $$ where $w\approx 0.8662746635723$ is the unique positive real root of $F(s)$.

I computed this numerically and got $0.4205151954612$, so based on Robert Israel’s computations it might be reasonable to hope this strategy is asymptotically optimal.