Invariance principle for nonhomogeneous random walks on the grid ℤ1

A nonhomogeneous random walk on the grid ℤ¹ with transition probabilities that differ from those of a certain homogeneous random walk only at a finite number of points is considered. Trajectories of such a walk are proved to converge to trajectories of a certain generalized diffusion process on the line. This result is a generalization of the well-known invariance principle for the sums of independent random variables and Brownian motion. Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 459–472, September, 1999.     

Random permutations of countable sets

Summary The main objective of this paper is a study of random decompositions of random point configurations onR ^d into finite clusters. This is achieved by constructing for each configurationZ a random permutation ofZ with finite cycles; these cycles then form the cluster decomposition ofZ. It is argued that a good candidate for a random permutation ofZ is a Gibbs measure for a certain specification, and conditions are given for the existence and uniqueness of such a Gibbs measure. These conditions are then verified for certain random configurationsZ.     

Stochastic Differential Games with Multiple Modes and a Small Parameter

Abstract

Two persons stochastic differential games with multiple modes where the system is driven by a wideband noise is considered. The state of the system at time t is given by a pair (x ^ε(t), θ^ε(t)), where θ^ε(t) takes values in S = {1, 2,…, N} and ε is a small parameter. The discrete component θ^ε(t) describes various modes of the system. The continuous component x ^ε(t) is governed by a “controlled process” with drift vector which depends on the discrete component θ^ε (t). Thus, the state of the system, x ^ε(t), switches from one random path to another at random times as the mode θ^ε(t) changes. The discrete component θ^ε (t) is a “controlled Markov chain” with transition rate matrix depending on the continuous component. Both zero-sum and nonzero-sum games will be considered. In a zero-sum game, player I is trying to maximize certain expected payoff over his/her admissible strategies, where as player II is trying to minimize the same over his/her admissible strategies. This kind of game typically occurs in a pursuit-evation problem where an interceptor tries to destroy a specific target. Due to swift manuaring of the evador and the corresponding reaction by the interceptor, the trajectory keep switching rapidly at random times. We will show that the process (x ^ε(t), θ^ε(t)) converges to a process whose evolution is given by a “controlled diffusion process” with switching random paths. We will also establish the existence of randomized δ -optimal strategies for both players.     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

Generating a Random Signed Permutation with Random Reversals

Signed permutations form a group known as the hyperoctahedral group. We bound the rate of convergence to uniformity for a certain random walk on the hyperoctahedral group that is generated by random reversals. Specifically, we determine that O(n log n) steps are both necessary and sufficient for total variation distance and ℓ² distance to become small. This random walk arose as the result of an effort in molecular biology to model certain types of genome rearrangements.     

TheT, T −1-process, finitary codings and weak Bernoulli

We give an elementary proof that the second coordinate (the scenery process) of theT, T ⁻¹-process associated to any mean zero i.i.d. random walk onZ ^d is not a finitary factor of an i.i.d. process. In particular, this yields an elementary proof that the basicT, T ⁻¹-process is not finitarily isomorphic to a Bernoulli shift (the stronger fact that it is not Bernoulli was proved by Kalikow). This also provides (using past work of den Hollander and the author) an elementary example, namely theT, T ⁻¹-process in 5 dimensions, of a process which is weak Bernoulli but not a finitary factor of an i.i.d. process. An example of such a process was given earlier by del Junco and Rahe. The above holds true for arbitrary stationary recurrent random walks as well. On the other hand, if the random walk is Bernoulli and transient, theT, T ⁻¹-process associated to it is also Bernoulli. Finally, we show that finitary factors of i.i.d. processes with finite expected coding volume satisfy certain notions of weak Bernoulli in higher dimensions which have been previously introduced and studied in the literature. In particular, this yields (using past work of van den Berg and the author) the fact that the Ising model is weak Bernoulli throughout the subcritical regime.     

On stochastic integration by series of Wiener integrals

Stochastic integrals of random functions with respect to a white-noise random measure are defined in terms of random series of usual Wiener integrals. Conditions for the existence of such integrals are obtained in terms of the nuclearity of certain operators onL ² -spaces. The relation with the Fisk-Stratonovich symmetric integral is also discussed.This research was supported by AFOSR Contract No. F49620 82 C 0009.     

Some central limit theorems for ℓ∞-valued semimartingales and their applications

Summary. This paper is devoted to the generalization of central limit theorems for empirical processes to several types of ℓ^∞(Ψ)-valued continuous-time stochastic processes t⇝X _t ⁿ =(X _t ^{n ,ψ}|ψ∈Ψ), where Ψ is a non-empty set. We deal with three kinds of situations as follows. Each coordinate process t⇝X _t ^{n ,ψ} is: (i) a general semimartingale; (ii) a stochastic integral of a predictable function with respect to an integer-valued random measure; (iii) a continuous local martingale. Some applications to statistical inference problems are also presented. We prove the functional asymptotic normality of generalized Nelson-Aalen's estimator in the multiplicative intensity model for marked point processes. Its asymptotic efficiency in the sense of convolution theorem is also shown. The asymptotic behavior of log-likelihood ratio random fields of certain continuous semimartingales is derived. Received: 6 May 1996 / In revised form: 4 February 1997     

