GATE CSE 2019 | Question: 46

@vaishnavi30

In Probability, events can be dependent or independent of other events.

Let's say tossing a coin two times, the probability of getting heads in either trial is 1/2. This is an independent event, where the outcome of the next trial is not dependent on the previous. 

Now take an example of 2 balls (one red, one blue). The probability of getting blue in the first pick is 1/2 and the second pick would be 1 (since red was picked last time and only blue remains). These are dependent events where the probabilities change depending on the previous outcome.

Back to this question, when it says independent choosing - for choosing two nodes and finding their distance, we could pick any node as the first (1/8 probability) and the second node as we may think would be (1/7) since we have already picked the first but that's just dependent choosing and not what the question is asking. When we consider independent choosing, we can pick the first node again as the second node as well, therefore probabilities remain the same (1/8 => for both). 

Hope this helps

That’s almost  exactly how i did. However i missed the word INDEPENDENT and ended up dividing by 7 instead of 8.

Apparently, the guy was EVIL.

A great explanation, but at the last point  it is (1/8) * {0+2+4+4+6+6+6+6}

@Kriti. 1212 Actually we need to multiply 1/8 only for first leaf because we are just choosing the first leaf randomly. The other leaf is not “random”. We actually pick all of the other leaves one by one and add their distances from our first leaf.

Simpler way:-

Expectation :-

Now here the $p_i = 1/8$ which is getting multiplied every time. Thus we can take $1/8$ as common.

Easy Way:

[Img credit: @arjuno.]

Total Path distances from $1$ leaf [say $H$] to all other leaves (incld. itself) = $2 + 4*2 + 6*4 = 2+8+24 = 34$

Since there are $8$ leaves, hence probability of picking anyone = $1/8$

Thus E(x) = $1/8 * 34 = 4.25$

I am sorry, but i checked your references now. I don't think this makes much sense:

2. Graph theory by Frank Harary.

https://shyam.nitk.ac.in/Books/GT%20Books/Harary.pdf page 13

On the next page, page 14, it mentions :

Also,

3. mit book on discrete maths

https://courses.csail.mit.edu/6.042/spring17/mcs.pdf page 384-385, 

On page 385, it mentions :

@Arjun Sir, might it be the case, that the term independent is used to imply that, given a selection of node, post selection, the selection of the next node has nothing to do with the sub-tree from which the earlier node is chosen?