I'm refering to the following paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.329.3653&rep=rep1&type=pdf.
There is a lemma states:
Let $G$ be a directed acyclic graph with source $s$ and sink $t$. Let each edge $e = (v_i, v_j)$ of $G$ have weight $w(e)$ (we also use the notation $w(e) = w(v_i, v_j)$), and each node have weight $w(vi)$. Assume without loss of generality that $$\sum_{all\ paths\ P=(v_1,...,v_{k(P)}) }{ w(v_1)\prod_{i=2}^{k(P)}{w(v_{i−1}, v_i)w(v_i) = 1} }$$ It is possible to pick at random a path $P$ consisting of $s = v_1, v_2,...,v_{k(P)} = t$ in time $O(n)$ such that $$Pr(picking\ P) = w(s)\prod_{i=2}^{k(P)} {w(v_{i−1}, v_i)w(v_i) }$$
The aim of the lemma is give a method for sampling in a HMM graph. The proof is by induction on the maximal lenght of a path between s and t.
My questions is:
Why assume that all path weight sum up to 1? and why without loss of generality?
I have thinked that only paths between $s$ and $t$ should sum up to 1. I guess that is related to the proof that is based on maximal leght of a path between $s$ and $t$ but how?