On the structure of stationary flat processes. III

Summary For arbitrary k and d with 1 k < d, sufficient conditions in terms of the second order moment measure are found for a stationary random measure in the space of k-flats in R ^d to be a.s. invariant. Some of these conditions are further shown to be almost sharp, in the sense of being nearly fulfilled for a certain class of stationary random measures which fail to be invariant. The latter results are based on estimates of the distributions under the homogeneous probability measure of certain rotational invariants for pairs of linear subspaces.     

Intersections of random hypersurfaces and visibility

Summary For a wide class of stationary random hypersurfaces in ^d the notion of the projection body is introduced. It turns out that this convex body, a very special case of which is Matheron's Steiner compact associated with a Poisson process of hyperplanes, contains most of the information concerning certain intersection properties of the random hypersurface, while its polar reciprocal set is closely connected with the behaviour of the random hypersurface in visibility problems. This enables one to give a unified treatment of several intersection and visibility problems for random hypersurfaces. A detailed investigation of the case where the random hypersurface is generated by a Poisson process is given separately.     

On a random graph with immigrating vertices: Emergence of the giant component

A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1/n, is studied. The detailed picture of emergence of giant components with O(n^2/3) vertices is shown to be the same as in the Erdős–Rényi graph process with the number of vertices fixed at n at the start. A major difference is that now the transition occurs about a time t=π/2, rather than t=1. The proof has three ingredients. The size of the largest component in the subcritical phase is bounded by comparison with a certain multitype branching process. With this bound at hand, the growth of the sum‐of‐squares and sum‐of‐cubes of component sizes is shown, via martingale methods, to follow closely a solution of the Smoluchowsky‐type equations. The approximation allows us to apply results of Aldous [Brownian excursions, critical random graphs and the multiplicative coalescent, Ann Probab 25 (1997), 812–854] on emergence of giant components in the multiplicative coalescent, i.e., a nonuniform random graph process. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 79–102, 2000     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

Continuity properties of decomposable probability measures on euclidean spaces

It is shown that every full e^A decomposable probability measure on R^k, where A is a linear operator all of whose eigenvalues have negative real part, is either absolutely continuous with respect to Lebesgue measure or continuous singular with respect to Lebesgue measure. This result is used to characterize the continuity properties of random variables that are limits of solutions of certain stochastic difference equations.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

Weak convergence to fractional Brownian motion in Brownian scenery

 Kesten and Spitzer have shown that certain random walks in random sceneries converge to stable processes in random sceneries. In this paper, we consider certain random walks in sceneries defined using stationary Gaussian sequence, and show their convergence towards a certain self-similar process that we call fractional Brownian motion in Brownian scenery. Received: 17 April 2002 / Revised version: 11 October 2002 / Published online: 15 April 2003 Research supported by NSFC (10131040). Mathematics Subject Classification (2002): 60J55, 60J15, 60J65 Key words or phrases: Weak convergence – Random walk in random scenery – Local time – Fractional Brownian motion in Brownian scenery     

Suprema of Chaos Processes and the Restricted Isometry Property

We present a new bound for suprema of a special type of chaos process indexed by a set of matrices, which is based on a chaining method. As applications we show significantly improved estimates for the restricted isometry constants of partial random circulant matrices and time‐frequency structured random matrices. In both cases the required condition on the number m of rows in terms of the sparsity s and the vector length n is m ? s log² s log² n. © 2014 Wiley Periodicals, Inc.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

Note on the heights of random recursive trees and random m-ary search trees

A process of growing a random recursive tree T_n is studied. The sequence {T_n} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T_n is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)^?1, where γe^1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.     

The scaling window for a random graph with a given degree sequence

We consider a random graph on a given degree sequence D, satisfying certain conditions. Molloy and Reed defined a parameter Q = Q(D) and proved that Q = 0 is the threshold for the random graph to have a giant component. We introduce a new parameter R = R( \begin{align*}\mathcal {D}\end{align*}) and prove that if |Q| = O(n^‐1/3R^2/3) then, with high probability, the size of the largest component of the random graph will be of order Θ(n^2/3R^‐1/3). If |Q| is asymptotically larger than n^‐1/3R^2/3 then the size of the largest component is asymptotically smaller or larger than n^2/3R^‐1/3. Thus, we establish that the scaling window is |Q| = O(n^‐1/3R^2/3). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012