Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed subgraphs of $G$ (not necessarily induced subgraphs, but graphs with the same vertices as $G$). Each such space has an event "$H$ has $e$"; this is the probability that a randomly chosen graph $H$ from $S$ has $e$ as an edge between its source and target. Let's say that a $G$-space is a probability space of this form with the property that for each edge $e$ of the original $G$, $Pr[\mbox{$H$ has $e$}]\geq n(e)$.
The question concerns estimating the probability in a $G$-space that there is a directed path from the original $s$ to the original $t$.
It is easy to get a lower bound on this probability. For each path $p = e_1, . . . , e_k$ from s to t, let $f(p) = n(e1) + \cdots + n(e_k) - k + 1$. For all G-spaces S, the probability that there is a directed edge from $s$ to $t$ is at least $\max(0, f(p))$. And so the lower bound on the probability we are after is the maximum over all paths $p$ from $s$ to $t$ of $\max(0, f(p))$.
My question is whether this bound is tight. In special cases, a colleague and I have verified that it is indeed tight, but before we invest further time and energy, I wonder if anyone has seen this or something similar. We also have a formulation of a related problem in terns of linear inequalities, but since this is long enough already I won't post this.
