Expected hitting times for a random walk on a connected graph (Q1080258): Difference between revisions

Let \(G_ N\), \(N\geq 2\), denote any undirected connected graph without loops or multiple edges, having N vertices. Let \(V(G_ N)\) and \(E(G_ N)\) denote the set of vertices and the set of edges of \(G_ N\), respectively. Let \(v(x)=v(x,G_ N)\) denote the number of vertices of \(G_ N\) which are connected with \(x\in V(G_ N)\). Consider a simple random walk S(n), \(n\geq 0\), on \(V(G_ N)\) having transition probabilities \(p_{xy}\) given by \[ p_{xy} = \begin{cases} 0, &\text{if \((x,y)\not\in E(G_ N)\)} \\ 1/v(x), &\text{if \((x,y)\in E(G_ N).\)}\end{cases} \] Given that \(S(0)=x\), put \(e(x,y;G_ N)=E_ x(\tau (y))\), \(x,y\in V(G_ N)\), where the stopping time \(\tau\) (y) is given by \(\tau (y)=\inf \{j:S(j)=y\}\). The author obtains the following results: (i) \(e(x,y;G_ N)\leq N(N-1)^ 2\), \(N\geq 2;\) (ii) If, for some constant K, \(v(x;G_ N)\leq K\), \(x\in V(G_ N)\), then \(e(x,y;G_ N)\leq KN(N-1).\) Examples show that the order of magnitude of the bounds given in (i) and (ii) is best possible as \(N\to \infty\).