Two choice optimal stopping

We consider the classical sequential binary hypothesis testing problem in which there are two hypotheses governed respectively by distributions $P_0$ and $P_1$ and we would like to decide which hypothesis is true using a sequential test. It is known from the work of Wald and Wolfowitz that as the expectation of the length of the test grows, the optimal type-I and type-II error exponents approach the relative entropies $D(P_1\|P_0)$ and $D(P_0\|P_1)$. We refine this result by ...

Given a gamma population with known shape parameter $\alpha$, we develop a general theory for estimating a function $g(\cdot)$ of the scale parameter $\beta$ with bounded variance. We begin by defining a sequential sampling procedure with $g(\cdot)$ satisfying some desired condition in proposing the stopping rule, and show the procedure enjoys appealing asymptotic properties. After these general conditions, we substitute $g(\cdot)$ with specific functions including the gamma ...

We use the geometry of functions associated with martingales under nonlinear expectations to solve risk-sensitive Markovian optimal stopping problems. Generalising the linear case due to Dynkin and Yushkievich (1969), the value function is the majorant or pointwise infimum of those functions which dominate the gain function. An emphasis is placed on the geometry of the majorant and pathwise arguments, rather than exploiting convexity, positive homogeneity or related analytica...

Let $X_{1,n} \leq .... \leq X_{n,n}$ be the order statistics associated with a sample $X_{1}, ...., X_{n}$ whose pertaining distribution function (% \textit{df}) is $F$. We are concerned with the functional asymptotic behaviour of the sequence of stochastic processes \begin{equation} T_{n}(f,s)=\sum_{j=1}^{j=k}f(j)\left(\log X_{n-j+1,n}-\log X_{n-j,n}\right)^{s}, \label{fme} \end{equation} indexed by some classes $\mathcal{F}$ of functions $f:\mathbb{N}% ^{\ast}\longmapsto \m...

Prophet inequalities for rewards maximization are fundamental to optimal stopping theory with extensive applications to mechanism design and online optimization. We study the \emph{cost minimization} counterpart of the classical prophet inequality: a decision maker is facing a sequence of costs $X_1, X_2, \dots, X_n$ drawn from known distributions in an online manner and \emph{must} ``stop'' at some point and take the last cost seen. The goal is to compete with a ``prophet'' ...

We present a method for upper and lower bounding the right and the left tail probabilities of continuous random variables (RVs). For the right tail probability of RV $X$ with probability density function $f_X(x)$, this method requires first setting a continuous, positive, and strictly decreasing function $g_X(x)$ such that $-f_X(x)/g'_X(x)$ is a decreasing and increasing function, $\forall x>x_0$, which results in upper and lower bounds, respectively, given in the form $-f_X(...

In this article, a general problem of sequential statistical inference for general discrete-time stochastic processes is considered. The problem is to minimize an average sample number given that Bayesian risk due to incorrect decision does not exceed some given bound. We characterize the form of optimal sequential stopping rules in this problem. In particular, we have a characterization of the form of optimal sequential decision procedures when the Bayesian risk includes bot...

Most of the literature on online algorithms and sequential decision-making focuses on settings with "irrevocable decisions" where the algorithm's decision upon arrival of the new input is set in stone and can never change in the future. One canonical example is the classic prophet inequality problem, where realizations of a sequence of independent random variables $X_1, X_2,\ldots$ with known distributions are drawn one by one and a decision maker decides when to stop and acc...

The main purpose of this paper is to correct an error in the previously submitted version [*] := arXiv:2004.13749v1. [*] had been already accepted for publication in a scientific journal, but withdrawn by the author after the discovery of the error. For the withdrawal from arXiv we follow their preference to maintain what remains of interest. The background of the open problem, and the brief survey which comes with it, stay relevant. These keep their place in the present corr...

Let X_t, 0<=t<=T be a one-dimensional stochastic process with independent and stationary increments. This paper considers the problem of stopping the process X_t "as close as possible" to its eventual supremum M_T:=sup{X_t: 0<=t<=T}, when the reward for stopping with a stopping time tau<=T is a nonincreasing convex function of M_T-X_tau. Under fairly general conditions on the process X_t, it is shown that the optimal stopping time tau is of "bang-bang" form: it is either opti...