Search

The random—or orderly—seating of passengers on a bus is used to motivate several questions about cycles of permutations. These in turn motivates the investigation of bijections between special subs...

We find a two term asymptotic expansion for the optimal expected value of a sequentially selected monotone subsequence from a random permutation of length n n . A striking feature of this expansion is that it tells us that the expected value of optimal selection from a random permutation is quantifiably larger than optimal sequential selection from an independent sequence of uniformly distributed random variables; specifically, it is larger by at least ( 1 / 6 ) log ⁡ n + O ( 1 ) (1/6) \log n +O(1) .

We analyze the optimal policy for the sequential selection of an alternating subsequence from a sequence of $n$ independent observations from a continuous distribution $F$, and we prove a central limit theorem for the number of selections made by that policy. The proof exploits the backward recursion of dynamic programming and assembles a detailed understanding of the associated value functions and selection rules., 24 pages, 1 figure

We illustrate a process that constructs martingales with help from matrix products that arise naturally in the theory of sampling without replacement. The usefulness of the new martingales is illustrated by the development of maximal inequalities for permuted sequences of real numbers. Some of these inequalities are new and some are variations of classical inequalities like those introduced by A. Garsia in the study of rearrangement of orthogonal series.

It is common in inventory theory to consider policies that minimize the expected cost of ordering and holding goods or materials. Nevertheless, the realized cost is a random variable, and, as the Saint Petersburg Paradox reminds us, the expected value does not always capture the full economic reality of a decision problem. Here we take the classic inventory model of Bulinskaya (1964), and, by proving an appropriate central limit theorem, we show in a reasonably rich (and practical) sense that the mean-optimal policies are economically appropriate. The motivation and the tools are applicable to a large class of Markov decision problems., 15 pages

The Bruss-Robertson inequality gives a bound on themaximal number of elements of a random sample whose sum is less than a specifiedvalue, and the extension of that inequality which is given hereneither requires the independence of the summands nor requires the equality of their marginal distributions. A review is also given of the applications of the Bruss-Robertson inequality,especially the applications to problems of combinatorial optimization such as the sequential knapsack problem and the sequential monotone subsequence selection problem.

We construct a stationary ergodic process $X_1, X_2, \ldots $ such that each $X_t$ has the uniform distribution on the unit square and the length $L_n$ of the shortest path through the points $X_1, X_2, \ldots,X_n$ is not asymptotic to a constant times the square root of $n$. In other words, we show that the Beardwood, Halton and Hammersley theorem does not extend from the case of independent uniformly distributed random variables to the case of stationary ergodic sequences with uniform marginal distributions., 24 pages, 1 figure

We consider sequential selection of an alternating subsequence from a sequence of independent, identically distributed, continuous random variables, and we determine the exact asymptotic behavior of an optimal sequentially selected subsequence. Moreover, we find (in a sense we make precise) that a person who is constrained to make sequential selections does only about 12 percent worse than a person who can make selections with full knowledge of the random sequence.

We consider a simple model of sequential decisions made by a fusion agent that receives binary-passive reports from distributed sensors. The main result is an explicit formula for the probability of making a decision before a fixed budget is exhausted. These results depend on the relationship between a special ruin problem for a “lazy random walk” and a traditional biased walk.

In the theory of interest rate futures, the difference between the futures rate and forward rate is called the “convexity bias,” and there are several widely offered reasons why the convexity bias should be positive. Nevertheless, it is not infrequent that the empirical the bias is observed to be negative. Moreover, in its most general form, the benchmark Heath–Jarrow–Morton (HJM) term structure model is agnostic on the question of the sign of the bias; it allows for models where the convexity bias can be positive or negative. In partial support of the practitioner’s arguments, we develop a simple scalar condition within the HJM framework that suffices to guarantee that the convexity bias is positive. Moreover, when we check this condition on the LIBOR futures data, we find strong empirical support for the new condition. The empirical validity of the sufficient condition and the periodic observation of negative bias, therefore leads one to a paradoxical situation where either (1) there are arbitrage possibilities or (2) a large subclass of HJM models provide interest rate dynamics that fail to capture a fundamental feature of LIBOR futures.

