Number of paths ending at a vertex in a functional graph

Question

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.

Answer 1

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$$