Gary2005's blog

A strange probability and graph problem
By Gary2005, history, 4 years ago, In English

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?

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by Gary2005 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)$$$

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But how to deal with this case:

        a->b->c->d->e->f->g ,where (a,c,e,g $$$\in A$$$,others $$$\in B$$$)

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think Gaussian elimination will be helpful here
https://codeforces.me/blog/entry/60003
See the Markov chain and cyclic expected value.

→ Reply