Random walks – expected number of steps

Mouse and cat walk randomly (and independently) on the same consistent 8-regular graph with 20 vertices. At the beginning, they are in non-neighboring vertices. When they are in the same vertex, the cat eats the mouse. Explain that the expected number of steps at which the mouse will be eaten is less than 625 ยท 2^15

I know that average cover time for a random walk over any consistent G graph, for any state initial, is smaller than 2e(G)v(G)., where e(G) is number of edges in graph and v(G) is number verticles.

I also have a small hint that this number of steps should be smaller than 8*(e(G)^2)(v(G)^2), but don’t know how to use it and moreover prove it.

Application of random walks on graphs

Let $ G$ be an electrical network, i.e. a graph with nodes $ \{1,2,\dots,n\}$ in which to every edge $ E_{i,j}$ a conductivity $ \sigma_{i,j}$ is assigned. Suppose an electrical current $ I$ enters the network at node 1 and exists the network at node n (the current may enter and exit from multiple nodes as well). If $ \sigma_{i,j}$ is known, then it is an elementary problem to compute the induced current $ I$ along all edges of the graph $ G$ . Here $ I=(I_{i,j})$ is an $ n \times n$ matrix where $ I_{i,j}$ is the current flowing from node $ i$ to node $ j$ . Note that $ I_{i,j}=-I_{j,i}$ .

Suppose that only the matrix $ |I|=(|I_{i,j}|)$ is known. Assume also that the current entering the network at node 1 and exiting the network at node n is also known. We have developed an algorithm which determines the matrix $ I$ from the knowledge of $ |I|$ , as well as the class of conductivities $ \sigma=(\sigma_{i,j})$ which could produce the current $ I$ over the network. Indeed with this method one can design electrical networks (determine $ \sigma=(\sigma_{i,j})$ ) with prescribed $ |J|=|J_{i,j}|$ , or determine transition probabilities $ P=(p_{i,j})$ in random walk models, where $ p_{i,j}$ is the probability that a random walker takes an step from $ i$ to $ j$ , with prescribed net number of times the walker passes along each edge of the graph, i.e. $ |W_{i,j}-W_{j,i}|$ . Here $ W_{i,j}$ is the expected number of times the walker walks from node $ i$ to $ j$ .

Since electrical networks and random walks on graphs, and other diffusion problems on networks have numerous applications, I wonder if this method has any interesting application in problems that could be modeled by random walks on graphs or electrical networks.

Aspect ratio of random walks from the gyration tensor

In the context of random walks or polymer chains, a useful quantity for capturing and characterizing the shape of the walk or the conformation of the polymer in space is the gyration tensor $ T$ , which in words is the arithmetic mean of the second moment of particle positions along the chain, and visited positions in case of random walks.

Given that the gyration tensor is a symmetric 3-by-3 matrix, it can be diagonalized and written in the following form:

$ $ T = \begin{pmatrix} \lambda_x^2 & 0 & 0 \ 0 & \lambda_y^2 & 0 \ 0 & 0 & \lambda_z^2 \end{pmatrix} \tag{1} $ $ and the axes chosen such that the diagonal elements follow the $ \lambda_z^2 \ge \lambda_y^2 \ge \lambda_x^2$ relation.

The found eigen-spectrum and various function of $ T$ can be used to define geometric descriptors such as:

  • Radius of gyration (average spatial extent of the structure) $ R_g^2 = \lambda_z^2+\lambda_y^2+\lambda_x^2 \tag{2}$

  • The asphericity ($ 0$ when the structure of the walk or the distribution of the particles is spherically symmetric, and positive otherwise) $ b = \frac{1}{2}(3\lambda_z^2-R_g^2) \tag{3}$

  • Similarly, acylindrity ($ 0$ when there’s cylindrical symmetry): $ c = \lambda_y^2 – \lambda_x^2 \tag{4}$

  • Relative shape anisotropy (takes values between $ 0$ and $ 1$ , it reaches near $ 1$ for linear structures, line-like, and $ 0$ for highly symmetric ones), with a slight modification of $ T,$ namely $ \hat{T}_{ij}=T_{ij}-\delta_{ij}\text{Tr}(T/3)$ it can be written as ($ \text{Tr}$ denoting the trace operation) $ $ \kappa^2 = \frac{3}{2}\frac{\text{Tr}(\hat{T}^2)}{(\text{Tr}\hat{T})^2}\tag{5}$ $

  • Nature of asphericity, describing the prolateness or oblateness of the structure, can be expressed as (varying between $ -1$ to $ 1$ , with $ -1$ corresponding to the fully oblate case, and $ 1$ to the fully prolate one.) $ $ S=\frac{4 \text{det}\hat{T}}{\left(\frac{2}{3}\text{Tr}\hat{T}^2\right)^{3/2}} \tag{6} $ $


With all these various measures that describe somewhat differently the geometric structure of the walk or particle distribution, is it possible to also estimate the ratio of the long to the short axis of the structure? (similar to aspect ratio, of two different dimensions of the structure). $ R_g^2$ is only a spatial extent measure (so providing information about one dimension), and $ \kappa^2$ or $ S$ only inform on whether the structure is line-like or ob(pro)-late respectively, but not what their respective aspect ratios are. Would $ R_g S$ be close to such a measure?

Admittedly, I have only recently learned about the gyration tensor and the geometric interpretations of its eigen-spectrum, so I hope I haven’t missed something too naive here.

Random walks on Complete Binary Trees

Let $ T$ be a complete binary tree of height $ n$ and root $ r$ .

A random walk starts at $ r$ , and at each step uniformly at random moves on a neighbor.

There are $ m$ random walkers all starting at $ r$ and let denote with $ H_1,\dots,H_m$ , the heights reached by the walkers after $ n$ steps.

Show that, for some constant $ C$ which do not have to depend on $ n$ and $ m$ , it holds that

$ \mathbb{P}\left(\underset{i \in [m]}\max\left|H_i – \frac{n}{3}\right| \le C \sqrt{n\ln m}\right) \ge 1 – \frac{1}{m}$

I have been trying several strategies, to appropriately define $ H_i$ as sum of random variables and similar, but no one turned out to work. Do you have any idea/suggestion to attach this problem?

Thanks in advance!