# Number of paths ending at a vertex in a functional graph

## Question

Let $G=\left(V,E\right)$ be a directed graph such that all $v\in V$ have outdegree exactly 1. Let $\alpha \in \left[ 0,1\right)$. Denote by $P\left(v\right)$ the set of all paths ending at vertex $v$.

Does $\sum_{p\in P\left( v\right)}{\alpha^{\left|p\right|}}$ converge for all $D,\alpha$ and for any $v\in V$? If not, what can we say about $\alpha$s for which this series converges?

## Observations so far

Firstly, $P\left(v\right)$ is infinite iff $v$ participates in a cycle in $G$, so it suffices to examine only such $v$'s, though I'm not sure if that helps.

To simplify the series, we can notice that $$\sum_{p\in P\left( v\right)}{\alpha^{\left|p\right|}} = \sum_{n=1}^{\infty}{\left| P\left(v\right)\cap V^n \right|\alpha^n}$$ so if $\left| P\left(v\right)\cap V^n \right|$ grows slow enough (or is even bounded) the series will indeed converge, or in other words we wish to prove some notion of sparsity of $P\left(v\right)$ in $V^\ast$. For this, we need to make some combinatorial observation about the number of possible paths given that the outdegree is exactly one, which is where I am stuck (if the claim is indeed true).

## Motivation

I am reading a paper about voting in social networks and am trying to determine whether the voting score in a transitive proxy voting system with exponential damping is necessarily finite, as defined in section 3.1. This is not explicitly stated in the paper.

For $u,v \in V$, define $u \sim v$ if there is a cycle containing both $u$ and $v$. Then $G/\sim$ is a directed graph without cycles. There can be only a finite number of paths in such a graph. Let $m(v) = \left|P_{G/\sim}([v])\right|$ be the number of paths that end in $[v]$.

Now consider a path $p \in P(v)$, where $v$ is part of a cycle $C$. $p = p_1 + p_2$, where $p_1$ is the part of $p$ that leads up to $C$, ending in the first node of $p$ which lies in $C$, $p_2$ starts at the same node and consists of the rest of $p$, and $+$ is the obvious joining.

$p_1$ cannot visit any other cycle, since once it visited one, it could never escape. Therefore $p_1$ translates directly to a path in $G/\sim$. Hence there are at most $m(v)$ choices for $p_1$.

Since $p_2$ is a path in $C$ and ends in $v$, for each natural number $n$, there is a unique $p_2$ with $|p_2| = n$.

Thus for each natural number $n$, there is only one possible choice for $|p_2| = n$, and at most $m(v)$ possible choices for $p_1$. So there are most $m(v)$ choices for $p$, with $n = |p_2| \le |p|$ and therefore $\alpha^{|p|} \le \alpha^n$. Hence $$\sum_{p \in P(v)} \alpha^{|p|} \le \sum_{n=0}^\infty m(v)\alpha^n = m(v) \sum_{n=0}^\infty \alpha^n = \frac {m(v)}{1-\alpha} < \infty$$

• Just to be sure, $G / \sim$ is the condensation of $G$? If $v$ has a loop, wouldn't that loop also appear in $G / \sim$ making it cyclic? Although this is not a problem since in such case $v$ is a sink so the number of paths of length $n$ leading to it is constant for large enough $n$. – 8l2s Nov 29 '17 at 12:59
• Also, what do you mean by "there are at most $m\left( v\right)$ choices for $p_1$? When $p$ is fixed, then so is $p_1$. Similarly, what do you mean by "there is a unique $p_2$ with $\left| p_2 \right| = n$"? – 8l2s Nov 29 '17 at 12:59
• $G/\sim$ is the graph $G$ modulo the equivalence relation $~$. $[v]$ is the set of all nodes equivalent to $v$ in $G$, which is a single node in $G/\sim$. If $u \sim v$, then any edge $u \to v$ is dropped. If $u \nsim v$, then an edge $(u \to v)$ in $G$ becomes an edge $[u]\to [v]$ in $G/\sim$. If $v$ is in a cycle, then $[v]$ is the entire cycle (the nodes). Otherwise $[v] = \{v\}$. So modding by $\sim$ converts all cycles to single nodes. And as there is no way to leave a cycle, cycles become sinks in $G/\sim$. – Paul Sinclair Nov 29 '17 at 17:53
• I am trying to convey that any $p$ is composed of $p_1$ leading up to $C$ and $p_2$ within $C$. The idea is then to use the $p_1$ and $p_2$ components to classify all the possible $p$. And you can check it yourself: For any natural number $n$, there is exactly one path in $C$ ending in $v$ and having length $n$. Since any path leading up to $C$ corresponds 1-1 to a path ending in $[v]$ in $G/\sim$, there are at most $m(v)$ possible paths leading up to $C$. – Paul Sinclair Nov 29 '17 at 18:02