Optimal stopping on trajectories and the ballot problem (Q4537302)

The author considers the following optimal stopping problem: there are \(m\) minus balls and \(p\) plus balls in an urn and let \(X_k\) be random variables which take \(-1\) if minus ball is drawn and \(+1\) if plus ball is done at the \(k\)th draw. The process \(\{Z_n\}^{m+p}_{n= 0}\) is defined by \(Z_0= 0\) and \(Z_n= \sum^n_{k=1} X_k\), \(1\leq n\leq m+p\). The objective is to find a stopping rule \(\sigma^*_1\) such that \[ P\Biggl(Z_{\sigma^*_1}= \max_{0\leq n\leq m+p} Z_n\Biggr)= \sup_{\sigma\in C} P\Biggl(Z_\sigma= \max_{0\leq n\leq m+ p}Z_n\Biggr), \] where \(C\) is the class of all stopping times. Then, by using several results obtained from the ballot problem, the author shows that an optimal stopping rule is given by \[ \sigma^*_1= \min\Biggl\{0\leq n\leq m+p: Z_n= \max_{0\leq j\leq n} Z_j, Z_n\geq f_n(m, p)\Biggr\}, \] where \(f_n(m,p)= \sqrt{m+ p+1-n}-(m- p+1)\), \(0\leq n\leq m+p\). He also considers modifications of the problem, one of which is to seek a stopping rule \(\sigma^*_r\) such that \[ P\Biggl(Z_{\sigma^*_r}\geq \max_{0\leq n\leq m+p} Z_n- (r-1)\Biggr)= \sup_{\sigma\in C} P\Biggl(Z_\sigma\geq \max_{0\leq n\leq m+p} Z_n- (r-1)\Biggr). \] For this problem, it is given an optimal stopping rule \(\sigma^*_2\) as \[ \sigma^*_2= \min\Biggl\{0\leq n\leq m_p: Z_n= \max_{0\leq j\leq n} Z_j- 1, Z_n\geq f_n(m+ 1,p)\Biggr\} \] when \(r=2\). Another modification is to detect the last peak of the process. Finally, it is shown how the process \(\{Z_n\}^{m+ p}_{n=0}\) can be associated with a backward martingale to yield the ballot theorem.