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
    You can't calculate a probability because you haven't introduced any random events. I presume you forgot to say that you descend this tree, choosing the left or right branch with equal probabilities at each level?2012-10-14
  • 1
    The desired probabilities are the constants $c_{n,k}$ in Hagen's answer.2012-10-14
  • 0
    @joriki Yes you are right. At every node left or right is chosen with equal probabilities. In other words: When we are moving from top to bottom, every character which is selected appears in all the leafs in its below subtree. So, here I define the probability of a character as: number of leafs at which it appear divided by total number of leaves.2012-10-14
  • 0
    @joriki Thank You for the link. Its is a similar problem. Clearly C(n,k) is the probability as its sum over multiplication with the corresponding value gives the Expectation. But the calculation of C(n,k) is not comprehensive to me. Can you please elaborate it a little. Thanks in advance. :)2012-10-14
  • 1
    I don't know what you mean by "not comprehensive". I tried simplifying the expression in Hagen's answer but failed. Please note that whether this question is a duplicate of another question doesn't depend on whether the other question has been fully answered; only on whether everything that's being asked here is also asked there.2012-10-14
  • 0
    @joriki Ok sir. I agree its a similar question. I din'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