I apologize in advance if this question is too simplistic to be appropriate for MathOverflow. I have inquired in multiple places but have found little to indicate that this is a previously studied problem, and my own understanding of probability and discrete mathematics is too sparse and incomplete for me to have any sort of intuition about whether this is a difficult problem or not.
Consider a Markov chain with $N$ nodes and let $T_{ij}$ and $C_{ij}$ respectively denote the transition probability and 'cost' for moving from node $i$ to $j$. Now consider a position vector $p(t)$ which has $N$ entries; at time step $t$, the probability of being at node $i$ is given by $p_i(t)$. Consider also a cost vector $c(t)$ which has $N$ entries; at time step $t$, the cost incurred conditioned on being at node $j$ is given by $c_j(t)$. At time $t = 0$, we have probability $1$ of being on a specific 'starting' node. In our transition matrix $T$, we add an attractor at a 'final' node, setting the transition probability away from it to $0$.
Now suppose that we iterate this model forward in time with the standard update $p(t+1) = p(t) \cdot T$ on the position vector and
$$ c_i(t+1) = \sum_{j = 1}^N \mathrm{P}(\mathrm{was\ at\ }j | \mathrm{am\ at\ }i) (c_j(t) + C_{ji}) $$
for the cost vector, where
$$ \mathrm{P}(\mathrm{was\ at\ }j | \mathrm{am\ at\ }i) = \frac{\mathrm{P}(\mathrm{am\ at\ }i | \mathrm{was\ at\ }j) \cdot \mathrm{P}(\mathrm{was\ at\ }j)}{\mathrm{P}(\mathrm{am\ at\ }i)} = \frac{T_{ji} \cdot p_j(t)}{p_i(t+1)}. $$
Let $f$ be index of the final node. Moving the model forward in time until the probability of having reached the final node is above some certain threshold, e.g. $0.9999$, we obtain, at each time $t$, a point $(c_f(t), p_f(t))$ on the 'cumulative distribution curve of cost', i.e. a graph that relates the probability of having reached the final node given a particular amount of total expenditure.
This is a workable computational way of plotting this 'cumulative distribution of cost'. However, I am curious if we can say take this forward analytically any further than we already have. I am not looking for any specific thing in particular, rather I simply want to know if we can say anything interesting about this 'cumulative distribution of cost' without resorting to brute force computations.
The structures of $T$ and $C$ are quite arbitrary in practice, so generalized approaches are best, but I am also curious to know what could be done if certain limitations are imposed upon the structure of $T$ and $C$.
Any pointers to books or papers would also be appreciated.
