Specifying absorption probabilities for the simple random walk

In the theory of the simple random walk an important problem is the determination of absorption probabilities. This paper considers the inverse problem in which for specified absorption probabilities, feasible regions are determined for the set of possible initial probability vectors which could generate such probabilities.     

Large deviations for hitting times of a random walk in random environment on a strip

We consider a random walk in random environment on a strip, which is transient to the right. The random environment is stationary and ergodic. By the constructed enlarged random environment which was first introduced by Goldsheid （2008）, we obtain the large deviations conditioned on the environment （in the quenched case） for the hitting times of the random walk.     

Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G, let T_G(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which T_G(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2_n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time T_G(x, y) to reach y from x in this graph is approximately 4_n³/27.     

The disconnection exponent for simple random walk

LetS(t) denote a simple random walk inZ ² with integer timet. The disconnection exponent is defined by saying the probability that the path ofS starting at 0 and ending at the circle of radiusn disconnects 0 from infinity decays like . We prove that the disconnection exponent is well-defined and equals the disconnection exponent for Brownian motion which is known to exist. Research supported by the National Science Foundation.     

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.     

Favourite sites of simple random walk

Periodica Mathematica Hungarica - We survey the current status of the list of questions related to the favourite (or: most visited) sites of simple random walk on Z, raised by Pál Erd?s...     

Linear and sub-linear growth and the CLT for hitting times of a random walk in random environment on a strip

The main goal of this work is to study the asymptotic behaviour of hitting times of a random walk (RW) in a quenched random environment (RE) on a strip. We introduce enlarged random environments in which the traditional hitting time can be presented as a sum of independent random variables whose distribution functions form a stationary random sequence. This allows us to obtain conditions (stated in terms of properties of random environments) for a linear growth of hitting times of relevant random walks. In some important cases (e.g. independent random environments) these conditions are also necessary for this type of behaviour. We also prove the quenched Central Limit Theorem (CLT) for hitting times in the general ergodic setting. A particular feature of these (ballistic) laws in random environment is that, whenever they hold under standard normalization, the convergence is a convergence with a speed. The latter is due to certain properties of moments of hitting times which are also studied in this paper. The asymptotic properties of the position of the walk are stated but are not proved in this work since this has been done in Goldhseid (Probab. Theory Relat. Fields 139(1):41–64, 2007).      

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

Recurrence time and range for a generalized random walk

The notions of recurrence time, range, and the limit of probabilities P_k of return to the origin arise in the study of random walks on groups. We examine these notions and develop relationships among them in an ergodic theory setting in which the usual requirement of independence of the increments of the random walk can be relaxed to simply an ergodic requirement. Thus we consider generalized random walks or GRWs. The ergodic theory setting is related to Mackey's virtual group theory in that the GRW determines a virtual group homomorphism (or cocycle). We relate the condition- that the homomorphism is trivial (the cocycle is a coboundary) to the Cesáro limit of P_k. The basic ideas of virtual group theory were established by Mackey and further developed by Ramsay. Our virtual group homomorphism result does not require familiarity with the technicalities of virtual group theory.     

Two explicit Skorokhod embeddings for simple symmetric random walk

Motivated by problems in behavioural finance, we provide two explicit constructions of a randomized stopping time which embeds a given centred distribution $\mu$ on integers into a simple symmetric random walk in a uniformly integrable manner. Our first construction has a simple Markovian structure: at each step, we stop if an independent coin with a state-dependent bias returns tails. Our second construction is a discrete analogue of the celebrated Azéma–Yor solution and requires independent coin tosses only when excursions away from maximum breach predefined levels. Further, this construction maximizes the distribution of the stopped running maximum among all uniformly integrable embeddings of $\mu$.     

Renewal theorems for random walk with multidimensional time

We consider the sumS(m,n)=X(i,j) of independent identically distributed nonnegative random variables X(i, j) withU(x)=P(s(m,n)x) an analog of the renewal function for a random walk {S(m, n)} with multidimensional time. The behavior of U(x) as x is studied.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 9, pp. 1161–1167, September, 1991.     

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.     

Another look at the Burns-Krantz theorem

We obtain a generalization of the Burns-Krantz rigidity theorem for holomorphic self-mappings of the unit disk in the spirit of the classical Schwarz-Pick Lemma and its continuous version due to L. Harris via the generation theory for one-parameter semigroups. In particular, we establish geometric and analytic criteria for a holomorphic function on the disk with a boundary null point to be a generator of a semigroup of linear fractional transformations in term of relations among three boundary derivatives of the function at this point.     

SOME LIMIT PROPERTIES OF LOCAL TIME FOR RANDOM WALK

Let X,X1,X2 be i. i. d. random variables with EX^2＋δ〈∞ （for some δ〉0）. Consider a one dimensional random walk S={Sn}n≥0, starting from S0 =0. Let ζ＊ （n）=supx∈zζ（x,n）,ζ（x,n） =#{0≤k≤n：[Sk]=x}. A strong approximation of ζ（n） by the local time for Wiener process is presented and the limsup type and liminf-type laws of iterated logarithm of the maximum local time ζ＊（n） are obtained. Furthermore,the precise asymptoties in the law of iterated logarithm of ζ＊（n） is proved.     

Quenched invariance principle for simple random walk on percolation clusters

We consider the simple random walk on the (unique) infinite cluster of super-critical bond percolation in ℤ ^d with d≥2. We prove that, for almost every percolation configuration, the path distribution of the walk converges weakly to that of non-degenerate, isotropic Brownian motion. Our analysis is based on the consideration of a harmonic deformation of the infinite cluster on which the random walk becomes a square-integrable martingale. The size of the deformation, expressed by the so called corrector, is estimated by means of ergodicity arguments.     

Chung-type law of the iterated logarithm for continuous time random walk

A continuous time random walk is a random walk subordinated to a renewal process used in physics to model anomalous diffusion. In this paper, we establish a Chung-type law of the iterated logarithm for continuous time random walk with jumps and waiting times in the domains of attraction of stable laws.     

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.     

The simple random walk and max‐degree walk on a directed graph

We bound total variation and L^∞ mixing times, spectral gap and magnitudes of the complex valued eigenvalues of general (nonreversible nonlazy) Markov chains with a minor expansion property. The resulting bounds for the (nonlazy) simple and max‐degree walks on a (directed) graph are of the optimal order. It follows that, within a factor of two or four, the worst case of each of these mixing time and eigenvalue quantities is a walk on a cycle with clockwise drift. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009