共查询到20条相似文献,搜索用时 31 毫秒
1.
Let {S
k
, k ≥ 0} be a symmetric random walk on , and an independent random field of centered i.i.d. random variables with tail decay . We consider a random walk in random scenery, that is . We present asymptotics for the probability, over both randomness, that {X
n
> n
β} for β > 1/2 and α > 1. To obtain such asymptotics, we establish large deviations estimates for the self-intersection local
times process , where l
n
(x) is the number of visits of site x up to time n.
相似文献
2.
We present a multiscale analysis for the exit measures from large balls in , of random walks in certain i.i.d. random environments which are small perturbations of the fixed environment corresponding
to simple random walk. Our main assumption is an isotropy assumption on the law of the environment, introduced by Bricmont
and Kupiainen. Under this assumption, we prove that the exit measure of the random walk in a random environment from a large
ball, approaches the exit measure of a simple random walk from the same ball, in the sense that the variational distance between
smoothed versions of these measures converges to zero. We also prove the transience of the random walk in random environment.
The analysis is based on propagating estimates on the variational distance between the exit measure of the random walk in
random environment and that of simple random walk, in addition to estimates on the variational distance between smoothed versions
of these quantities.
Partially supported by NSF grant DMS-0503775. 相似文献
3.
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 ℓ2 distance to become small. This random walk arose as the result of an effort in molecular biology to model certain types of
genome rearrangements. 相似文献
4.
We prove large deviations principles in large time, for the Brownian occupation time in random scenery . The random field is constant on the elements of a partition of d into unit cubes. These random constants, say consist of i.i.d. bounded variables, independent of the Brownian motion {Bs,s0}. This model is a time-continuous version of Kesten and Spitzer's random walk in random scenery. We prove large deviations principles in ``quenched' and ``annealed' settings.Mathematics Subject Classification (2000):60F10, 60J55, 60K37 相似文献
5.
David Gluck 《Journal of Theoretical Probability》1999,12(3):739-755
We consider a random walk on a finite group G based on a generating set that is a union of conjugacy classes. Let the nonnegative integer valued random variable T denote the first time the walk arrives at the identity element of G, if the starting point of the walk is uniformly distributed on G. Under suitable hypotheses, we show that the distribution function F of T is almost exponential, and we give an error term. 相似文献
6.
J. Hoffmann-Jørgensen 《Journal of Theoretical Probability》1999,12(1):131-145
Let N
n denote the number of positive sums in the first n trials in a random walk (S
i) and let L
n denote the first time we obtain the maximum in S
0,..., S
n. Then the classical equivalence principle states that N
n and L
n have the same distribution and the classical arcsine law gives necessary and sufficient condition for (1/n) L
n or (1/n) N
n to converge in law to the arcsine distribution. The objective of this note is to provide a simple and elementary proof of the arcsine law for a general class of integer valued random variables (T
n) and to provide a simple an elementary proof of the equivalence principle for a general class of integer valued random vectors (N
n, L
n). 相似文献
7.
Amir Dembo Nina Gantert Yuval Peres Ofer Zeitouni 《Probability Theory and Related Fields》2002,122(2):241-288
In the study of large deviations for random walks in random environment, a key distinction has emerged between quenched asymptotics, conditional on the environment, and annealed asymptotics, obtained from averaging over environments. In this paper we consider a simple random walk {X
n
} on a Galton–Watson tree T, i.e., on the family tree arising from a supercritical branching process. Denote by |X
n
| the distance between the node X
n
and the root of T. Our main result is the almost sure equality of the large deviation rate function for |X
n
|/n under the “quenched measure” (conditional upon T), and the rate function for the same ratio under the “annealed measure” (averaging on T according to the Galton–Watson distribution). This equality hinges on a concentration of measure phenomenon for the momentum of the walk. (The momentum at level n, for a specific tree T, is the average, over random walk paths, of the forward drift at the hitting point of that level). This concentration, or
certainty, is a consequence of the uncertainty in the location of the hitting point. We also obtain similar results when {X
n
} is a λ-biased walk on a Galton–Watson tree, even though in that case there is no known formula for the asymptotic speed.
Our arguments rely at several points on a “ubiquity” lemma for Galton–Watson trees, due to Grimmett and Kesten (1984).
Received: 15 November 2000 / Revised version: 27 February 2001 / Published online: 19 December 2001 相似文献
8.
David Bruce Wilson 《Probability Theory and Related Fields》1997,108(4):441-457
Summary. We consider random walks on classes of graphs defined on the d-dimensional binary cube ℤ2
d
by placing edges on n randomly chosen parallel classes of vectors. The mixing time of a graph is the number of steps of a random walk before the
walk forgets where it started, and reaches a random location. In this paper we resolve a question of Diaconis by finding exact
expressions for this mixing time that hold for all n>d and almost all choices of vector classes. This result improves a number of previous bounds. Our method, which has application
to similar problems on other Abelian groups, uses the concept of a universal hash function, from computer science. 相似文献
9.
Silke W.W. Rolles 《Probability Theory and Related Fields》2006,135(2):216-264
Let G be a finite tree. It is shown that edge-reinforced random walk on ℤ×G with large initial weights is recurrent. This includes recurrence on multi-level ladders of arbitrary width. For edge-reinforced
random walk on {0,1, . . . ,n}×G, it is proved that asymptotically, with high probability, the normalized edge local times decay exponentially in the distance
from the starting level. The estimates are uniform in n. They are used in the recurrence proof. 相似文献
10.
Uniform random mappings of an n-element set to itself have been much studied in the combinatorial literature. We introduce a new technique, which starts by specifying a coding of mappings as walks with ± 1 steps. The uniform random mapping is thereby coded as a nonuniform random walk, and our main result is that as n→∞ the random walk rescales to reflecting Brownian bridge. This result encompasses a large number of limit theorems for “global” characteristics of uniform random mappings. © 1994 John Wiley & Sons, Inc. 相似文献
11.
Mei Juan Zhang 《数学学报(英文版)》2014,30(3):395-410
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. 相似文献
12.
Harry Kesten R. A. Maller 《Annales de l'Institut Henri Poincaré (B) Probabilités et Statistiques》1999,35(6):685
We show that the passage time, T*(r), of a random walk Sn above a horizontal boundary at r (r≥0) is stable (in probability) in the sense that
as r→∞ for a deterministic function C(r)>0, if and only if the random walk is relatively stable in the sense that
as n→∞ for a deterministic sequence Bn>0. The stability of a passage time is an important ingredient in some proofs in sequential analysis, where it arises during applications of Anscombe's Theorem. We also prove a counterpart for the almost sure stability of T*(r), which we show is equivalent to E|X|<∞, EX>0. Similarly, counterparts for the exit of the random walk from the strip {|y|≤r} are proved. The conditions arefurther related to the relative stability of the maximal sum and the maximum modulus of the sums. Another result shows that the exit position of the random walk outside the boundaries at ±r drifts to ∞ as r→∞ if and only if the random walk drifts to ∞. 相似文献
13.
Alain-Sol Sznitman 《Probability Theory and Related Fields》1999,115(3):287-323
We consider a d-dimensional random walk in random environment for which transition probabilities at each site are either neutral or present
an effective drift “pointing to the right”. We obtain large deviation estimates on the probability that the walk moves in
a too slow ballistic fashion, both under the annealed and quenched measures. These estimates underline the key role of large
neutral pockets of the medium in the occurrence of slowdowns of the walk.
Received: 12 March 1998 / Revised version: 19 February 1999 相似文献
14.
Our work is motivated by Bourque and Pevzner's (2002) simulation study of the effectiveness of the parsimony method in studying
genome rearrangement, and leads to a surprising result about the random transposition walk on the group of permutations on
n elements. Consider this walk in continuous time starting at the identity and let D
t
be the minimum number of transpositions needed to go back to the identity from the location at time t. D
t
undergoes a phase transition: the distance D
cn
/2∼u(c)n, where u is an explicit function satisfying u(c)=c/2 for c≤1 and u(c)<c/2 for c>1. In addition, we describe the fluctuations of D
cn
/2 about its mean in each of the three regimes (subcritical, critical and supercritical). The techniques used involve viewing
the cycles in the random permutation as a coagulation-fragmentation process and relating the behavior to the Erdős-Renyi random
graph model. 相似文献
15.
H. Bohman 《BIT Numerical Mathematics》1971,11(2):133-138
We consider a random walk with drift to the left. LetM
n
denote the extreme position to the right of the particle during its firstn steps. An approximate expression for the characteristic function of the distribution of this random variable is evaluated. The numerical inversion of this characteristic function is performed with the aid of the Fast Fourier Transform. 相似文献
16.
Consider an arbitrary transient random walk on ℤ
d
with d∈ℕ. Pick α∈[0,∞), and let L
n
(α) be the spatial sum of the αth power of the n-step local times of the walk. Hence, L
n
(0) is the range, L
n
(1)=n+1, and for integers α, L
n
(α) is the number of the α-fold self-intersections of the walk. We prove a strong law of large numbers for L
n
(α) as n→∞. Furthermore, we identify the asymptotic law of the local time in a random site uniformly distributed over the range. These
results complement and contrast analogous results for recurrent walks in two dimensions recently derived by Černy (Stoch.
Proc. Appl. 117:262–270, 2007). Although these assertions are certainly known to experts, we could find no proof in the literature in this generality.
相似文献
17.
E. Kh. Gimadi 《Journal of Applied and Industrial Mathematics》2011,5(2):212-220
In order to solve the location problem in the p-median form we present an approximation algorithm with time complexity O(n
2) and the results of its probabilistic analysis. The input data are defined on a complete graph with distances between the
vertices expressed by the independent random variables with the same uniform distribution. The value of the objective function
produced by the algorithm amounts to a certain sum of the random variables that we analyze basing on an estimate for the probabilities
of large deviations of these sums. We use a limit theorem in the form of the Petrov inequalities, taking into account the
dependence of the random variables in the sum. The probabilistic analysis yields some estimates for the relative error and
the failure probability of our algorithm, as well as conditions for its asymptotic exactness. 相似文献
18.
Jeff D. Kahn Nathan Linial Noam Nisan Michael E. Saks 《Journal of Theoretical Probability》1989,2(1):121-128
This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n
2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271. 相似文献
19.
C.J.H. McDiarmid R.B. Hayward 《Journal of Algorithms in Cognition, Informatics and Logic》1996,21(3):476-507
LetQnbe the random number of comparisons made by quicksort in sortingndistinct keys when we assume that alln! possible orderings are equally likely. Known results concerning moments forQndo not show how rare it is forQnto make large deviations from its mean. Here we give a good approximation to the probability of such a large deviation and find that this probability is quite small. As well as the basic quicksort, we consider the variant in which the partitioning key is chosen as the median of (2t+1) keys. 相似文献
20.
We give necessary and sufficient conditions for the almost sure relative stability of the overshoot of a random walk when
it exits from a two-sided symmetric region with curved boundaries. The boundaries are of power-law type, ±rn
b
, r > 0, n = 1, 2,..., where 0 ≤ b < 1, b≠ 1/2. In these cases, the a.s. stability occurs if and only if the mean step length of the random walk is finite and non-zero,
or the step length has a finite variance and mean zero.
相似文献