On the monotonicity of the speed of random walks on a percolation cluster of trees (Q2477790): Difference between revisions

The simple random walk \(\{X_n\}\) on graph \(G\) is defined as Markov chain on the set of its vertices with transition probability \(p(x,y)=1/d_x\) if there is an edge between \(x,y\) and if \(d_x\) is a number of edges connected to vertex \(x\). If \(G\) is a tree and \(X_n\) starts from the root then the \(\lim_n | X_n| /n\), if it exists, is called the speed of the simple random walk, where \(| X_n| \) is a distance from the root. Bernoulli bond percolation on \(G\) is defined as its subgraph which independently retains each edge of \(G\) with probability \(p\) and does not retain it with probability \(1-p\). A connected component of this subgraph is called a cluster. The authors consider the simple random walk on the infinite cluster of the Bernoulli bond percolation of trees, and investigate the relation between the simple random walk and retaining probability \(p\) by studying three classes of trees: the regular tree, Galton-Watson trees, and the binary tree with pipes, which is obtained by adding a pipe to each vertex of the binary tree. A sufficient condition is established for Galton-Watson trees.