Let G be a graph and u and v two vertices.
(1) Let H be a random graph where every edge of G is chosen with probability ½. Let p be the probability that there is a path between u and v in H.
(2) Let T be a random orientation of the graph G. Namely, every edge {x,y} is directed from x to y with probability ½ and otherwise it is directed from from y to x. Let q be the probability that there is a directed path from u to v in T.
What is the relation between p and q?
Test your intuition (1), test your intuition (2), test your intuition (3), answer to (3)–
Combinatorics and more 
Does q=2p?
I vote that the directed version is more likely to have a p-q path
I agree with daveagp.
My reasoning: if we define an event P_i for the existence of path i, then these events have the same probabilities in each model. But in the undirected model any two events that are correlated (when the paths share an edge) are positively correlated, whereas in the directed model some correlations can be negative (when the shared edge is used in opposite directions).
Of course, the expected number of paths is equal in both models…
In accordance with the David Exclusion Principle I change my vote to that they are equal
I reckon they’re the same.
Consider the set of all vertices we can reach along a path from u. We can build up that set recursively: start with just {u} and repeatedly add to the set all new vertices that we can reach from a vertex currently in the set.
As we run this procedure we are repeatedly examining edges between pairs of vertices x and y, where x is already in our set and y is not. The procedure basically runs the same in both models. Each edge we examine is useful to us (i.e. allows us to add the new vertex y to our set) with probability 1/2 (in the original model, the edge is useful when it exists, and in the oriented model it’s useful when it’s oriented the right way).
So it seems something stronger is true: the set of all vertices reachable from u has the same distribution in both models.
Consider the trivial graph with two vertices u and v. p = q in that case.
Wow, this is a great problem! Thanks!
consider the complete graph on two vertices. q=2p in that case. then consider a tree on three vertices. then q=2p again.
if you consider the graph as the lattice of subgroups of the klein viergruppe you get something more interesting like 7/8 and 37/64, but it’s still close. my guess is q \in [p,2p]
Don’t understand your last comment, dan. For the complete graph on two vertices, q=p=1/2 (assuming u and v are different vertices). There is only one edge to consider. To give a path from u to v: in case (1) the edge has to be chosen (which has probability 1/2) and in case (2) the edge has to be oriented from u to v (which has probability 1/2).
(3) Let graph K be a directed graph such that for every pair of vertices x != y, either there is a directed edge from x to y with probability 1/2 or directed edge from y to x with probability 1/2. Let r be the probability that there is a directed path from u to v in T. What is the relationship between p, q and r 😉
I think Dan may be thinking that a path from v to u is as good as a path from u to v.
Great problem. My first instinct was p ≤ q. My first argument would have shown q ≤ p. In the end, each at least was not wrong.
q < p
Intuition: p 3 must match one of 11***, **11*, 1**11, *11*0. Using exclusion-exclusion I got q=16/32.
So, unless I made a mistake when I was counting, in this case p>q. So much for my intuition.
WordPress ate my tags.
Intuition: p≤q.
But then I looked at 1a2, 2b3, 1c4, 4d3, 2e4. (1a2 means that edge “a” connect node 1 with node 2.) Subgraphs that have the path 1-3 must match one of 11***, **11*, 1**11, *11*1. Using inclusion-exclusion I got p=17/32. Orientations can also be represented with bitstrings (say 1=edge goes from low node to high node.) The orientations that have the path 1->3 must match one of: 11***, **11*, 1**11, *11*0. Using inclusion-exclusion I got q=16/32.
Again, unless I miscounted, in this case p>q.
not all orientations of all Gs which there is a path from v to u will have a directed path from u to v, therefore q<p.
not all orientations of all Gs which there is a path from v to u will have a directed path from v to u, therefore q<p.
As choosing the direction could block a path, I also vote they’re the same. This can be seen by restricting the path length to k = 1, 2, … edges.
Now that I know I miscounted it was fairly easy to do it right: p=q=1/2 in my example.