1
$\begingroup$

We start with an arbitrary length string say 'n'. Now we follow a binary tree which has following property:

  1. At first level:

    (i). Starting character from the string is selected (and removed) and it represents the left branch of the binary tree.

    (ii). Ending character from the string is selected (and removed) and it represents the right branch of the binary tree.

  2. At second level:

    (i). Starting character from the string is discarded (and removed) and it represents the left branch of the binary tree.

    (ii). Ending character from the string is discarded (and removed) and it represents the right branch of the binary tree.

Above two steps alternate until the string becomes completely empty. So from root to every leaf node, we'll have a path where some characters are selected or discarded. All selected characters in the path, appear in the output at leaf.

We need to calculate the probability of every character with which it'll appear in the output.

My approach:

First character will be selected on the root as left subtree, so all the children below it will have the first character which makes its probability 1/2 for left subtree, whereas when we proceed in right subtree, it'll not be discarded in the right subtree of it. Now again this will be selected as the next left subtree but since we have come down by 2 levels, number of times of appearance in output has reduced by 4 folds. And from here the probability will be $1/8$ and so on... At the end I'm adding all those probabilities so it comes as:

$1/2 + 1/8 + 1/32 + ... $ But I'm stuck after finding the first character's probability. How to go about the second character and so on. I think I'm in wrong direction.

Please help me with this approach or any new approach which would work in this case.

  • 0
    @joriki Ok sir. I agree its a similar questio$n$. I di$n$'t find that question before posting this otherwise could have participated there. Thank you for pointing me to that link. You can mark this question as duplicate and I'll participate on that link. Thank you so much :)2012-10-14

0 Answers 0