Rank-based selection strategies for the random walk process

In many decision situations such as hiring a secretary, selling an asset, or seeking a job, the value of each offer, applicant, or choice is assumed to be an independent, identically distributed random variable. In this paper, we consider a special case where the observations are auto-correlated as in the random walk model for stock prices. For a given random walk process of n observations, we explicitly compute the probability that the j-th observation in the sequence is the maximum or minimum among all n observations. Based on the probability distribution of the rank, we derive several distribution-free selection strategies under which the decision maker's expected utility of selecting the best choice is maximized. We show that, unlike in the classical secretary problem, evaluating more choices in the random walk process does not increase the likelihood of successfully selecting the best.     

Conditioning and stability of finite difference schemes on uniform meshes for a singularly perturbed parabolic convection-diffusion equation

For a singularly perturbed parabolic convection-diffusion equation, the conditioning and stability of finite difference schemes on uniform meshes are analyzed. It is shown that a convergent standard monotone finite difference scheme on a uniform mesh is not ?-uniformly well conditioned or ?-uniformly stable to perturbations of the data of the grid problem (here, ? is a perturbation parameter, ? ∈ (0, 1]). An alternative finite difference scheme is proposed, namely, a scheme in which the discrete solution is decomposed into regular and singular components that solve grid subproblems considered on uniform meshes. It is shown that this solution decomposition scheme converges ?-uniformly in the maximum norm at an O(N ^?1lnN + N ₀ ^?1 ) rate, where N + 1 and N ₀ + 1 are the numbers of grid nodes in x and t, respectively. This scheme is ?-uniformly well conditioned and ?-uniformly stable to perturbations of the data of the grid problem. The condition number of the solution decomposition scheme is of order O(δ^?2lnδ^?1 + δ ₀ ^?1 ); i.e., up to a logarithmic factor, it is the same as that of a classical scheme on uniform meshes in the case of a regular problem. Here, δ = N ^?1lnN and δ₀ = N ₀ ^?1 are the accuracies of the discrete solution in x and t, respectively.     

Optimal selection of thek best of a sequence withk stops

We first consider the situation in which the decision-maker is allowed to have five choices with purpose to choose exactly the five absolute best candidates fromN applicants. The optimal stopping rule and the maximum probability of making the right five-choice are given for largeN εN, the maximum asymptotic value of the probability of the best choice being lim _N→∝ P (win) ≈ 0.104305. Then, we study the general problem of selecting thek best of a sequence withk stops, constructing first a rough solution for this problem. Using this suboptimal solution, we find an approximation for the optimal probability valuesP _k of the form $$P_k \approx \frac{1}{{(e - 1)k + 1}}$$ for any k εN.     

Uniform grid approximation of nonsmooth solutions with improved convergence for a singularly perturbed convection-diffusion equation with characteristic layers

A mixed boundary value problem for a singularly perturbed elliptic convection-diffusion equation with constant coefficients in a square domain is considered. Dirichlet conditions are specified on two sides orthogonal to the flow, and Neumann conditions are set on the other two sides. The right-hand side and the boundary functions are assumed to be sufficiently smooth, which ensures the required smoothness of the desired solution in the domain, except for neighborhoods of the corner points. Only zero-order compatibility conditions are assumed to hold at the corner points. The problem is solved numerically by applying an inhomogeneous monotone difference scheme on a rectangular piecewise uniform Shishkin mesh. The inhomogeneity of the scheme lies in that the approximating difference equations are not identical at different grid nodes but depend on the perturbation parameter. Under the assumptions made, the numerical solution is proved to converge ?-uniformly to the exact solution in a discrete uniform metric at an O(N ^?3/2ln² N) rate, where N is the number of grid nodes in each coordinate direction.     

How Many Comparisons Does Quicksort Use?

We examine the probability distribution of the number of comparisons needed by the Quicksort sorting algorithm, where probability arises due to the items being in random order. We develop a general class of distributions for the permutation of the items to be sorted which includes the uniform distribution on permutations as a special case. For this general class, the distribution of the number of comparisons is given by the solution of a simple recurrence relation. We provide an exact solution of the recurrence for very small n. We show that the solution can be approximated asymptotically by the solution of a "quadratic" operator equation. We exhibit three numerical solutions to the operator equation for two different distributions on permutations from the general class. We also exhibit numerical solutions for the case in which the algorithm is modified so that arrays are partitioned by the median-of-three selected items rather than by a single selected item.     

Strong stability of a scheme on locally uniform meshes for a singularly perturbed ordinary differential convection-diffusion equation

