Search

An exponential limit distribution is obtained for stopping times associated with partial sums of independent, identically distributed random variables whose distribution function is slowly varying at infinity. It is also demonstrated that a generalized law of the iterated logarithm cannot obtain in such a case.

The solution is found to the optimal stopping problem with payoff $$\sup_{\tau} E(S_{\tau} - \int_0^{\tau} c(X_t)dt),$$ where $S = (S_t)_{t \geq 0}$ is the maximum process associated with the one-dimensional time-homogeneous diffusion $X = (X_t)_{t \geq 0}$, the function $x \mapsto c(x)$ is positive and continuous, and the supremum is taken over all stopping times $\tau$ of $X$ for which the integral has finite expectation. It is proved, under no extra conditions, that this problem has a solution; that is, the payoff is finite and there is an optimal stopping time, if and only if the following maximality principle holds: the first-order nonlinear differential equation $$g'(s) = \frac{\sigma^2 (g(s))L'(g(s))}{2c(g(s))(L(s) - L(g(s)))}$$ admits a maximal solution $s \mapsto g_*(s)$ which stays strictly below the diagonal in $\mathbb{R}^2$. [In this equation $x \mapsto \sigma(x)$ is the diffusion coefficient and $x \mapsto L(x)$ the scale function of $X$.] In this case the stopping time $$\tau_* = \inf{t > 0|X_t \leq g_*(S_t)}$$ is proved optimal, and explicit formulas for the payoff are given. The result has a large number of applications and may be viewed as the cornerstone in a general treatment of the maximum process.

In this paper we provide sharp bounds on the $L_p$-norms of randomly stopped $U$-statistics. These bounds consist mainly of decoupling inequalities designed to reduce the level of dependence between the $U$-statistics and the stopping time involved. We apply our results to obtain Wald’s equation for $U$-statistics, moment convergence theorems and asymptotic expansions for the moments of randomly stopped $U$-statistics. The proofs are based on decoupling inequalities, symmetrization techniques, the use of subsequences and induction arguments.

Let $B$ be a brownian motion starting at 0. We denote by $L^\ast_t = \max_{x\in\mathbb{R}} L^\ast_t$ the maximum of local times at time $t$. The Barlow-Yor inequalities tell us that for every $p > 0$, there are constants $C_p > c_p > 0$ such that for every stopping time $\tau$, $c_p\mathbb{E}\lbrack\tau^{p/2}\rbrack \leq \mathbb{E}\lbrack L^{\ast p}_\tau\rbrack \leq C_p\mathbb{E}\lbrack\tau^{p/2}\rbrack.$ Given a fixed closed set $F \subset \mathbb{R}$, we give a condition on $F$ which is necessary and sufficient to derive similar inequalities with $\max_{x\in F}L^x_\tau$ instead of $L^\ast_\tau$ and we prove various related results.

A general set of distribution-free conditions is described under which an i.i.d. sequence of random variables is preserved under optional skipping. This work is motivated by theorems of J. L. Doob [Ann. of Math. 37 (1936) 363-367] and Z. Ignatov [Annuaire Univ. Sofia Fac. Math. Mech. 71 (1977) 79-94], unifying and extending aspects of both.

Consider a process $X(\cdot) = {X(t), 0 \leq t < \infty}$ with values in the interval $I = (0, 1)$, absorption at the boundary points of $I$, and dynamics $$dX(t) = \beta(t)dt + \sigma(t)dW(t),\quad X(0) = x.$$ ¶ The values $(\beta(t), \sigma(t))$ are selected by a controller from a subset of $\Re \times (0, \infty)$ that depends on the current position $X(t)$, for every $t \geq 0$. At any stopping rule $\tau$ of his choice, a second player, called a stopper, can halt the evolution of the process $X(\cdot)$, upon which he receives from the controller the amount $e^{-\alpha\tau}u(X(\tau))$; here $\alpha \epsilon [0, \infty)$ is a discount factor, and $u: [0, 1] \to \Re$ is a continuous “reward function.” Under appropriate conditions on this function and on the controller’s set of choices, it is shown that the two players have a saddlepoint of “optimal strategies.” These can be described fairly explicitly by reduction to a suitable problem of optimal stopping, whose maximal expected reward V coincides with the value of the game, $$V = \sup_{\tau} \inf_{X(\cdot)} \mathbf{E}[e^{-\alpha\tau}u(X(\tau))] = \inf_{X(\cdot)} \sup_{\tau} \mathbf{E}[e^{-\alpha\tau}u(X(\tau))].$$

