in DS retagged by
30,270 views
71 votes
71 votes
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) _________.
in DS retagged by
by
30.3k views

4 Comments

One of the toughest and trickiest questions in gate 2019
4
4

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

 

8
8
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...
0
0

9 Answers

132 votes
132 votes
Best answer

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$

edited by
by

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

 

2
2
@KUSHAGRA nice answer
0
0

@KUSHAGRA

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

0
0
152 votes
152 votes

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$

edited by

4 Comments

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?
0
0
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]
0
0

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

6
6
11 votes
11 votes

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

 

 

edited by

2 Comments

This seems legit. You should definitely challenge.
2
2

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 :

 

6
6
7 votes
7 votes
Ans should be 4.25,Becoz path length 0 is also possible as it is not said "distinct leafs"
edited by

4 Comments

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

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

1
1
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".
0
0
Answer:

Related questions