Brownian Optimal Stopping and Random Walks

One way to compute the value function of an optimal stopping problem along Brownian paths consists of approximating Brownian motion by a random walk. We derive error estimates for this type of approximation under various assumptions on the distribution of the approximating random walk.     

Brownian Optimal Stopping and Random Walks

One way to compute the value function of an optimal stopping problem along Brownian paths consists of approximating Brownian motion by a random walk. We derive error estimates for this type of approximation under various assumptions on the distribution of the approximating random walk.     

A stopping rule for choosing the best of three coins

A recently proposed stopping rule for choosing the best of three coins is presented as the first exit time from a certain polygonal region by a two-dimensional random walk. A diffusion approximation to the expected value of this exit time is developed, using techniques of conformal mapping. An algebraic method for calculating the exact value of this expectation is also described.     

A bivariate stable characterization and domains of attraction

Bivariate stable distributions are defined as those having a domain of attraction, where vectors are used for normalization. These distributions are identified and their domains of attraction are given in a number of equivalent forms. In one case, marginal convergence implies joint convergence. A bivariate optional stopping property is given. Applications to bivariate random walk are suggested.     

On infinite horizon optimal stopping of general random walk

The objective of this study is to provide an alternative characterization of the optimal value function of a certain Black–Scholes-type optimal stopping problem where the underlying stochastic process is a general random walk, i.e. the process constituted by partial sums of an IID sequence of random variables. Furthermore, the pasting principle of this optimal stopping problem is studied.      

Degeneracy condition for the optimal moment in the optimal stop problem for a functional of a skewed down random walk and its maximum

The paper presents a new class of functions dependent on a skewed down random walk and its maximum such that the optimal moment in the optimal stopping problem for this function on a finite time interval is trivial and equal to the beginning of the interval.     

Asymptotic variance of the self-intersections of stable random walks using Darboux-Wiener theory

We present a Darboux-Wiener type lemma as a powerful alternative to the classical Tauberian theorem when monotonicity is not known a priori. We apply it to obtain the exact asymptotics of the variance of the self-intersections of a one-dimensional stable random walk. Finally we prove a functional central limit theorem for stable random walk in random scenery conjectured in [1].     

Martingale convergence and the stopped branching random walk

We discuss the construction of stopping lines in the branching random walk and thus the existence of a class of supermartingales indexed by sequences of stopping lines. Applying a method of Lyons (1997) and Lyons, Pemantle and Peres (1995) concerning size biased branching trees, we establish a relationship between stopping lines and certain stopping times. Consequently we develop conditions under which these supermartingales are also martingales. Further we prove a generalization of Biggins' Martingale Convergence Theorem, Biggins (1977a) within this context. Received: 21 December 1998 / Revised version: 28 June 1999 / Published online: 7 February 2000     

On the exact distributional asymptotics for the supremum of a random walk with increments in a class of light-tailed distributions

We study the distribution of the maximum M of a random walk whose increments have a distribution with negative mean which belongs for some γ > 0 to a subclass of the class S _γ (for example, see Chover, Ney, and Wainger [5]). For this subclass we provide a probabilistic derivation of the asymptotic tail distribution of M and show that the extreme values of M are in general attained through some single large increment in the random walk near the beginning of its trajectory. We also give some results concerning the “spatially local” asymptotics of the distribution of M, the maximum of the stopped random walk for various stopping times, and various bounds.     

Generalized best choice problem based on the information economics approach

We consider the problem of choosing the ‘best choice’ among a certain number of objects that are presented to a decision-maker in sequential order. Such a sequential selection problem is commonly referred to as the ‘best choice problem’, and its optimal stopping rule has been obtained either via the dynamic programming approach or via the Markovian approach. Based on the theory of information economics, we propose in the paper the third approach to a generalized version of the best choice problem that is intuitively more appealing. Various types of the best choice problem, such as (1) the classical secretary problem, (2) no information group interview problem, and (3) full information best choice problem with a random walk process, are shown to be special cases of the generalized best choice problem. The modelling framework of information economics has potential for building theory that ultimately would produce practical stopping rules.     

On time-inconsistent stopping problems and mixed strategy stopping times

A game-theoretic framework for time-inconsistent stopping problems where the time-inconsistency is due to the consideration of a non-linear function of an expected reward is developed. A class of mixed strategy stopping times that allows the agents in the game to jointly choose the intensity function of a Cox process is introduced and motivated. A subgame perfect Nash equilibrium is defined. The equilibrium is characterized and other necessary and sufficient equilibrium conditions including a smooth fit result are proved. Existence and uniqueness are investigated. A mean–variance and a variance problem are studied. The state process is a general one-dimensional Itô diffusion.     

Optimal variance stopping with linear diffusions

We study the optimal stopping problem of maximizing the variance of an unkilled linear diffusion. Especially, we demonstrate how the problem can be solved as a convex two-player zero-sum game, and reveal quite surprising application of game theory by doing so. Our main result shows that an optimal solution can, in a general case, be found among stopping times that are mixtures of two hitting times. This and other revealed phenomena together with suggested solution methods could be helpful when facing more complex non-linear optimal stopping problems. The results are illustrated by a few examples.     

Approximations and Inequalities for Moving Sums

In this article accurate approximations and inequalities are derived for the distribution, expected stopping time and variance of the stopping time associated with moving sums of independent and identically distributed continuous random variables. Numerical results for a scan statistic based on a sequence of moving sums are presented for a normal distribution model, for both known and unknown mean and variance. The new R algorithms for the multivariate normal and t distributions established by Genz et?al. (2010) provide readily available numerical values of the bounds and approximations.     

