### Gary2005's blog

By Gary2005, history, 3 years ago, There is a graph with n nodes.The edges are generated with different probabilities.

P[i][j] is the probability of generating the edge i->j .

For every i, you want to know the probability that the first node can go to the i-th node through the generated edges .

n<=80

I don't know how to solve it ,can you help me?  Comments (9)
 » Auto comment: topic has been updated by Gary2005 (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   Divide the vertices in two set A,B each having $\dfrac{n}{2}$ vertices. For each Set, you separetely calculate the answer, let $f(S)$ return the probability matrix for vertices in $S$.Now, to combine the answer, you can iterate over the path $a\rightarrow b\rightarrow c\rightarrow d$ where $a,b,c,d \in A,B$ and not all of them belong in the same set. This will be $f(A)[a][b] \times P[b][c] \times f(B)[c][d]$.The overall complexity should be $\mathcal{O}(n^4\log n)$
•  » » I don't think it is right:For example ,$a,b,d\in A$and $c\in B$,you can also go through this path a->b->c->d .
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Hmm, You're right. We can add that case also.For the tuple $(a,b,c,d)$ we can find all cases such that each vertex is in $A$ or $B$ and not all of them belong in the same set. There are $14$ such cases, so the overall complexity still holds.Thanks for pointing that out though. Updated.
•  » » » » But how to deal with this case:a->b->c->d->e->f->g ,where (a,c,e,g $\in A$,others $\in B$)
 » 3 years ago, # | ← Rev. 2 →   I think Gaussian elimination will be helpful here https://codeforces.com/blog/entry/60003 See the Markov chain and cyclic expected value.
•  » » I have ever thought of this.But it can't work
•  » » » Here it is mentioned that exact probability cannot be solved in polynomial time. https://math.stackexchange.com/questions/1678084/probability-u-v-are-connected-in-a-random-graph-model But you can calculate upper bound and lower bound on probability
•  » » Bruh this is amazing. There are many problems of cyclic expected value(I didn't know they were called as such) that I have solved with an equation system but don't know why the solution is correct. Gonna go read about them brb. Thank you!