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.     

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.     

On the reverse process of a critical multitype Galton-Watson process without variances

Limit theorems are established for the reverse process of a critical multitype Galton-Watson process without variances. These results are an extension of those of Nakagawa |5| in the case with finite variances.     

The multitype branching random walk, II

Limit theorems for the multitype branching random walk as n → ∞ are given (n is the generation number) in the case in which the branching process has a mean matrix which is not positive regular. In particular, the existence of steady state distributions is proven in the subcritical case with immigration, and in the critical case with initial Poisson random fields of particles. In the supercritical case, analogues of the limit theorems of Kesten and Stigum are given.     

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)").     

On the first passage time of a simple random walk on a tree

We consider a simple random walk on a tree. Exact expressions are obtained for the expectation and the variance of the first passage time, thereby recovering the known result that these are integers. A relationship of the mean first passage matrix with the distance matrix is established and used to derive a formula for the inverse of the mean first passage matrix.     

Diffusion approximation of the two-type Galton-Watson process with mean matrix close to the identity

In this paper a diffusion approximation to the two-type Galton-Watson branching processes with mean matrix close to the identity is given in the form of Berstein stochastic differentials. An associated diffusion equation is found using an extension of the one-dimensional Bernstein technique. Expressions for the mean vector and covariance matrix of the diffusion approximation are derived.     

Scaling limit of local time of Sinai’s random walk

We prove that the local times of a sequence of Sinai’s random walks converge to those of Brox’s diffusion by proper scaling. Our proof is based on the intrinsic branching structure of the random walk and the convergence of the branching processes in random environment.     

On the insertion time of random walk cuckoo hashing

Cuckoo Hashing is a hashing scheme invented by pervious study of Pagh and Rodler. It uses d ≥ 2 distinct hash functions to insert n items into the hash table of size m = (1 + ε)n. In their original paper they treated d = 2 and m = (2 + ε)n. It has been an open question for some time as to the expected time for Random Walk Insertion to add items when d > 2. We show that if the number of hash functions d ≥ d_ε = O(1) then the expected insertion time is O(1) per item.     

Large deviations of the first passage time for a random walk with semiexponentially distributed jumps

Suppose that ξ, ξ(1), ξ(2), ... are independent identically distributed random variables such that ?ξ is semiexponential; i.e., $P( - \xi \geqslant t) = e^{ - t^\beta L(t)} $ is a slowly varying function as t → ∞ possessing some smoothness properties. Let E ξ = 0, D ξ = 1, and S(k) = ξ(1) + ? + ξ(k). Given d > 0, define the first upcrossing time η ₊(u) = inf{k ≥ 1: S(k) + kd > u} at nonnegative level u ≥ 0 of the walk S(k) + kd with positive drift d > 0. We prove that, under general conditions, the following relation is valid for $u = (n) \in \left[ {0, dn - N_n \sqrt n } \right]$ : 0.1 $P(\eta + (u) > n) \sim \frac{{E\eta + (u)}}{n}P(S(n) \leqslant x) as n \to \infty $ , where x = u ? nd < 0 and an arbitrary fixed sequence N _n not exceeding $d\sqrt n $ tends to ∞. The conditions under which we prove (0.1) coincide exactly with the conditions under which the asymptotic behavior of the probability P(S(n) ≤ x) for $x \leqslant - \sqrt n $ was found in [1] (for $x \in \left[ { - \sqrt n ,0} \right]$ it follows from the central limit theorem).     

Hitting time of a half-line by two-dimensional random walk

We consider the probability that a two-dimensional random walk starting from the origin never returns to the half-line {(x₁,x₂)|x₁0,x₂=0} before time n. It is proved that for aperiodic random walk with mean zero and finite 2+(>2)-th absolute moment, this probability times n^1/4 converges to some positive constant c^* as . We show that c^* is expressed by using the characteristic function of the increment of the random walk. For the simple random walk, this expression gives Mathematics Subject Classification (2000):60G50, 60E10     

On the speed of a cookie random walk

We consider the model of the one-dimensional cookie random walk when the initial cookie distribution is spatially uniform and the number of cookies per site is finite. We give a criterion to decide whether the limiting speed of the walk is non-zero. In particular, we show that a positive speed may be obtained for just three cookies per site. We also prove a result on the continuity of the speed with respect to the initial cookie distribution.      

On the sequence of Bayesian estimates of normal random walk process

Let (μ_t)^∞_t=0 be a k-variate (k?1) normal random walk process with successive increments being independently distributed as normal N(δ, R), and μ₀ being distributed as normal N(0, V₀). Let X_t have normal distribution N(μ_t, Σ) when μ_t is given, t = 1, 2,….Then the conditional distribution of μ_t given X₁, X₂,…, X_t is shown to be normal N(U_t, V_t) where U_t's and V_t's satisfy some recursive relations. It is found that there exists a positive definite matrix V and a constant θ, 0 < θ < 1, such that, for all t?1,

$\text{|R}\text{1}\text{2}\text{(V}{}^{\mathrm{?1}}{}_{\mathrm{t}}\text{?V}{}^{\mathrm{?1}}\text{R}\text{1}\text{2}\text{|<θ}{}^{\mathrm{t}}\text{|R}\text{1}\text{2}\text{(V}{}^{\mathrm{?1}}{}_0\text{?V}{}^{\mathrm{?1}}\text{)R}\text{1}\text{2}\text{|}$

where the norm |·| means that |A| is the largest eigenvalue of a positive definite matrix A. Thus, V_t approaches to V as t approaches to infinity. Under the quadratic loss, the Bayesian estimate of μ_t is U_t and the process {U_t}^∞_t=₀, U₀=0, is proved to have independent successive increments with normal N(θ, V_t?V_t+1+R) distribution. In particular, when V₀ =V then V_t = V for all t and {U_t}^∞_t=0 is the same as {μ_t}^∞_t=0 except that U₀ = 0 and μ₀ is random.     

Diffusivity of a random walk on random walks

We consider a random walk with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor with respect to the case of the classical simple random walk without constraint. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 267–283, 2015     

On the support of the simple branching random walk

Connectivity of the support of the simple branching random walk is established in certain asymmetric cases, extending a previous result of Grill.     

Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Critical window for the vacant set left by random walk on random regular graphs

We consider the simple random walk on a random d ‐regular graph with n vertices, and investigate percolative properties of the set of vertices not visited by the walk until time \begin{align*}\left\lfloor un \right\rfloor\end{align*}, where u > 0 is a fixed positive parameter. It was shown in ?erný et al., (Ann Inst Henri Poincaré Probab Stat 47 (2011) 929–968) that this so‐called vacant set exhibits a phase transition at u = u_?: there is a giant component if u < u_? and only small components when u > u_?. In this paper we show the existence of a critical window of size n^‐1/3 around u_?. In this window the size of the largest cluster is of order n^2/3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On the trajectory of an individual chosen according to supercritical Gibbs measure in the branching random walk

Consider a branching random walk on the real line. Madaule (2016) showed the renormalized trajectory of an individual selected according to the critical Gibbs measure converges in law to a Brownian meander. Besides, Chen (2015) proved that the renormalized trajectory leading to the leftmost individual at time $n$ converges in law to a standard Brownian excursion. In this article, we prove that the renormalized trajectory of an individual selected according to a supercritical Gibbs measure also converges in law toward the Brownian excursion. Moreover, refinements of this results enables to express the probability for the trajectories of two individuals selected according to the Gibbs measure to have split before time $t$, partially answering a question of Derrida and Spohn (1988).     

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