This article is reproduced from the previous edition, volume 18, pp. 12099–12104, © 2001, Elsevier Ltd.

We prove a central limit theorem for a class of additive processes that arise naturally in the theory of finite horizon Markov decision problems. The main theorem generalizes a classic result of Dobrushin (1956) for temporally non-homogeneous Markov chains, and the principal innovation is that here the summands are permitted to depend on both the current state and a bounded number of future states of the chain. We show through several examples that this added flexibility gives one a direct path to asymptotic normality of the optimal total reward of finite horizon Markov decision problems. The same examples also explain why such results are not easily obtained by alternative Markovian techniques such as enlargement of the state space., Comment: 27 pages, 1 figure

Condensation phenomenon is often observed in social networks such as Twitter where one "superstar" vertex gains a positive fraction of the edges, while the remaining empirical degree distribution still exhibits a power law tail. We formulate a mathematically tractable model for this phenomenon that provides a better fit to empirical data than the standard preferential attachment model across an array of networks observed in Twitter. Using embeddings in an equivalent continuous time version of the process, and adapting techniques from the stable age-distribution theory of branching processes, we prove limit results for the proportion of edges that condense around the superstar, the degree distribution of the remaining vertices, maximal nonsuperstar degree asymptotics and height of these random trees in the large network limit., Comment: Published at http://dx.doi.org/10.1214/14-AAP1053 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We construct a continuous distribution G such that the number of faces in the smallest concave majorant of the random walk with G -distributed summands will take on each natural number infinitely often with probability one. This investigation is motivated by the fact that the number of faces F n of the concave majorant of the random walk at time n has the same distribution as the number of records R n in the sequence of summands up to time n . Since R n is almost surely asymptotic to log n , the construction shows that despite the equality of all of the one-dimensional marginals, the almost sure behaviors of the sequences { R n } and { F n } may be radically different.

Scan statistics are commonly used in biology, medicine, engineering and other fields where interest is in the probability of observing clusters of events in a window at an unknown location. Due to the dependent nature of the number of events in a large number of overlapping window locations, even approximate solutions for the simplest scan statistics may require elaborate calculations. We propose a new martingale method which allows one to approximate the distribution for a wide variety of scan statistics, including some for which analytical results are computationally infeasible.

Consider a sequence of $n$ independent random variables with a common continuous distribution $F$, and consider the task of choosing an increasing subsequence where the observations are revealed sequentially and where an observation must be accepted or rejected when it is first revealed. There is a unique selection policy $\pi_n^*$ that is optimal in the sense that it maximizes the expected value of $L_n(\pi_n^*)$, the number of selected observations. We investigate the distribution of $L_n(\pi_n^*)$; in particular, we obtain a central limit theorem for $L_n(\pi_n^*)$ and a detailed understanding of its mean and variance for large $n$. Our results and methods are complementary to the work of Bruss and Delbaen (2004) where an analogous central limit theorem is found for monotone increasing selections from a finite sequence with cardinality $N$ where $N$ is a Poisson random variable that is independent of the sequence., Comment: 26 pages

Given a sequence of independent random variables with a common continuous distribution, we consider the online decision problem where one seeks to minimize the expected value of the time that is needed to complete the selection of a monotone increasing subsequence of a prespecified length $n$. This problem is dual to some online decision problems that have been considered earlier, and this dual problem has some notable advantages. In particular, the recursions and equations of optimality lead with relative ease to asymptotic formulas for mean and variance of the minimal selection time., Comment: 17 pages

The sum of squares of the edge lengths of the tour provided by the spacefilling curve heuristic applied to a random sample of $n$ points from the unit square is proved to be asymptotically equal to a periodic function of the logarithm of the sample size.