A strong stationary time for a Markov chain $(X_n)$ is a stopping time $T$ for which $X_T$ is stationary and independent of $T$. Such times yield sharp bounds on certain measures of nonstationarity for $X$ at fixed finite times $n$. We construct an absorbing dual Markov chain with absorption time a strong stationary time for $X$. We relate our dual to a notion of duality used in the study of interacting particle systems. For birth and death chains, our dual is again birth and death and permits a stochastic interpretation of the eigenvalues of the transition matrix for $X$. The duality approach unifies and extends the analysis of previous constructions and provides several new examples.

Consider a catalytic super-Brownian motion $X =X^\Gamma$ with finite variance branching. Here “catalytic ” means that branching of the reactant $X$ is only possible in the presence of some catalyst. Our intrinsic example of a catalyst is a stable random measure $\Gamma$ on $\mathsf{R}$ of index $0

We consider a one-dimensional random walk $(X_n)_{n \times \mathbb{N}}$ in a random environment of zero or strictly positive drifts. We establish a full large deviation principle for $X_n/n$ of the correct order $n/(\log n)^2$ in the low speed regime, valid for almost every environment. This completes the large deviation picture obtained earlier by Greven and den Hollander and Gantert and Zeitouni in the case of zero and positive drifts. The proof uses coarse graining along with concentration of measure techniques.

The planar Brownian snake is a continuous, strong Markov process taking values in the space of continuous functions in $\mathbb{R}^2$ that are stopped at some time. For a fixed time the snake is distributed like a planar Brownian motion with a random lifetime. This paper characterizes the convex hull of the trace of the snake paths that exit the half-plane at the origin. It is shown that the convex hull at 0 is roughly a factor of x smoother than the convex hull of a piece of planar Brownian motion at its minimum y-value.

We prove the strong law of large numbers for a continuous-time version of reinforced random walk. This extends previous results of Durrett and Rogers.

Let $R$ be a random time in $\mathscr{F}_\infty$, the terminal element of a filtration $\mathscr{F}_t$ satisfying the usual hypotheses. It is shown that if optimal sampling holds at $R$ for all bounded martingales, then $R$ is optional. If $\mathscr{F}_t$ is the natural pseudo-path filtration of a measurable process $X_t$, then $R$ is optional if (and only if) the conditional distribution of $X_{R + .}$ given $\mathscr{F}_R$ is $Z_R$, where $Z_t$ is an optional version of the conditional distribution of $X_{t +.}$ given $\mathscr{F}_t$.

Let $X_i$ be i.i.d. random variables, $0 \leq X_i \leq 1$ and $c \geq 0$, and let $Y_i = X_i - ic$. It is shown that for all $n$, all $c$ and all such $X_i, E(\max_{i \geq 1} Y_i) - \sup_t EY_t < e^{-1}$, where $t$ is a stopping rule and $e^{-1}$ is shown to be the best bound for which the inequality holds. Specific bounds are also obtained for fixed $n$ or fixed $c$. These results are very similar to those obtained by Jones for a similar problem, where $0 \leq X_i \leq 1$ are independent but not necessarily identically distributed. All results are valid and unchanged also when $Y_i$ is replaced by $Y^\ast_i = \max_{1 \leq j \leq i} X_j - ic$.

Let $T$ be the first time that a perturbed random walk crosses a nonlinear boundary. This paper concerns the approximations of the distribution of the excess over the boundary, the expected stopping time $ET$ and the variance of the stopping time $\operatorname{Var}(T)$. Expansions are obtained by using linear renewal theorems with varying drift.

