Suppose we have a directed graph $G$ with $n$ nodes. Suppose that the probability of an edge from node $i$ to node $j$ is $\pi_{ij}$.

Probability distributions must must assign probability 1 to the entire sample space, but what is the relevant probability distribution/sample space here?

Is there a probability distribution for any two nodes? Or perhaps two probability distributions for any two nodes (one for each direction)? And then each probability distribution has two events: there is a directed edge; there isn't a directed edge?

Or is there perhaps a probability distribution over all nodes? If this is the case, then what probabilities must sum to 1? Would it be $$\sum_i\sum_j \pi_{ij}$$ where $i,j$ are nodes?

Or is the probability distribution something else I have not mentioned?


One way to think of this: for each pair of nodes, flip an independent coin which has heads probability $\pi_{ij}$. Then put an edge if the coin came up heads. Thus your question reduces to understanding the probability space underlying a coin flip experiment, which you can find in any just about any probability textbook. I would start by making sure you understand that construction.

There is one distribution for each ordered pair of nodes. Under the assumption that they are independent, we can 'product' them and get a distribution on the space of directed graphs. This is analogous to how we have one distribution for each coin flip, and (under independence assumption) product them to get a distribution on sequences of coin flips.

  • $\begingroup$ But when they are not independent things can get messy? (messy=tedious) $\endgroup$ – user106860 May 2 '18 at 2:54
  • 1
    $\begingroup$ @user106860 when things are not independent you need more information to specify the distribution. For example, there are exponentially many 2^n sequences of coin flips, but n coordinates. Specifying the distribution by requiring Independence and then telling you about each coordinate takes many fewer bits than telling you the entire joint distribution. There are other assumptions people can make , but independent is definitely the simplest. $\endgroup$ – Lorenzo Najt May 2 '18 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.