Scenery reconstruction with branching random walk

We study the problem of scenery reconstruction in arbitrary dimension using observations registered in boxes of size k (for k fixed), seen along a branching random walk. We prove that, using a large enough k for almost all the realizations of the branching random walk, almost all sceneries can be reconstructed up to equivalence.     

On optimal search plans to detect a target moving randomly on the real line

A target, whose initial position is unknown, is performing a random walk on the integers. A searcher, starting at the origin, wants to follow a search plan for which E[τ^k] is finite, where k ≥ 1 and τ is the time to capture. The searcher, who has a prior distribution over the target's initial position, can move only to adjacent positions, and cannot travel faster than the target. Necessary and sufficient conditions are given for the existence of search plans for which E[τ^k] is finite and a minimum.     

On the height of random m-ary search trees

A random m-ary seach tree is constructed from a random permutation of 1,…, n. A law of large numbers is obtained for the height H_n of these trees by applying the theory of branching random walks. in particular, it is shown that H_n/log n→γ in probability as n→∞ where γ = γ(m) is a constant depending upon m only. Interestingly, as m→∞, γ(m) is asymptotic to 1/log m, the coefficient of log n in the asymptotic expression for the height of the complete m-ary search tree. This proves that for large m, random m-ary search trees behave virtually like complete m-ary trees.     

Patterns in random binary search trees

In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 : 223–244, 1997     

On total progeny of multitype Galton-Watson process and the first passage time of random walk on lattice

In this paper,we form a method to calculate the probability generating function of the total progeny of multitype branching process.As examples,we calculate probability generating function of the total progeny of the multitype branching processes within random walk which could stay at its position and(2-1) random walk.Consequently,we could give the probability generating functions and the distributions of the first passage time of corresponding random walks.Especially,for recurrent random walk which could stay at its position with probability 0 r 1,we show that the tail probability of the first passage time decays as 2/(π(1-r)~(1/2)) n~(1/1)= when n →∞.     

出生率与年龄段有关的生灭分枝树

本文基于生灭过程的生灭演化机理, 将生物繁衍过程描述为有向随机图过程-随机分枝树, 建立了出生率与年龄段有关的生灭分枝树演化模型. 本文研究了任一节点在不同年龄及临死时刻的出度分布、虚出度分布和拟出度分布, 并证明了拟出度过程是随机时刻终止的Poisson过程, 讨论了首生年龄及相对出生年龄的分布, 给出了任一节点成为孤立节点的概率.     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

Majorizing kernels and stochastic cascades with applications to incompressible Navier-Stokes equations

A general method is developed to obtain conditions on initial data and forcing terms for the global existence of unique regular solutions to incompressible 3d Navier-Stokes equations. The basic idea generalizes a probabilistic approach introduced by LeJan and Sznitman (1997) to obtain weak solutions whose Fourier transform may be represented by an expected value of a stochastic cascade. A functional analytic framework is also developed which partially connects stochastic iterations and certain Picard iterates. Some local existence and uniqueness results are also obtained by contractive mapping conditions on the Picard iteration.

     

On the Monotonicity of the Speed of Random Walks on a Percolation Cluster of Trees

The authors consider the simple random walk on the infinite cluster of the Bernoulli bond percolation of trees, and investigate the relation between the speed of the simple random walk and the retaining probability p by studying three classes of trees. A sufficient condition is established for Galton-Watson trees.     

The type problem for random walks on trees

We consider the question of whether the simple random walk (SRW) on an infinite tree is transient or recurrent. For random-trees (all vertices of distancen from the root of the tree have degreed _n , where {d _n } are independent random variables), we prove that the SRW is a.s. transient if lim inf _n n E(log(d _n-1))>1 and a.s. recurrent if lim sup _n n E(log(d _n-1))<1. For random trees in which the degrees of the vertices are independently 2 or 3, with distribution depending on the distance from the root, a partial classification of type is obtained.Research supported in part by NSF DMS 8710027.     

Random Walks on Trees with Finitely Many Cone Types

This paper is devoted to the study of random walks on infinite trees with finitely many cone types (also called periodic trees). We consider nearest neighbour random walks with probabilities adapted to the cone structure of the tree, which include in particular the well studied classes of simple and homesick random walks. We give a simple criterion for transience or recurrence of the random walk and prove that the spectral radius is equal to 1 if and only if the random walk is recurrent. Furthermore, we study the asymptotic behaviour of return probabilitites and prove a local limit theorem. In the transient case, we also prove a law of large numbers and compute the rate of escape of the random walk to infinity, as well as prove a central limit theorem. Finally, we describe the structure of the boundary process and explain its connection with the random walk.