Two choice optimal stopping

In the best choice problem with random arrivals, an unknown number $n$ of rankable items arrive at times sampled from the uniform distribution. As is well known, a real-time player can ensure stopping at the overall best item with probability at least $1/e$, by waiting until time $1/e$ then selecting the first relatively best item to appear (if any). This paper discusses the issue of dominance in a wide class of stopping strategies of best choice, and argues that in fact the ...

We consider the problem of selecting sequentially a unimodal subsequence from a sequence of independent identically distributed random variables, and we find that a person doing optimal sequential selection does within a factor of the square root of two as well as a prophet who knows all of the random observations in advance of any selections. Our analysis applies in fact to selections of subsequences that have d+1 monotone blocks, and, by including the case d=0, our analysis...

This article proposes a new method of truncated estimation to estimate the tail index $\alpha$ of the extremely heavy-tailed distribution with infinite mean or variance. We not only present two truncated estimators $\hat{\alpha}$ and $\hat{\alpha}^{\prime}$ for estimating $\alpha$ ($0<\alpha \leq 1$) and $\alpha$ ($1<\alpha \leq 2$) respectively, but also prove their asymptotic statistical properties. The numerical simulation results comparing the six known estimators in esti...

Let $X_1,X_2,\ldots $ be independent random variables observed sequentially and such that $X_1,\ldots,X_{\theta-1}$ have a common probability density $p_0$, while $X_\theta,X_{\theta+1},\ldots $ are all distributed according to $p_1\neq p_0$. It is assumed that $p_0$ and $p_1$ are known, but the time change $\theta\in \mathbb{Z}^+$ is unknown and the goal is to construct a stopping time $\tau$ that detects the change-point $\theta$ as soon as possible. The existing approaches...

Let $S=\sum_{i=1}^{+\infty}\lambda_{i}Z_{i}$ where the $Z_{i}$'s are i.d.d. positive with $\mathbb{E}\| Z\| ^{3}<+\infty$ and $(\lambda_{i})_{i\in\mathbb{N}}$ a positive nonincreasing sequence such that $\sum\lambda_{i}<+\infty$. We study the small ball probability $\mathbb{P}(S<\epsilon) $ when $\epsilon\downarrow0$. We start from a result by Lifshits (1997) who computed this probability by means of the Laplace transform of $S$. We prove that $\mathbb{P}(S<\cdot) $ belongs t...

Given a stable L\'{e}vy process $X=(X_t)_{0\le t\le T}$ of index $\alpha\in(1,2)$ with no negative jumps, and letting $S_t=\sup_{0\le s\le t}X_s$ denote its running supremum for $t\in [0,T]$, we consider the optimal prediction problem \[V=\inf_{0\le\tau\le T}\mathsf{E}(S_T-X_{\tau})^p,\] where the infimum is taken over all stopping times $\tau$ of $X$, and the error parameter $p\in(1,\alpha)$ is given and fixed. Reducing the optimal prediction problem to a fractional free-bou...

We consider a discounted infinite horizon optimal stopping problem. If the underlying distribution is known a priori, the solution of this problem is obtained via dynamic programming (DP) and is given by a well known threshold rule. When information on this distribution is lacking, a natural (though naive) approach is "explore-then-exploit," whereby the unknown distribution or its parameters are estimated over an initial exploration phase, and this estimate is then used in th...

Let $Z=(Z_t)_{t\ge0}$ be a regular diffusion process started at $0$, let $\ell$ be an independent random variable with a strictly increasing and continuous distribution function $F$, and let $\tau_{\ell}=\inf\{t\ge0\vert Z_t=\ell\}$ be the first entry time of $Z$ at the level $\ell$. We show that the quickest detection problem \[\inf_{\tau}\bigl[\mathsf{P}(\tau<\tau_{\ell})+c\mathsf{E}(\tau -\tau_{\ell})^+\bigr]\] is equivalent to the (three-dimensional) optimal stopping prob...

Motivated by real-world machine learning applications, we analyze approximations to the non-asymptotic fundamental limits of statistical classification. In the binary version of this problem, given two training sequences generated according to two {\em unknown} distributions $P_1$ and $P_2$, one is tasked to classify a test sequence which is known to be generated according to either $P_1$ or $P_2$. This problem can be thought of as an analogue of the binary hypothesis testing...

Given a standard Brownian motion $B^{\mu}=(B_t^{\mu})_{0\le t\le T}$ with drift $\mu \in \mathbb{R}$ and letting $S_t^{\mu}=\max_{0\le s\le t}B_s^{\mu}$ for $0\le t\le T$, we consider the optimal prediction problem: \[V=\inf_{0\le \tau \le T}\mathsf{E}(B_{\tau}^{\mu}-S_T^{\mu})^2\] where the infimum is taken over all stopping times $\tau$ of $B^{\mu}$. Reducing the optimal prediction problem to a parabolic free-boundary problem we show that the following stopping time is opti...