Convergence of the average weight of an infinite path through a weighted directed graph

Question

Consider a directed graph $G = (V, E, w)$, where $V$ is the set of vertices, $E \subseteq V \times V$ is the set of directed edges (with self-loops allowed), and $w : E \to \mathbb{R}_+$ is a weight function that assigns a fixed positive weight to each edge in $G$. For any infinite non-periodic path $p = v_0 \overset{e_0}{\to} v_1 \overset{e_1}{\to} v_2 \overset{e_2}{\to}\ldots$ through $G$, let $\bar{w}_t(p) = \frac{1}{t} \sum_{i=0}^{t-1} w(e_i)$ denote the mean of the weights of the first $t$ edges traversed in the path $p$.

Given $G$ and $p$, what are necessary and sufficient conditions for $\lim_{t \to \infty} \bar{w}_t(p)$ to exist?

Answer 1

I will be thinking of $G$ as locally finite.

The simplest case is if $p$ is a ray (this is also the only case if you meant "path" in the usual graph-theoretic sense). In that case, this is a calculus problem; the only necessary and sufficient condition is that the sequence $w(e_i)$ is such that its partial averages converge, and this condition does not reduce to a graph-theoretic one.

This case is more interesting when we want $\overline{w_t}(p)$ to converge for every ray.

Claim: If the weight of every ray converges, then equivalent rays have equal weights.

Proof: Consider two rays $R$, $R'$ with weights $w$, $w'$ and a ray $L$ which bounces between them, coinciding with each of them long enough to approximate their corresponding weights more and more before passing to the other. Then $w(R)=w(L)=w(R')$, concluding the proof.

Corollary: If the weight of every ray converges, then there are at most as many weights of rays as there are ends of $G$. In fact, for every $x\in \mathbb{R}_{+}^N$, where $N$ is the number of ends of $G$, there exists a weight function $w'$ such that the multiset of weights of rays of $G$ is exactly the multiset of coordinates of $x$.

Now, a simple sufficient condition for the weights of rays to converge would be if the weights of edges converge as their distance from an arbitrary root increases. More generally, one can pick an arbitrary root and an arbitrary increasing sequence of finite subgraphs $H_i$ with $H_0$ being the root and $G\setminus H_i$ having only connected components of infinite size. Initially, all of the edges are thought to "take" weights in $[0,1]$. Whenever a connected component the edges of which take weights in $[a,b]$ splits into $n$ new connected components, partition $[a,b]$ into $n$ intervals and assign an interval to each of the new connected components. This process yields a way to pick a weight for each edge so that the weight of each ray converges: just assign to the edge $e$ a weight from the interval associated with the connected component of $G\setminus H_k$ that contains it, where $H_k$ is the last element of the sequence $H_i$ that does not contain $e$.

It is easy to see that all of the above also hold in the more general case of transient paths.

Now, for a different case, let us see what happens if $p$ is bounded. If $p$ is periodic, then of course its weight converges. If $p$ is not periodic, as stated in the question, then still it must visit a certain vertex $v$ with positive density, and there must be at least two distinct closed walks from $v$ to itself. Let $S$ be the set of closed walks $v\rightarrow v$ within the ball $B$ in which $p$ lies. Identify the times that $p$ crosses $v$ with $\mathbb{N}$. Then it is easy to note that, if the density of the times when $p$ chooses to traverse each element of $S$ converges, $\overline{w_t}(p)$ converges as well.

So, we have seen sufficient conditions for transient paths and for bounded paths. It remains to come up with necessary conditions for those cases, and to think about recurrent paths.