共查询到20条相似文献,搜索用时 625 毫秒
1.
Clyde H. Schoolfield Jr. 《Journal of Theoretical Probability》2002,15(3):667-693
We bound the rate of convergence to uniformity for a certain random walk on the complete monomial groups GS
n
for any group G. Specifically, we determine that
n log n+
n log (|G|–1|) steps are both necessary and sufficient for 2 distance to become small. We also determine that
n log n steps are both necessary and sufficient for total variation distance to become small. These results provide rates of convergence for random walks on a number of groups of interest: the hyperoctahedral group 2S
n
, the generalized symmetric group
m
S
n
, and S
m
S
n
. In the special case of the hyperoctahedral group, our random walk exhibits the cutoff phenomenon. 相似文献
2.
In this paper, we look at the lower bounds of two specific random walks on the dihedral group. The first theorem discusses
a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p
2 steps are necessary for the walk to become close to uniformly distributed on all of D
2p
where p≥3 is an integer. Next we take a random walk on the dihedral group generated by a random k-subset of the dihedral group. The latter theorem shows that it is necessary to take roughly p
2/(k−1) steps in the typical random walk to become close to uniformly distributed on all of D
2p
. We note that there is at least one rotation and one flip in the k-subset, or the random walk generated by this subset has periodicity problems or will not generate all of D
2p
. 相似文献
3.
Martin Hildebrand 《Journal of Algebraic Combinatorics》1992,1(2):133-150
This paper studies a random walk based on random transvections in SL
n(F
q
) and shows that, given
> 0, there is a constant c such that after n + c steps the walk is within a distance
from uniform and that after n – c steps the walk is a distance at least 1 –
from uniform. This paper uses results of Diaconis and Shahshahani to get the upper bound, uses results of Rudvalis to get the lower bound, and briefly considers some other random walks on SL
n(F
q
) to compare them with random transvections. 相似文献
4.
Martin Hildebrand 《Probability Theory and Related Fields》1994,100(2):191-203
Summary This paper considers random walks on the integers modn supported onk points and asks how long does it take for these walks to get close to uniformly distributed. Ifk is a constant, Greenhalgh showed that at least some constant timesn
2/(k–1) steps are necessary to make the distance of the random walk from the uniform distribution small; here we show that ifn is prime, some constant timesn
2/(k–1) steps suffice to make this distance small for almost all choices ofk points. The proof uses the Upper Bound Lemma of Diaconis and Shahshahani and some averaging techniques. This paper also explores some cases wherek varies withn. In particular, ifk=(logn)
a
, we find different kinds of results for different values ofa, and these results disprove a conjecture of Aldous and Diaconis.Research Supported in Part by a Rackham Faculty Fellowship at the University of Michigan 相似文献
5.
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. 相似文献
6.
In Csáki et al.
(1) and Révész and Willekens(9) it was proved that the length of the longest excursion among the first n excursions of a plane random walk is nearly equal to the total sum of the lenghts of these excursions. In this paper several results are proved in the same spirit, for plane random walks and for random walks in higher dimensions. 相似文献
7.
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
\mathbbRn{\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
\mathbbR2{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic. 相似文献
8.
We give a randomized algorithm using O(n7 log2 n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O(n6 log4 n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O(n5 log4 n) for centrally symmetric polytopes with a polynomial number of facets. We also give an O(n6 log n) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc. 相似文献
9.
Amir Dembo Nina Gantert Yuval Peres Zhan Shi 《Probability Theory and Related Fields》2007,137(3-4):443-473
Let ξ (n, x) be the local time at x for a recurrent one-dimensional random walk in random environment after n steps, and consider the maximum ξ*(n) = max
x
ξ(n, x). It is known that lim sup
is a positive constant a.s. We prove that lim inf
is a positive constant a.s. this answers a question of P. Révész [5]. The proof is based on an analysis of the valleys in the environment, defined as the potential wells of record depth. In particular, we show that almost surely, at any time
n large enough, the random walker has spent almost all of its lifetime in the two deepest valleys of the environment it has
encountered. We also prove a uniform exponential tail bound for the ratio of the expected total occupation time of a valley
and the expected local time at its bottom. 相似文献
10.
Driss Gretete 《Rendiconti del Circolo Matematico di Palermo》2011,60(3):329-335
We use the estimate of paths in Z 2 enclosing a null algebraic area to compute correction terms on the random walk on certain discrete Heisenberg groups. We obtain that the probability to return at the origin of the simple random walk on this group is $\frac{1}{4n^{2}}+O(\frac{1}{n^{3}})$ . 相似文献
11.
Given n vectors {i} ∈ [0, 1)d, consider a random walk on the d‐dimensional torus ??d = ?d/?d generated by these vectors by successive addition and subtraction. For certain sets of vectors, this walk converges to Haar (uniform) measure on the torus. We show that the discrepancy distance D(Q*k) between the kth step distribution of the walk and Haar measure is bounded below by D(Q*k) ≥ C1k?n/2, where C1 = C(n, d) is a constant. If the vectors are badly approximated by rationals (in a sense we will define), then D(Q*k) ≤ C2k?n/2d for C2 = C(n, d, j) a constant. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004 相似文献
12.
Jason Schweinsberg 《Journal of Theoretical Probability》2008,21(2):378-396
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. 相似文献
13.
We study the Linial–Meshulam model of random two-dimensional simplicial complexes. One of our main results states that for
p≪n
−1 a random 2-complex Y collapses simplicially to a graph and, in particular, the fundamental group π
1(Y) is free and H
2(Y)=0, asymptotically almost surely. Our other main result gives a precise threshold for collapsibility of a random 2-complex
to a graph in a prescribed number of steps. We also prove that, if the probability parameter p satisfies p≫n
−1/2+ϵ
, where ϵ>0, then an arbitrary finite two-dimensional simplicial complex admits a topological embedding into a random 2-complex, with
probability tending to one as n→∞. We also establish several related results; for example, we show that for p<c/n with c<3 the fundamental group of a random 2-complex contains a non-abelian free subgroup. Our method is based on exploiting explicit
thresholds (established in the paper) for the existence of simplicial embeddings and immersions of 2-complexes into a random
2-complex. 相似文献
14.
Summary We compute the expected values of certain random variables associated with a random process of manifolds in R
n
by inserting certain general formulas of integral geometry into the definition of the moment measures of a point process.Dedicated to Professor Leopold Schmetterer on the occasion of his 60th Birthday 相似文献
15.
We present an upper bound O(n
2
) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant,
and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion
process on a circle indeed mixes more rapidly than the corresponding symmetric process.
Received: 25 January 1999 / Revised version: 17 September 1999 / Published online: 14 June 2000 相似文献
16.
In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let Gln denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph Gln we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges. 相似文献
17.
U. A. Rozikov 《Mathematical Notes》2000,67(1):103-107
Random walks in random environments on countable metric groups with bounded jumps of the walking particle are considered.
The transition probabilities of such a random walk from a pointx εG (whereG is the group in question) are described by a vectorp(x) ε ℝ|W| (whereW ⊏G is fixed and |W|<∞). The set {p(x),x εG} is assumed to consist of independent identically distributed random vectors. A sufficient condition for this random walk
to be transient is found. As an example, the groups ℤ
d
, free groups, and the free product of finitely many cyclic groups of second order are considered.
Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 129–135, January, 2000. 相似文献
18.
A random walk on the set of integers {0,1,2,...,a} with absorbing barriers at 0 and a is considered. The transition times from the integers z (0<z<a) are random variables with finite moments. The nth moment of the time to absorption at a, Dz,n, conditioned on the walk starting at z and being absorbed at a, is discussed, and a difference equation with boundary values and initial values for Dz,n is given. It is solved in several special cases. The problem is motivated by questions from biology about tumor growth and multigene evolution which are discussed. 相似文献
19.
D. Bertacchi 《Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg》2001,71(1):205-224
We investigate various features of a quite new family of graphs, introduced as a possible example of vertex-transitive graph
not roughly isometric with a Cayley graph of some finitely generated group. We exhibit a natural compactification and study
a large class of random walks, proving theorems concerning almost sure convergence to the boundary, a strong law of large
numbers and a central limit theorem. The asymptotic type of then-step transition probabilities of the simple random walk is determined. 相似文献
20.
Given a high dimensional convex body K⊆ℝn by a separation oracle, we can approximate its volume with relative error ε, using O*(n5) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding” followed by a multiphase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing; and a stepwise interlacing of rounding and sampling. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 1–50, 1997 相似文献