Mean and variance of first passage time of non-homogeneous random walk

The prime concern of this paper is the first passage time of a non-homogeneous random walk, which is nearest neighbor but able to stay at its position. It is revealed that the branching structure of the walk corresponds to a 2-type non-homogeneous branching process and the first passage time of the walk can be expressed by that branching process. Therefore, one can calculate the mean and variance of the first passage time, though its exact distribution is unknown.     

Critical survival barrier for branching random walk

We consider a branching random walk with an absorbing barrier, where the associated one-dimensional random walk is in the domain of attraction of an α-stable law. We shall prove that there is a barrier and a critical value such that the process dies under the critical barrier, and survives above it. This generalizes previous result in the case that the associated random walk has finite variance.     

Market efficiency of Brazilian exchange rate: Evidence from variance ratio statistics and technical trading rules

This study utilizes the variance ratio test to examine the behavior of Brazilian exchange rate. We show that adjustments for multiple tests and a bootstrap methodology must be employed in order to avoid size distortions. We propose a block bootstrap scheme and show that it has much nicer properties than the traditional Chow–Denning [Chow, K.V., Denning, K.C., 1993. A simple multiple variance ratio test. Journal of Econometrics 58 (3), 385–401] multiple variance ratio tests. Overall, the method proposed in the paper provides evidence refuting the random walk behavior for the Brazilian exchange rate for long investment horizon, but consistent with the random walk hypothesis for short-run horizon. Additionally, we also test for the predictive power of variable moving average (VMA) and trading range break (TRB) technical rules and find evidence of forecasting ability for these rules. Nonetheless, the excess return that can be obtained from such rules is not significant, suggesting that such predictability is not economically significant.     

Discrete-Time Pricing and Optimal Exercise of American Perpetual Warrants in the Geometric Random Walk Model

An American option (or, warrant) is the right, but not the obligation, to purchase or sell an underlying equity at any time up to a predetermined expiration date for a predetermined amount. A perpetual American option differs from a plain American option in that it does not expire. In this study, we solve the optimal stopping problem of a perpetual American option (both call and put) in discrete time using linear programming duality. Under the assumption that the underlying stock price follows a discrete time and discrete state Markov process, namely a geometric random walk, we formulate the pricing problem as an infinite dimensional linear programming (LP) problem using the excessive-majorant property of the value function. This formulation allows us to solve complementary slackness conditions in closed-form, revealing an optimal stopping strategy which highlights the set of stock-prices where the option should be exercised. The analysis for the call option reveals that such a critical value exists only in some cases, depending on a combination of state-transition probabilities and the economic discount factor (i.e., the prevailing interest rate) whereas it ceases to be an issue for the put.     

Weak interaction limits for one-dimensional random polymers

 In this paper we present a new and flexible method to show that, in one dimension, various self-repellent random walks converge to self-repellent Brownian motion in the limit of weak interaction after appropriate space-time scaling. Our method is based on cutting the path into pieces of an appropriately scaled length, controlling the interaction between the different pieces, and applying an invariance principle to the single pieces. In this way, we show that the self-repellent random walk large deviation rate function for the empirical drift of the path converges to the self-repellent Brownian motion large deviation rate function after appropriate scaling with the interaction parameters. The method is considerably simpler than the approach followed in our earlier work, which was based on functional analytic arguments applied to variational representations and only worked in a very limited number of situations. We consider two examples of a weak interaction limit: (1) vanishing self-repellence, (2) diverging step variance. In example (1), we recover our earlier scaling results for simple random walk with vanishing self-repellence and show how these can be extended to random walk with steps that have zero mean and a finite exponential moment. Moreover, we show that these scaling results are stable against adding self-attraction, provided the self-repellence dominates. In example (2), we prove a conjecture by Aldous for the scaling of self-avoiding walk with diverging step variance. Moreover, we consider self-avoiding walk on a two-dimensional horizontal strip such that the steps in the vertical direction are uniform over the width of the strip and find the scaling as the width tends to infinity. Received: 6 March 2002 / Revised version: 11 October 2002 / Published online: 21 February 2003 Mathematics Subject Classification (2000): 60F05, 60F10, 60J55, 82D60 Key words or phrases: Self-repellent random walk and Brownian motion – Invariance principles – Large deviations – Scaling limits – Universality     

Corrected asymptotics for a multi-server queue in the Halfin-Whitt regime

To investigate the quality of heavy-traffic approximations for queues with many servers, we consider the steady-state number of waiting customers in an M/D/s queue as s→∞. In the Halfin-Whitt regime, it is well known that this random variable converges to the supremum of a Gaussian random walk. This paper develops methods that yield more accurate results in terms of series expansions and inequalities for the probability of an empty queue, and the mean and variance of the queue length distribution. This quantifies the relationship between the limiting system and the queue with a small or moderate number of servers. The main idea is to view the M/D/s queue through the prism of the Gaussian random walk: as for the standard Gaussian random walk, we provide scalable series expansions involving terms that include the Riemann zeta function.      

Optimal Scaling for Random Walk Metropolis on Spherically Constrained Target Densities

We consider the problem of optimal scaling of the proposal variance for multidimensional random walk Metropolis algorithms. It is well known, for a wide range of continuous target densities, that the optimal scaling of the proposal variance leads to an average acceptance rate of 0.234. Therefore a natural question is, do similar results hold for target densities which have discontinuities? In the current work, we answer in the affirmative for a class of spherically constrained target densities. Even though the acceptance probability is more complicated than for continuous target densities, the optimal scaling of the proposal variance again leads to an average acceptance rate of 0.234.