# Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci

In a series graph, each edge $$e_i$$ exists with probability $$p_i$$. And if you want to examine the existence of edge $$e_i$$, it will cost you $$c_i$$. I want to test the connectivity between source $$s$$ and destination $$d$$ with the minimum expexted cost.

I have figured out that the expected cost can be caculated below if the edge detection sequence is $$e_1, e_2, \cdots e_n$$:

$$E(cost) = c_1 + p_1 * (c_2 + p_2 * (c_3 + p_3 * (\cdots (c_{n-1} + p_{n-1} * c_n)\cdots))))$$

So is there a stretegy or algorithm to find out the minimum expected cost and the edge detection sequence?

Suppose that you test the edges in order. The expected cost is thus $$\sum_{i=1}^n c_i \prod_{j=1}^{i-1} p_j.$$ Now suppose that we switch the order of $$k$$ and $$k+1$$. The two relevant terms are $$c_k \prod_{j=1}^{k-1} p_j + c_{k+1} \prod_{j=1}^k p_j.$$ After switching $$k$$ and $$k+1$$, these two terms become $$c_{k+1} \prod_{j=1}^{k-1} p_j + c_k p_{k+1} \prod_{j=1}^{k-1} p_j.$$ Dividing by $$\prod_{j=1}^{k-1} p_j$$, these two expressions become $$c_k + p_k c_{k+1} \\ c_{k+1} + p_{k+1} c_k$$ The switch leads to an improvement if $$c_k + p_k c_{k+1} > c_{k+1} + p_{k+1} c_k \\ \Longleftrightarrow \\ c_k (1-p_{k+1}) > (1-p_k) c_{k+1} \\ \Longleftrightarrow \\ \frac{c_k}{1-p_k} > \frac{c_{k+1}}{1-p_{k+1}}.$$ This suggests testing the edges in increasing order of $$\frac{c_i}{1-p_i}.$$