At the beginning of Ferguson's notes on Optimal Stopping (https://www.math.ucla.edu/~tom/Stopping/Contents.html) a general definition of stopping rule is introduced. Denoting with $N$ the random time at which stopping occurs, associated with the observed process $\{X_n\}$, it is defined in terms of its probability of stopping at time $n$, given observations $X_1=x_1,\ldots,X_n=x_n$, that is in terms of the functions $\phi_n(x_1,\ldots,x_n)=\mathbb{P}(N=n|N\geq n,X_1=x_1,\ldots,X_n=x_n)$, where $0\leq\phi_n\leq 1$. The author calls this a randomised stopping rule. According to this definition, a randomised stopping rule is not in general a stopping time, since the event of stopping is not determined by the process $X$ alone (as usual, I call a stopping time a random time $N$ such that $\{N=n\}\in\mathcal{F}_n=\sigma(X_1,\ldots,X_n)$). Is my understanding correct? Thanks for sharing any advice. I found several definitions of randomised stopping rules on the internet, but there seems to be little agreement, and this seems to be the most general I encountered so far.
Randomised stopping time
probabilityprobability distributionsprobability theorystopping-times
Related Solutions
It sometimes is a useful exercise to separate the random from the non-random pieces of the puzzle.
Let's build up a stopping time, starting without randomness, along the lines of your intuition. Suppose that the observations $X_j$ take values in the space $S$, and let $S^\mathbb{N}$ be the space of $S$-valued sequences.
For any strategy or stopping policy, and any $0\leq n<\infty$ we may define a two-valued map $\phi_n:S^\mathbb{N}\to\{\mbox{GO},\mbox{STOP}\}$ which tells me what to do at time $n$ if I were to observe $s=(s_0,s_1,\dots)$. We require that $\phi_n(s)$ only depends on the first part of the sequence $(s_0,s_1,\dots,s_n)$. That is, the decision to stop at time $n$ must only depend on the observations up to time $n$. No peeking into the future!
Now define $\phi(s)=\inf(n\geq 0: \phi_n(s)=\mbox{STOP})$, where the infimum over the empty set is $\infty$. This gives a map $\phi:S^\mathbb{N}\to \mathbb{N}\cup \{\infty\}$ which expresses our policy, by telling us when to stop.
Finally we can put probability back into the picture by defining $\tau:\Omega\to \mathbb{N}\cup \{\infty\}$ by $$\tau(\omega)=\phi(X_0(\omega), X_1(\omega), X_2(\omega), \dots ).$$ This random variable is the stopping strategy applied to the random sequence $(X_0(\omega), X_1(\omega), X_2(\omega), \dots)$.
Every stopping time $\tau$ can be expressed like this for some such $\phi$.
For $0\leq n< \infty$, by the Doob-Dynkin lemma, there is a measurable map
$\varphi_n:(S^\mathbb{N},{\cal G}_n) \to \{0,1\}$ so that $1_{[\tau=n]}=\varphi_n(X_0,X_1,X_2,\dots)$.
Here ${\cal G}_n$ is the $\sigma$-field generated by the coordinate maps $s_j$ for $0\leq j\leq n$. Now let $\phi(s)=\inf(n\geq 0: \varphi_n(s)=1)$.
Hints:
- The stopped process $M_n := 3^{X_1+\ldots+X_{n \wedge \tau}}$ is also a martingale; hence, $$\mathbb{E}M_n = \mathbb{E}M_1.$$ Calculate $\mathbb{E}M_1$.
- By the strong law of large numbers, $$\frac{X_1+\ldots+X_n}{n} \to \mathbb{E}X_1 = - \frac{1}{3}.$$ Thus, $$X_1+\ldots+X_n \to - \infty \quad \text{almost surely as} \, \, n \to \infty.$$
- Conclude that $$\begin{align*} M_n &= 3^{X_1+\ldots+X_n} 1_{\{ \tau=\infty\}} + 3^{X_1+\ldots+X_{n \wedge \tau}} 1_{\{\tau<\infty\}}\\ &\to 0 + 3^1 1_{\{\tau<\infty\}}. \end{align*}$$
- Deduce from step 1 and 3 that $$\mathbb{P}(\tau<\infty) = \frac{1}{3}.$$
Best Answer
A randomized stopping rule corresponds to a stopping time for an enlarged filtration. Let $U_1,U_2,\dots$ be i.i.d. variables that are uniform in $[0,1]$ and independent of the process $\{X_j\}_{j \ge 1}$. Let $\mathcal G_n$ be the $\sigma$-field generated by $X_1,U_1,\dots,X_n,U_n$. Then the stopping time $\tau$ (I prefer that notation rather than $N$) can be defined by $$\tau:=\min\{n \ge 1 :\, U_n\le \phi_n(X_1,\dots,X_n)\}\,.$$ Clearly, $\tau$ is a stopping time for the filtration $\{\mathcal G_n\}$, and it satisfies $$\mathbb{P}(\tau=n|\tau\geq n,X_1=x_1,\ldots,X_n=x_n) =\phi_n(x_1,\ldots,x_n) \,.$$