Phase transition of the minimum degree random multigraph process

We study the phase transition of the minimum degree multigraph process. We prove that for a constant h_g ≈︁ 0.8607, with probability tending to 1 as n → ∞, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than h_gn, the largest component has order roughly n^2/3 when the number of edges added is exactly h_gn, and the graph consists of one giant component on Θ(n) vertices and small components on O(log n) vertices when the number of edges added is larger than h_gn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A note on multitype branching process with bounded immigration in random environment

In this paper, we study the total number of progeny, W, before regenerating of multitype branching process with immigration in random environment. We show that the tail probability of |W| is of order t-κ as t→∞, with κ some constant. As an application, we prove a stable law for (L-1) random walk in random environment, generalizing the stable law for the nearest random walk in random environment (see "Kesten, Kozlov, Spitzer: A limit law for random walk in a random environment. Compositio Math., 30, 145-168 (1975)").     

Delaying satisfiability for random 2SAT

Let (C₁,C′_(*)),(C₂,C′_(*)),…,(C _m,C′_(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 \begin{align*}\binom{n}{2}\end{align*} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on‐line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on‐line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)^1/4. This contrasts with the well‐known fact that a random m ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on‐line setting above, we also consider an off‐line version in which all m clause‐pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off‐line setting, we show that the two‐choice satisfiability threshold for k ‐SAT for any fixed k coincides with the standard satisfiability threshold for random 2k ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Loop-Erased Random Walk on Finite Graphs and the Rayleigh Process

Let (G _n ) _n=1^∞ be a sequence of finite graphs, and let Y _t be the length of a loop-erased random walk on G _n after t steps. We show that for a large family of sequences of finite graphs, which includes the case in which G _n is the d-dimensional torus of size-length n for d≥4, the process (Y _t ) _t=0^∞, suitably normalized, converges to the Rayleigh process introduced by Evans, Pitman, and Winter. Our proof relies heavily on ideas of Peres and Revelle, who used loop-erased random walks to show that the uniform spanning tree on large finite graphs converges to the Brownian continuum random tree of Aldous. Supported in part by NSF Grant DMS-0504882.     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Gnedenko-Type Limit Theorems for Cyclostationary χ2-Processes

We prove Gnedenko type limit theorems on extremes for cyclostationary ²-processes.     

THE CONSTRUCTION OF DENUMERABLE q-PROCESSES IN RANDOM ENVIRONMENTS SATISFYING (F) OR (B)

This article is a continuation of [9]. Based on the discussion of random Kol-mogorov forward (backward) equations, for any given q-matrix in random environment,Q(θ) = (q(θ; x, y), x, y ∈ X), an infinite class of q-processes in random environments sat-isfying the random Kolmogorov forward (backward) equation is constructed. Moreover,under some conditions, all the q-processes in random environments satisfying the random Kolmogorov forward (backward) equation are constructed.     

A physical basis for Krein's prediction formula

A prediction problem of the following variety is considered. A stationary random process w(·) of known spectrum is observed over |t|?a. Using these observed values, w(b) is to be predicted for some b with |b|>a. We present a physical interpretation of a solution to this problem due to Krein, which used the theory of inverse Sturm-Liouville problems. Our physical model involves a nonuniform lossless transmission line excited at one end by white noise. The signal at the other end is the process w(t), and the prediction is found by calculating as intermediate quantities the voltage and current stored on the line at t=0. These quantities are spatially uncorrelated and provide a spatial representation at t=0 of the innovations of w(t) over |t|?a.     

Stationary distributions of semistochastic processes with disturbances at random times and with random severity

We consider a semistochastic continuous-time continuous-state space random process that undergoes downward disturbances with random severity occurring at random times. Between two consecutive disturbances, the evolution is deterministic, given by an autonomous ordinary differential equation. The times of occurrence of the disturbances are distributed according to a general renewal process. At each disturbance, the process gets multiplied by a continuous random variable (“severity”) supported on [0,1). The inter-disturbance time intervals and the severities are assumed to be independent random variables that also do not depend on the history.We derive an explicit expression for the conditional density connecting two consecutive post-disturbance levels, and an integral equation for the stationary distribution of the post-disturbance levels. We obtain an explicit expression for the stationary distribution of the random process. Several concrete examples are considered to illustrate the methods for solving the integral equations that occur.     

Recovering a Family of Two-Dimensional Gaussian Variables from the Minimum Process

Suppose that {(X _t, Y _t): t>}0 is a family of two independent Gaussian random variables with means m ₁(t) and m ₂(t) and variances σ ² ₁(t) and σ ² ₂(t). If at every time t>0 the first and second moment of the minimum process X _t∧Y _t are known, are the parameters governing these four moment functions uniquely determined ? We answer this question in the negative for a large class of Gaussian families including the “Brownian” case. Except for some degenerate situation where one variance function dominates the other, in which case the recovery of the parameters is fully successful, the second moment of the minimum process does not provide any additional clues on identifying the parameters.     

The Cℓ‐free process

The ‐free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of is created. For every we show that, with high probability as , the maximum degree is , which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the ‐free process typically terminates with edges, which answers a question of Erd?s, Suen and Winkler. This is the first result that determines the final number of edges of the more general H‐free process for a non‐trivial class of graphs H. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to ‘transfer’ certain decreasing properties from the binomial random graph to the H‐free process. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 490–526, 2014     

Extremum of a time-inhomogeneous branching random walk

Consider a time-inhomogeneous branching random walk, generated by the point process L_n which composed by two independent parts: ‘branching’offspring X_n with the mean \mathrm{1}+{B(\mathrm{1}+n)}^{-\beta } for \beta \in (\mathrm{0},\mathrm{1}) and ‘displacement’ {{\displaystyle \xi }}_n with a drift {A(\mathrm{1}+n)}^{-\mathrm{2}\alpha } for \alpha \in (\mathrm{0},\mathrm{1}/\mathrm{2}), where the ‘branching’ process is supercritical for B>0 but ‘asymptotically critical’ and the drift of the ‘displacement’ {{\displaystyle \xi }}_n is strictly positive or negative for \left|A\right|\rangle \mathrm{0} but ‘asymptotically’ goes to zero as time goes to infinity. We find that the limit behavior of the minimal (or maximal) position of the branching random walk is sensitive to the ‘asymptotical’ parameter \beta and \alpha.     

An ornstein-uhlenbeck model for random oscillations

We consider the effect of a random "noise" on an n-dimensional simple harmonic oscillator with time-dependent damping. The noise in the system is modelled by incorporating a Brownian motion term in the equation for the velocity process of the simple harmonic oscillator, giving a stochastic differential equation similar to that of an Ornstein-Uhlenbeck proces. Necessary and sufficient conditions for the convergence of the solution of this SDE to an orbit of simple harmonic motion (satisfying the usual ODE) are then obtained     

Random walks in a strongly sparse random environment

The integer points (sites) of the real line are marked by the positions of a standard random walk with positive integer jumps. We say that the set of marked sites is weakly, moderately or strongly sparse depending on whether the jumps of the random walk are supported by a bounded set, have finite or infinite mean, respectively. Focussing on the case of strong sparsity and assuming additionally that the distribution tail of the jumps is regularly varying at infinity we consider a nearest neighbor random walk on the set of integers having jumps $\pm 1$ with probability $1∕2$ at every nonmarked site, whereas a random drift is imposed at every marked site. We prove new distributional limit theorems for the so defined random walk in a strongly sparse random environment, thereby complementing results obtained recently in Buraczewski et al. (2019) for the case of moderate sparsity and in Matzavinos et al. (2016) for the case of weak sparsity. While the random walk in a strongly sparse random environment exhibits either the diffusive scaling inherent to a simple symmetric random walk or a wide range of subdiffusive scalings, the corresponding limit distributions are non-stable.     

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     

Upper triangular matrix walk: Cutoff for finitely many columns

We consider random walk on the space of all upper triangular matrices with entries in which forms an important example of a nilpotent group. Peres and Sly proved tight bounds on the mixing time of this walk up to constants. It is well known that the column projection of this chain is the one dimensional East process. In this article we complement the Peres‐Sly result by proving a cutoff result for the mixing of finitely many columns in the upper triangular matrix walk at the same location as the East process of the same dimension. The proof is based on a recursive argument which uses a local version of a dual process appearing in a previous study, various combinatorial consequences of mixing and concentration results for the movement of the front in the one dimensional East process.     

On weighted heights of random trees

Consider the family treeT of a branching process starting from a single progenitor and conditioned to havev=v(T) edges (total progeny). To each edge <e> we associate a weightW(e). The weights are i.i.d. random variables and independent ofT. The weighted height of a self-avoiding path inT starting at the root is the sum of the weights associated with the path. We are interested in the asymptotic distribution of the maximum weighted path height in the limit asv=n. Depending on the tail of the weight distribution, we obtain the limit in three cases. In particular ify ² P(W(e)> y)0, then the limit distribution depends strongly on the tree and, in fact, is the distribution of the maximum of a Brownian excursion. If the tail of the weight distribution is regularly varying with exponent 0<2, then the weight swamps the tree and the answer is the asymptotic distribution of the maximum edge weight in the tree. There is a borderline case, namely,P(W(e)> y)cy ^–2 asy, in which the limit distribution exists but involves both the tree and the weights in a more complicated way.     

Position dependent and stochastic thinning of point processes

A short probabilistic proof of Kallenberg's theorem [2] on thinning of point processes is given. It is extended to the case where the probability of deletion of a point depends on the position of the point and is itself random. The proof also leads easily to a statement about the rate of convergence in Renyi's theorem on thinning a renewal process.     

The range of once‐reinforced random walk in one dimension

We study once‐reinforced random walk on . For this model, we derive limit results on all moments of its range using Tauberian theory.