The Dirichlet problem for a singularly perturbed ordinary differential convection-diffusion equation with a small parameter ? (? ?? (0, 1]) multiplying the higher order derivative is considered. For the problem, a difference scheme on locally uniform meshes is constructed that converges in the maximum norm conditionally, i.e., depending on the relation between the parameter ? and the value N defining the number of nodes in the mesh used; in particular, the scheme converges almost ?-uniformly (i.e., its accuracy depends weakly on ?). The stability of the scheme with respect to perturbations in the data and its conditioning are analyzed. The scheme is constructed using classical monotone approximations of the boundary value problem on a priori adapted grids, which are uniform on subdomains where the solution is improved. The boundaries of these subdomains are determined by a majorant of the singular component of the discrete solution. On locally uniform meshes, the difference scheme converges at a rate of O(min[?^?1 N ^?K lnN, 1] + N ^?1lnN), where K is a prescribed number of iterations for refining the discrete solution. The scheme converges almost ?-uniformly at a rate of O(N ^?1lnN) if N ^?1 ?? ?^??, where ?? (the defect of ?-uniform convergence) determines the required number K of iterations (K = K(??) ?? ??^?1) and can be chosen arbitrarily small from the half-open interval (0, 1]. The condition number of the difference scheme satisfies the bound ?? _P = O(?^?1/K ln^1/K ?^?1??^{?(K + 1)/K} ), where ?? is the accuracy of the solution of the scheme in the maximum norm in the absence of perturbations. For sufficiently large K, the scheme is almost ?-uniformly strongly stable.     

A general method for finding the optimal threshold in discrete time

We develop an approach for solving one-sided optimal stopping problems in discrete time for general underlying Markov processes on the real line. The main idea is to transform the problem into an auxiliary problem for the ladder height variables. In case that the original problem has a one-sided solution and the auxiliary problem has a monotone structure, the corresponding myopic stopping time is optimal for the original problem as well. This elementary line of argument directly leads to a characterization of the optimal boundary in the original problem. The optimal threshold is given by the threshold of the myopic stopping time in the auxiliary problem. Supplying also a sufficient condition for our approach to work, we obtain solutions for many prominent examples in the literature, among others the problems of Novikov-Shiryaev, Shepp-Shiryaev, and the American put in option pricing under general conditions. As a further application we show that for underlying random walks (and Lévy processes in continuous time), general monotone and log-concave reward functions g lead to one-sided stopping problems.     

Sparse solutions to random standard quadratic optimization problems

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.     

Optimal stopping in a search for a vertex with full degree in a random graph

We consider the following on-line decision problem. The vertices of a realization of the random graph G(n,p) are being observed one by one by a selector. At time m, the selector examines the mth vertex and knows the graph induced by the m vertices that have already been examined. The selector’s aim is to choose the currently examined vertex maximizing the probability that this vertex has full degree, i.e. it is connected to all other vertices in the graph. An optimal algorithm for such a choice (in other words, optimal stopping time) is given. We show that it is of a threshold type and we find the threshold and its asymptotic estimation.     

Additive comparisons of stopping values and supremum values for finite stage multiparameter stochastic processes

This paper concerns the optimal stopping problem for discrete time multiparameter stochastic processes with the index set Nd. In the classical optimal stopping problems, the comparisons between the expected reward of a player with complete foresight and the expected reward of a player using nonanticipating stop rules, known as prophet inequalities, have been studied by many authors. Ratio comparisons between these values in the case of multiparameter optimal stopping problems are studied by Krengel and Sucheston (1981) [9] and Tanaka (2007, 2006) [14] and [15]. In this paper an additive comparison in the case of finite stage multiparameter optimal stopping problems is given.     

The equivalence between uniqueness and continuous dependence of solutions for FBSDEs with continuous monotone coefficients

In this paper we study one kind of coupled forward-backward stochastic differential equation. With some particular choice for the coefficients, if one of them satisfies a uniform growth condition and they are accordingly monotone, then we obtain the equivalence between the uniqueness of solution and its continuous dependence on x and ξ, where x is the initial value of the forward component and ξ is the terminal value of the backward component.     

A leavable bounded-velocity stochastic control problem

This paper studies bounded-velocity control of a Brownian motion when discretionary stopping, or ‘leaving’, is allowed. The goal is to choose a control law and a stopping time in order to minimize the expected sum of a running and a termination cost, when both costs increase as a function of distance from the origin. There are two versions of this problem: the fully observed case, in which the control multiplies a known gain, and the partially observed case, in which the gain is random and unknown. Without the extra feature of stopping, the fully observed problem originates with Beneš (Stochastic Process. Appl. 2 (1974) 127–140), who showed that the optimal control takes the ‘bang–bang’ form of pushing with maximum velocity toward the origin. We show here that this same control is optimal in the case of discretionary stopping; in the case of power-law costs, we solve the variational equation for the value function and explicitly determine the optimal stopping policy.We also discuss qualitative features of the solution for more general cost structures. When no discretionary stopping is allowed, the partially observed case has been solved by Beneš et al. (Stochastics Monographs, Vol. 5, Gordon & Breach, New York and London, pp. 121–156) and Karatzas and Ocone (Stochastic Anal. Appl. 11 (1993) 569–605). When stopping is allowed, we obtain lower bounds on the optimal stopping region using stopping regions of related, fully observed problems.     

Strong convergence in nonparametric regression with truncated dependent data

In this paper we derive rates of uniform strong convergence for the kernel estimator of the regression function in a left-truncation model. It is assumed that the lifetime observations with multivariate covariates form a stationary α-mixing sequence. The estimation of the covariate’s density is considered as well. Under the assumption that the lifetime observations are bounded, we show that, by an appropriate choice of the bandwidth, both estimators of the covariate’s density and regression function attain the optimal strong convergence rate known from independent complete samples.     

