# If we choose a line segment at random, then what is the expected number of paths that pass through it?

I was trying to solve this question. To find the expected number of paths that pass through a randomly chosen line segment:

I observed that for different line segments the probability is different. Do we need to find the probabaility for each line segment and then add them to find the expectation?

Source: AOPS.

• You can use linearity of expectation. The expected number of paths through your edge is the sum over all paths of the expected number of times the specific path goes through your edge and this number is independent of the specific edge. Commented Jul 24 at 7:49

## 2 Answers

That would be one way to do it. However, there is a simpler way.

Suppose I am thinking of a specific path, and you choose a random edge. What is the probability that you chose an edge on my path? Note that this doesn't depend on which path I chose (why?), so you can just multiply by the total number of paths to get the expected number that meet the random edge.

• What is the probability that you chose an edge on my path? $= 5/17$ Commented Jul 24 at 11:08

We have to go three segments to the right and two segments upwards, therefore in each path, we pass through $$5$$ segments. Our path is uniquely defined by the order of the different segments, so out of the $$5$$ positions (segments) we can choose $$2$$ to be the ones where we walk upwards, therefore, the total number of paths is $$5 \choose 2$$ which equals $$5!/[(5-2)!2!]=5!/(3!2!)=5 \times 4/2=10$$ different paths. For $$17$$ segments and $$10$$ unique paths times $$5$$ segments per path we get that $$50/17=2.94$$ is the number of times each segment is passed through on average in this case.