GATE CSE 2019 | Question: 46

Question

Let $T$ be a full binary tree with $8$ leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. The expected value of the distance between $a$ and $b$ in $T$ (ie., the number of edges in the unique path between $a$ and $b$) is (rounded off to $2$ decimal places) _________.

Comments

One of the toughest and trickiest questions in gate 2019

---

One silly question is why the total number of alternative paths is 8^2, rather than 2^8.

It's similar to n places with the m option → n^m

that is 8 places with 2 option → 8^2

 

---

Question Says total 8 leaves ,

1.) First choose any 2 leaves independently and Uniformly=(1/8)*(1/8)=1/64.

2.) Use logic of Expectation.

{1/64 (2+4+4+6+6+6+6+4+4+6+6+6+6+2+6+6+6+6+6+6+6+6+2+4+4+4+4+2)}*2 (Multiply 2 because Node a and b can be swapped also so Total 2! ways.

2.125*2=4.25...

Answer 1

Two leaves a and b of T are chosen uniformly and independently at random.

See the word "independently" here. It means that choice of $a$ must not affect choice of $b$ and vice versa. This implies that both $a$ and $b$ can even be the same node.

Now, we are given that the binary tree has $8$ leaves. $\left(2^3 = 8\right) \implies$ we have $3$ levels in the tree starting from $0.$ The distance in terms of number of edges between any two leaf nodes will always be even. If we consider any two leaves (not necessarily distinct)

• No. of pairs with path length $0 = 8.$ (When $a = b)$
• No. of pairs with path length $2 = 8.$ (For each of the $8$ leaf nodes, we have a pair and since the selection is independent order of the pair is also significant)
• No. of pairs with path length $4 = 16.$ (For each leaf node we have to go two levels up and while coming down we have $2$ choices. So, we get $8 \times 2 = 16$ pairs)
• No. of pairs with path length $6 = 32.$ (For each leaf node we have to go till the root, and from there while coming down it has $2 \times 2 = 4$ choices. Thus we get $8 \times 4 = 32 $ pairs.

Total number of possible pairs $ = 8 \times 8 = 64$

So, expected path length

$\quad =0 \times \frac{8}{64}  + 2 \times \frac{8}{64}+4 \times \frac{16}{64}+6 \times \frac{32}{64}= \frac{272}{64}=4.25$

Comments

@Arjun

Sir what will be the case when a and b are dependent. I understand that in this case total number of possible pairs will be 8 X 7 = 56, and there will be no case of path length 0.

But will it affect other cases like pairs of path length 2, 4 and 6. Is there any changes in that?

 

---

@KUSHAGRA nice answer

---

@KUSHAGRA

you just clear all my doubts. thanks for the amazing visualization….

Answer 2

A full binary tree of $8$ leaves

Let's say we take node $H.$ The distances from $H$ to all other nodes (including itself) would be:

$\begin{array}{|c|c|c|c|c|c|c|c|}\hline
H&I&J&K&L&M&N&O\\\hline
0&2&4&4&6&6&6&6\\\hline
\end{array}$

If another node is taken, a similar table (to the one above) is attained. Therefore, all nodes have the same distances when added together. 

So, if a node is considered, the probability of choosing another node would be $1/8$ (including itself - independent choosing]. 

Therefore, $E = \frac{1}{8} \left[0+2+4+4+6+6+6+6\right] = 4.25$

Comments

precise basic answer. Thanks.

---

Thank you for your effort in drawing diagram and creating most simple and straighforward answer

---

One picture/figure remove all difficulties. Great explanation.

---

What does independently means?plz explain

---

@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

---

Yes, I got it.

Thanks for explanation

---

jiko:)

---

this should be made as the best answer.

---

Correct me if i am wrong

---

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}

---

BEST EXPLANATION :)

---

Sir,here in 0+2+4+4+6+6+6+6 ,here do you mean + is like or?

Like if we select I then dist is 2 or if we select J,dist is 4 or if we select M,dist is 6...and choosing one from these 8 is 1/8 probability..Am i correct?

---

I guess what you have thought is right. But, I have a doubt : we should have taken 1/8 one more time for the selection of first node i. e.  a  and after that 1/8 once more for selection of node b. So the final answer should have been 1/8 * 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$

Answer 3

Path can only have distinct vertices. If two leaves are same , path cannot be defined between them. distance(a,b) is not defined if a and b are same vertex.

This answer is according to definition of path given in two books which I came across:

1. Anaytics combinatorics by Alan Tucker

http://noahc.me/Applied%20Combinatorics%206th%20edition.pdf

page 4

2. Graph theory by Frank Harary.

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

3. mit book on discrete maths

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

see the comment below by ahabnnc

 

 

Comments

This seems legit. You should definitely challenge.

---

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 :

 

Answer 4

Ans should be 4.25,Becoz path length 0 is also possible as it is not said "distinct leafs"

Comments

But that way, we end up having two names for one node! That is contradictory.

---

@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?

---

I think "Independent" only means that the "order of selection" is irrelevant. That is, we need to take into consideration only the "combination" and not the "permutation".