By a backward time is meant a random time which only depends on the future, in the same sense as a stopping time only depends on the past. We show that backward times taking values in a regenerative set $M$ split $M$ into conditionally independent subsets. The conditional distributions of the past may further be identified with the Palm distributions $P_t$ with respect to the local time random measure $\xi$ of $M$ both a.e. $E\xi$ and wherever $\{P_t\}$ has a continuous version. Continuity of $\{P_t\}$ occurs essentially where $E\xi$ has a continuous density, and the latter continuity set may be described rather precisely in terms of the growth rate and regularity properties of the Levy measure of $M$.

Let $S_n, n = 1,2, \cdots$ denote the partial sums of i.i.d. random variables with positive, finite mean and with a finite moment of order $r, 1 \leqq r < 2$. Let $Z_n, n = 1,2, \cdots$ denote the partial sums of i.i.d. random variables with a finite moment of order $r, 0 < r < 2$, and with mean 0 if $1 \leqq r < 2$. Let $N(c) = \min \{n; S_n > c\}, c \geqq 0$. Theorem 1 states that $N(c)$, (suitably normalized), tends to 0 in $r$-mean as $c \rightarrow \infty$. The first part of that proof follows by applying Theorem 2, which generalizes the known result $E|Z_n|^r = o(n)$, as $n\rightarrow \infty$ to randomly indexed partial sums.

The optional sampling theorem for martingales indexed by a partially ordered set is true if the index set is directed. However, the corresponding result for submartingales indexed by a partially ordered set is not true in general. In this paper we completely characterize the class of stopping times for which the optional sampling theorem is true for all uniformly bounded submartingales indexed by countable partially ordered sets. By assuming a conditional independence property, we show that when the index set is $R^2$ the optional sampling theorem is true for all uniformly bounded, right continuous submartingales and all stopping times. This conditional independence property is satisfied in cases where the submartingales and stopping times are measurable with respect to the two-parameter Wiener process. A counterexample shows that the optional sampling result is false for $R^n$ when $n > 2$ even if the conditional independence property is satisfied.

A local convergence theorem for a class of martingales with multidimensional time parameter is proved. This is accomplished by an elaboration of stopping time arguments used in the one-dimensional setting.

Consider a sequence of dependent events, where each has uniformly small conditional probability given the past, and the sum of the conditional probabilities is approximately constant at $a$. Then the number of events which occur is approximately Poisson with parameter $a$. An explicit bound is given on the variation distance.

For the study of the paths of stochastic processes, the upcrossing-down-crossing arguments are available in the real-valued case but not in the vector-valued case. We use in this article stopping time methods and the Kadec-Klee renorming theorem to obtain regularity properties for Banach-lattice valued submartingales and Banach-valued pramarts.

We apply the concept of stopping times of martingales to problems in classical probability theory regarding the occurrence of sequence patterns in repeated experiments. For every finite collection of sequences of possible outcomes, we compute the expected waiting time till one of them is observed in a run of experiments. Also we compute the probability for each sequence to be the first to appear. The main result, with a transparent proof, is a generalization of some well-known facts on Bernoulli process including formulas of Feller and the "leading number" algorithm of Conway.

Let $S_n, n = 1,2,3, \cdots$, denote the partial sums of i.i.d. random variables with positive, finite mean. The first passage times $\min \{n; S_n > c\}$ and $\min \{n; S_n > c \cdot a(n)\}$, where $c \geqq 0$ and $a(y)$ is a positive, continuous function on $\lbrack 0, \infty)$, such that $a(y) = o(y)$ as $y \uparrow \infty$, are investigated. Necessary and sufficient conditions for finiteness of their moments and moment generating functions are given. Under some further assumptions on $a(y)$, asymptotic expressions for the moments and the excess over the boundary are obtained when $c \rightarrow \infty$. Convergence to the normal and stable distributions is established when $c \rightarrow \infty$. Finally, some of the results are generalized to a class of random processes.

Consider a recurrent random walk $\{X_n\}$ with state space $S \subseteqq R^d (d \leqq 2)$. A stopping time $T$ is called subterminal if it satisfies a technical condition which essentially states that it is the first time a path possesses some property which does not depend on how long the process has been running. Suppose $T$ is a subterminal time which can occur only when $\{X_n\}$ is in a bounded set; then under an additional assumption a ratio limit theorem (as $n \rightarrow \infty$) is obtained for $P(T > n \mid X_0 = x) (x\in S)$. The theorem applies in particular to the hitting time of a bounded set with nonempty interior in the general case, and to the hitting time of a bounded set with nonzero Haar measure in the nonsingular case.

