Expected steps for a simple random walk to reach a target vertex

Formula: with \(P_{ij} = w_{ij}/\sum_k w_{ik}\), \(H(t,t) = 0\) and \(H(i,t) = 1 + \sum_j P_{ij} H(j,t)\) for \(i \ne t\) – a linear system of size n-1, solved exactly rather than by simulating the walk. Vertices from which the target is unreachable have infinite hitting time and are reported as such instead of being dropped or given a large finite number; the system is solved only over the vertices that can reach it. Hitting time is not symmetric, which is why the commute time H(i,j) + H(j,i) is the quantity with metric behaviour.

Usage

Hittime(G, start = NULL, target = 0L)

Arguments

G

n by n non-negative weight matrix; zero means no edge.

start

Starting vertex, 0-based to match the Python arm; selects the scalar reported as estimate. All vertices are returned regardless.

target

Vertex to be hit, 0-based.

Value

List with estimate, hitting, target, start, n, method.

References

Lovasz (1996), Random walks on graphs: a survey, in Combinatorics, Paul Erdos is Eighty, vol. 2, pp. 353-398. This is the standard first-step recurrence. It is checked on the cycle C_n, where the classical closed form H(i,j) = d(n-d) with d the cyclic distance holds exactly and is independent of this code.

Examples

G <- matrix(c(0, 1, 0, 1, 0, 1, 0, 1, 0), 3)   # path 0 - 1 - 2
Hittime(G, start = 0L, target = 2L)$estimate   # 4 = (n - 1)^2 steps on a path
#> [1] 4