Search

We consider a simple random walk W_i in 1 or 2 dimensions, in which the walker may choose to stand still for a limited time. The time horizon is n, the maximum consecutive time steps which can be spent standing still is m_n and the goal is to maximize P(W_n=0). We show that for dimension 1, if m_n grows faster than (\log n)^{2+\gamma} for some \gamma>0, there is a strategy for each n such that P(W_n = 0) approaches 1. For dimension 2, if m_n grows faster than a positive power of n then there are strategies keeping P(W_n=0) bounded away from 0., Comment: 7 pages

Consider a translation-invariant bond percolation model on the integer lattice which has exponential decay of connectivities, that is, the probability of a connection $0 \leftrightarrow x$ by a path of open bonds decreases like $\exp\{-m(\theta)|x|\}$ for some positive constant $m(\theta)$ which may depend on the direction $\theta = x/|x|$. In two and three dimensions, it is shown that if the model has an appropriate mixing property and satisfies a special case of the FKG property, then there is at most a power-law correction to the exponential decay—there exist $A$ and $C$ such that $\exp\{-m(\theta)|x|\} \ge P(0 \leftrightarrow x) \ge A|x|^{-C} \exp\{-m(\theta)|x|\}$ for all nonzero $x$ . In four or more dimensions, a similar bound holds with $|x|^{-C}$ replaced by $\exp\{-C(\log |x|)^2\}$. In particular the power-law lower bound holds for the Fortuin-Kasteleyn random cluster model in two dimensions whenever the connectivity decays exponentially, since the mixing property is known to hold in that case. Consequently a similar bound holds for correlations in the Potts model at supercritical temperatures.

We prove a central limit theorem for the length of the minimal spanning tree of the set of sites of a Poisson process of intensity $\lambda$ in $[0, 1]^2$ as $\lambda \to \infty$. As observed previously by Ramey, the main difficulty is the dependency between the contributions to this length from different regions of $[0, 1]^2$; a percolation-theoretic result on circuits surrounding a fixed site can be used to control this dependency. We prove such a result via a continuum percolation version of the Russo-Seymour-Welsh theorem for occupied crossings of a rectangle. This RSW theorem also yields a variety of results for two-dimensional fixed-radius continuum percolation already well known for lattice models, including a finite-box criterion for percolation and absence of percolation at the critical point.

Ted Harris was born January 11, 1919, in Philadelphia, Pennsylvania. He grew up in Dallas, Texas, attended Southern Methodist University for two years and completed his undergraduate studies and some graduate work at the University of Texas at Austin. During World War II he served as a weather officer in England in the Army Air Force. He received his Ph.D. in 1947 from Princeton under Sam Wilks. From 1947 to 1966 he was a member of the mathematics department at The Rand Corporation in Santa Monica, California; he headed the department from 1959 to 1965. From 1966 to 1989 he was Professor of Mathematics and Electrical Engineering at the University of Southern California. Since 1989 he has been Professor Emeritus and Lecturer. In 1988 he was elected to the National Academy of Sciences, and in 1989 he received an honorary doctorate from Chalmers Institute of Technology, Sweden. He received an Albert S. Raubenheimer Distinguished Faculty Award in 1985 and a Distinguished Emeritus Award in 1990 from USC.

Given two i.i.d. sequences of $n$ letters from a finite alphabet, one can consider the length $L_n$ of the longest sequence which is a subsequence of both the given sequences. It is known that $EL_n$ grows like $\gamma n$ for some $\gamma \in \lbrack 0, 1\rbrack$. Here it is shown that $\gamma n \geq EL_n \geq \gamma n - C(n \log n)^{1/2}$ for an explicit numerical constant $C$ which does not depend on the distribution of the letters. In simulations with $n = 100,000, EL_n/n$ can be determined from $k$ such trials with 95% confidence to within $0.0055/\sqrt k$, and the results here show that $\gamma$ can then be determined with 95% confidence to within $0.0225 + 0.0055/\sqrt k$, for an arbitrary letter distribution.

Given a finite alphabet, there is an inductive method for constructing a stationary measure on doubly infinite words from this alphabet. This construction can be randomized; the main focus here is on a particular uniform randomization which intuitively corresponds to the idea of choosing a generic stationary process. It is shown that with probability 1, the random stationary process has zero entropy and gives positive probability to every periodic infinite word.

The probability $P\lbrack 0 \leftrightarrow x \rbrack$ of connection of 0 to $x$ by a path of occupied bonds for Bernoulli percolation at density $p$ below the critical point is known to decay exponentially for each direction $x \in \mathbb{Z}^d$, in that $P\lbrack 0 \leftrightarrow nx \rbrack \approx e^{-n\sigma g(x)}$ as $n \rightarrow \infty$ for some $\sigma > 0$ and $g(x)$ of order $\|x\|$. This approximation is also an upper bound: $P\lbrack 0 \leftrightarrow x \rbrack \leq e^{-\sigma g(x)}$ for all $x$. Here a complementary power-law lower bound is established for $d = 2$ and 3: $P\lbrack 0 \leftrightarrow x \rbrack \geq c\|x\|^{-r} e^{-\sigma g(x)}$ for some $r = r(d)$ and $c = c(p,d)$.

Given a class $\mathscr{A}$ of subsets of $\lbrack 0, 1\rbrack^d$ and an array $\{X_j: \mathbf{j} \in \mathbb{Z}^d_+\}$ of independent identically distributed random variables with $EX_j = 0, EX^2_j = 1$, the (unsmoothed) partial-sum process $S_n$ is given by $S_n(A) := n^{-d/2}\sum_{j \in n A}X_j, A \in \mathscr{A}$. If for the metric $\rho(A, B) = |A \Delta B|$ the metric entropy with inclusion $N_1(\varepsilon, \mathscr{A}, \rho)$ satisfies $\int^1_0(\varepsilon^{-1} \log N_I(\varepsilon, \mathscr{A}, \rho))^{1/2} d\varepsilon < \infty$, then an appropriately smoothed version of the partial-sum process converges weakly to the Brownian process indexed by $\mathscr{A}$. This improves on previous results of Pyke (1983) and of Bass and Pyke (1984) which require stronger conditions on the moments of $X_j$.

Sharp exponential bounds for the probabilities of deviations of the supremum of a (possibly non-iid) empirical process indexed by a class $\mathscr{F}$ of functions are proved under several kinds of conditions on $\mathscr{F}$. These bounds are used to establish laws of the iterated logarithm for this supremum and to obtain rates of convergence in total variation for empirical processes on the integers.

Each individual in a population of size $n$ is assigned a positive number as its weight. $k$ of the $n$ are sampled without replacement, with the individuals remaining at the time of each selection chosen with probabilities proportional to their weights. It is shown that for two fixed individuals, the events that each is in the sample can be positively correlated.