For an urn model (arising typically in the sequential estimation of the size of a finite population), along with an invariance principle for a partial sequence of nonnegative random variables, a renewal theorem relating to some stopping times is established. A representation of these random variables in terms of linear combinations of some martingale-differences provides the key to a simple solution. 1. Introduction. The following urn model arises typically in the sequential estimation of the total size of a finite population. An urn contains an unknown number N of white balls and no others. We repeatedly draw a ball at random, observe its color and replace it by a black ball, so that before each draw, there are N balls in the urn. Let W,, be the number of white balls observed in the first n draws, n -1 (Wo = 0, Wi X 1 and W1k ' k, k - 2). For large N (and n, satisfying n/N -o a: 0 0, consider the stopping variable

Let $Y_t$ be a stochastic process starting at $y$ which changes by i.i.d. dichotomous increments $X_t$ with mean 0 and variance 1. The cost of proceeding one step is one and the payoff is zero unless $n$ steps are taken and the final value $\hat{Y}$ of $Y_t$ is negative in which case the payoff is $\hat{Y}^2$. The optimal procedure consists of stopping as soon as $Y_t \geq \tilde{y}_m$ where $m$ is the number of steps left to be taken. The limit of $\tilde{y}_m$ as $m \rightarrow \infty$ is desired as a function of $p = P(X_t < 0)$. This limit $\tilde{y}$ is evaluated for $p$ rational and proved to be continuous in $p$. One can use $\tilde{y}$ to relate the solution of optimal stopping problems involving a Wiener process to those involving certain discrete-time discrete-process stopping problems. Thus $\tilde{y}$ is useful in calculating simple numerical approximations to solutions of various stopping problems.

A class of optimal stopping problems for conditioned random walk is discussed in terms of selling strategies for the stock market.

Let $S_n, n = 1, 2, 3, \cdots$ denote the recurrent random walk formed by the partial sums of i.i.d. lattice random variables with mean zero and finite variance. Let $T_{\{x\}} = \min \lbrack n \geqq 1 \mid S_n = x \rbrack$ with $T \equiv T_{\{0\}}$. We obtain a local limit theorem for the random walk conditioned by the event $\lbrack T > n \rbrack$. This result is applied then to obtain an approximation for $P\lbrack T_{\{x\}} = n \rbrack$ and the asymptotic distribution of $T_{\{x\}}$ as $x$ approaches infinity.

A generalized problem of optimal stopping is defined, which has a solution in the class of quasi-stopping times, which generalize the classical stopping times. The optimal quasi-stopping times are fully characterized. By time reversal, on a Markov process, various results of Meyer, Mokobodzki and Rost are interpreted as results of existence of optimal quasi-stopping times for the reversed process. Finally, a game on quasi-stopping times is solved.

For $X_1, X_2,\cdots$ i.i.d., $EX_1 = \mu \neq 0, S_n = X_1 + \cdots + X_n$, the asymptotic behavior of moments and error rates of the two-sided stopping rules $\inf \{n \geq 1: |S_n| > cn^\alpha\}, c > 0, 0 \leq \alpha < 1$, is considered. Convergence of (normalized) moments of all orders as $c \rightarrow \infty$ is obtained, without the higher moment assumptions needed in the one-sided case of extended renewal theory (Gut, 1974), and in a more general setting than just the i.i.d. case. Necessary and sufficient conditions are given for convergence of series involving the error rates, in terms of the moments of $X_1$.

This article tries to unify best choice problems under total ignorance of both the candidates, quality distribution and the distribution of the number of candidates. The result is what we shall call the $e^{-1}$-law because of the multiple role which is played by $e^{-1}$, and this in a more general context as only in the solution of the classical secretary problem. The unification is possible whenever best choice problems can be redefined as continuous time decision problems on conditionally independent arrivals. We shall also give several examples to illustrate how the approach and its implications compare with other models.

For $X_1, X_2, \cdots$ i.i.d. with finite mean and $Y_n = \max(X_1, \cdots, X_n) - cn, c$ positive, a number of authors have considered the problem of determining an optimal stopping rule for the reward sequence $Y_n$. The optimal stopping rule can be given explicitly in this case; however, in general its use requires complete knowledge of the distribution of the $X_i$. This paper examines the problem of approximating the optimal expected reward when only partial information about the distribution is available. Specifically, if the $X_i$ are known to be exponentially distributed with unknown mean, stopping rules designed to approximate the optimal rule (which can be used only when the mean is known) are proposed. Under certain conditions the difference between the expected reward using the proposed stopping rules and the optimal expected reward vanishes as $c$ approaches zero.

On obtient la fonction generatrice des moments du temps auquel le mouvement brownien sort d'une region bornee par deux lignes droites non convergentes, en utilisant le theoreme d'arret des martingales

A definition of duality for pairs of stopping times of any random walk is motivated by the duality relation of ascending and descending ladder epochs $N, \bar{N}$ of random walk in $R^1$. Dual pairs share several of the properties of the pair $N, \bar{N}$.

Let $R_n$ be the number of distinct elements among $X_0, X_1,\cdots, X_n$, where $\{X_n\}$ is an irreducible recurrent Markov chain. It is shown that, under an appropriate condition, $n^{-1}R_n \rightarrow 0$ a.s. $(P_a)$ where $a$ is any state and $P_a$ is conditional probability measure given $X_0 = a$. We prove that any recurrent random walk satisfies our condition, so that the result contains the well-known random walk case. We also give an example of an irreducible recurrent chain for which the result fails to hold.

We determine $E\lbrack \exp (\alpha X(T) - \beta T) \rbrack$ where $X(t)$ is a Brownian motion having arbitrary drift and variance and $T$ is the first time the process drops a specified amount below its maximum to date. From this result, the moments of $X(T)$ and $T$ and some asymptotic distributions may be found. Applications in process control and financial management are mentioned.

In this paper we make comparisons involving stopping times $\tau$ of a process $X$ and the maximal function $X^\ast_\tau$ of that process, where $X$ is either Brownian motion or random walk. In particular, we give conditions implying that $P(X^\ast_\tau > \lambda) \approx P(\tau^{1/2} > \lambda)$ in the sense of a two-sided inequality holding. We show that if, for all large $\lambda$ there exist constants $\beta > 1$ and $\gamma > 0$ satisfying $$0 < P(\tau^{1/2} > \lambda) \leq \gamma P(\tau^{1/2} > \beta\lambda),$$ and if $X$ is a one-dimensional Brownian motion, then $P(X^\ast_\tau > \lambda) \approx P(\tau^{1/2} > \lambda)$. An analogous result is given for $n$-dimensional Brownian motion $(n \geq 3)$. We also consider a similar result for one-sided maximal functions of local martingales. Finally, we look at a random walk $X$, where $X_n = x_1 + x_2 + \cdots + x_n$, and give two different sets of conditions on $\tau$ and the $x_i$'s under which the result $P(\tau^{1/2} > \lambda) \approx P(X^\ast_\tau > \lambda)$ is true.

Multi-parameter martingales and amarts can be studied using methods developed for amarts defined on a directed set by A. Millet and L. Sucheston. To study an amart indexed by $\mathbb{N} \times \mathbb{N}$, we use an associated process indexed by the "lower layers" of $\mathbb{N} \times \mathbb{N}$. J. B. Walsh's convergence theorem for two-parameter strong martingales is recovered as a special case. Vector-valued versions of some of the results are also stated.

This is a guide to some recent work in the theory of martingale inequalities. Methods are simplified; some new proofs are given. A number of new results are also included.

In $R^n$, Brownian diffusion leads to the normal or Gaussian distribution. On the sphere $S^n$, diffusion does not lead to the Fisher distribution which often plays the role of the normal distribution on $S^n$. On the circle $(S^1)$ and sphere $(S^2)$, they are known to be numerically close. It is shown that there exists a random stopping time for the diffusion which leads to the Fisher distribution. This follows from the fact, proved here, that the modified Bessel function $I_v(x)$ is a completely monotone function of $v^2$ (for fixed $x > 0$). More generally, we study the class of distributions on $S^n$ which can be represented as mixtures of diffusions. The stopping time distribution is characterized, but not given in computable form. Also, three new distribution functions involving Bessel functions are presented.

Let $X$ be a transient right (Markov) process on a compact metric space including a death point. Let $\mu$ and $\nu_n$ be finite measures whose potentials satisfy $\mu U \geq \cdots \geq \nu_nU \geq \cdots \geq \nu_1 U$. We prove that there exists a right-continuous stochastic process $Y = (\tilde\Omega, \mathscr{M}, \tilde\mathscr{M}_t, Y_t Q)$ that is a version of $X$ with initial measure $\nu_\infty(\cdot) = Q(Y_0 \in \cdot)$ and in which there are $(\tilde\mathscr{M}_t)$-stopping times $\tilde{\tau}_n \downarrow 0$ with $Q(Y(\tilde{\tau}_n) \in \cdot, \tilde{\tau}_n < \infty) = \nu_n(\cdot)$. Furthermore, a canonical representation of $Y$ and $(\tilde{\tau}_n)$ is given in which one has a better understanding of the tail behavior of the sequence $\tilde{\tau}_n$. Based on this representation an open question is posed whose answer in the positive would permit defining in $X$, assuming it admits a continuous real random variable independent of the path, decreasing stopping times $T_n$ such that $P^\mu(X(T_n) \in \cdot, T_n < \infty) = \nu_n(\cdot)$. These $T_n$ would satisfy the Markov property $T_n = T_{n+1} + S_n \circ \theta(T_{n+1}), S_n$ a stopping time linking $\nu_n$ and $\nu_{n+1}$. Fitzsimmons has now proved the existence of a desired decreasing sequence $T_n$ in $X$ for any given $\mu$ and $\nu_n$ as above, using a very different approach. His $T_n$, however, do not satisfy the Markov property.

Let $\{X_n\}$ be a sequence of independent Banach space valued random elements with partial sums $S_n = X_1 + \cdots + X_n$. Then let $T$ be any possibly randomized stopping time based on $\{X_n\}$. Fix any $\alpha > 0$ and let $\Phi(\cdot)$ be any nondecreasing continuous function on $\lbrack 0, \infty)$ with $\Phi(0) = 0$ such that $\Phi(cx) \leq c^\alpha\Phi(x)$ for all $x \geq 0, c \geq 2$. Put $S^\ast_n = \max_{1 \leq k \leq n}\|S_k\|$ and $a^\ast_n = E\Phi(S^\ast_n)$. It is proved that there exists a universal constant $c^\ast_\alpha < \infty$ depending only on $\alpha$ [and otherwise independent of $(B, \|\cdot\|), \{X_n\}, T \text{and} \Phi(\cdot)$] such that $Ea^\ast_T \leq c^\ast_\alpha E\Phi(S^\ast_T)$. As a consequence, $E\Phi(S^\ast_{T_c}) = \infty$ whenever $P(T_c < \infty) = 1$ and $c \geq c^\ast_\alpha$, where \begin{equation*}T_c = \begin{cases} \text{first} n: c^\Phi(S^\ast_n) < a^\ast_n,\\ \infty, \text{if no such} n \text{exists}.\end{cases}\end{equation*} In fact, $Ea^\ast_{T_c} = \infty$, too. An upper bound for $c^\ast_\alpha$ is constructed.

An upper bound for $E(\sup_{0\leqslant s\leqslant\tau}\|M_s\|^2)$, where $M$ is a square integrable martingale and $\tau$ a stopping time is given in terms of $\lbrack M\rbrack_{\tau^-}$ and $\langle M\rangle_{\tau^-}$. Counter examples show that $4E(\langle M\rangle_{\tau^-})$, which is easily derived as an upper bound from a classical Doob's inequality, when $\tau$ is predictable or totally unaccessible, is no longer an upper bound in general. The obtained majoration is used to prove existence and uniqueness of strong solutions of a stochastic equation $dX_t = a(t, X) dZ_t$, where $a$ is a functional, depending possibly on the whole past of $X$ before $t$, and $Z$ is a semimartingale. Our result thus extends to systems "with memory" recent results by Protter, Kazamaki, Doleans-Dade and Meyer.