Instrument effects and stochastic dominance

This paper investigates how individual choice is affected by increases in risk when the choice variable (instrument) affects the distribution of the random variable as well as the objective function. The effect of increased risk on optimal choice is shown to depend on attitudes towards risk and the interaction between exogenous uncertainty and the instrument. The latter is described in terms of an extension of the notion of stochastic dominance to a comparison of changes in probability distributions (signed measures) rather than the direct comparison of distributions (probability measures). Sufficiency conditions for signing comparative statistics exercises are presented and applied to an insurance example involving moral hazard.     

Local laws for non-Hermitian random matrices

The product of m ∈ N independent random square matrices whose elements are independent identically distributed random variables with zero mean and unit variance is considered. It is known that, as the size of the matrices increases to infinity, the empirical spectral measure of the normalized eigenvalues of the product converges with probability 1 to the distribution of the mth power of the random variable uniformly distributed on the unit disk of the complex plane. In particular, in the case of m = 1, the circular law holds. The purpose of this paper is to prove the validity of the local circular law (as well as its generalization to the case of any fixed m) in the case where the distribution of the matrix elements has finite absolute moment of order 4 + δ,δ > 0,. Recent results of Bourgade, Yau, and Yin, of Tao and Vu, and of Nemish are generalized.     

Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality

In this paper we studynon-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model toNICD on trees. In this model there is a fixed undirected tree with players at some of the nodes. One node is given a uniformly random string and this string is distributed throughout the network, with the edges of the tree acting as independent binary symmetric channels. The goal of the players is to agree on a shared random bit without communicating. Our new contributions include the following:

? In the case of ak-leaf star graph (the model considered in [31]), we resolve the open question of whether the success probability must go to zero ask » ∞. We show that this is indeed the case and provide matching upper and lower bounds on the asymptotically optimal rate (a slowly-decaying polynomial).

? In the case of thek-vertex path graph, we show that it is always optimal for all players to use the same 1-bit function.

? In the general case we show that all players should use monotone functions. We also show, somewhat surprisingly, that for certain trees it is better if not all players use the same function.

Our techniques include the use of thereverse Bonami-Beckner inequality. Although the usual Bonami-Beckner has been frequently used before, its reverse counterpart seems not to be well known. To demonstrate its strength, we use it to prove a new isoperimetric inequality for the discrete cube and a new result on the mixing of short random walks on the cube. Another tool that we need is a tight bound on the probability that a Markov chain stays inside certain sets; we prove a new theorem generalizing and strengthening previous such bounds [2, 3, 6]. On the probabilistic side, we use the “reflection principle” and the FKG and related inequalities in order to study the problem on general trees.     

Competitive subset selection with two agents

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion in its winning set. We study two natural rules to decide the winner of each round.For both rules we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria.Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).     

Generalized inverses and their application to applied probability problems

The main aim of this paper is to examine the applicability of generalized inverses to a wide variety of problems in applied probability where a Markov chain is present either directly or indirectly through some form of imbedding. By characterizing all generalized inverses of I—P, where P is the transition matrix of a finite irreducible discrete time Markov chain, we are able to obtain general procedures for finding stationary distributions, moments of the first passage time distributions, and asymptotic forms for the moments of the occupation-time random variables. It is shown that all known explicit methods for examining these problems can be expressed in this generalized inverse framework. More generally, in the context of a Markov renewal process setting the aforementioned problems are also examined using generalized inverses of I—P. As a special case, Markov chains in continuous time are considered, and we show that the generalized inverse technique can be applied directly to the infinitesimal generator of the process, instead of to I—P, where P is the transition matrix of the discrete time jump Markov chain.     

Decompounding random sums: a nonparametric approach

A compound distribution is the distribution of a random sum, which consists of a random number N of independent identically distributed summands, independent of N. Buchmann and Grübel (Ann Stat 31:1054–1074, 2003) considered decompounding a compound Poisson distribution, i.e. given observations on a random sum when N has a Poisson distribution, they constructed a nonparametric plug-in estimator of the underlying summand distribution. This approach is extended here to that of general (but known) distributions for N. Asymptotic normality of the proposed estimator is established, and bootstrap methods are used to provide confidence bounds. Finally, practical implementation is discussed, and tested on simulated data. In particular we show how recursion formulae can be inverted for the Panjer class in general, as well as for an example drawn from the Willmot class.     

Regularization methods for optimization problems with probabilistic constraints

We analyze nonlinear stochastic optimization problems with probabilistic constraints on nonlinear inequalities with random right hand sides. We develop two numerical methods with regularization for their numerical solution. The methods are based on first order optimality conditions and successive inner approximations of the feasible set by progressive generation of p-efficient points. The algorithms yield an optimal solution for problems involving α-concave probability distributions. For arbitrary distributions, the algorithms solve the convex hull problem and provide upper and lower bounds for the optimal value and nearly optimal solutions. The methods are compared numerically to two cutting plane methods.