Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have a perfect binary tree on 2^k-1 nodes. Every node in the tree is marked with probability 1/2, and a node is either marked or unmarked. We want to find a marked node and return it. Our algorithm is as follows

procedure find(v);
 if (v is marked)
   print(v)
 else if (v is not a leaf)
   v1 is the left child of v
   v2 is the right child of v
   find(v1) ( recursive call )
   find(v2) ( recursive call )

So the algorithm basically starts from the top. Searches down the tree in a depth first fashion, and returns at least one marked node if there are any. Note that the algorithm can easily return multiple marked nodes.

Now what I want to do is to say something about the expected number of nodes the algorithm will consider on a random tree (1/2 probability of marking nodes), when the algorithm is run on the root of the tree.

share|improve this question
    
It's easier if we assume the tree has $2^k-1$ nodes, is that what you meant? –  Yuval Filmus Nov 9 '10 at 17:03
    
Of course, I will edit it. –  utdiscant Nov 9 '10 at 17:32
1  
A better algorithm will stop upon finding the first marked node. Make it into a function returning a Boolean value (found or not), and then only continue to find(v2) if find(v1) wasn't successful. –  Yuval Filmus Nov 9 '10 at 19:12
    
Exactly. For the purpose of this improvement/correction, you might consider a breadth-first traversal instead of recursion with bools passed around. –  Raphael Nov 10 '10 at 9:39

3 Answers 3

up vote 1 down vote accepted

Let's assume as Yuval suggests that 2^k - 1 nodes are meant.

We can get a recursive expression for the expected number of nodes N(k), where the basis case is N(1) = 1, i.e. that if we have one node, we have to visit it (whether or not it turns out to be marked).

If k > 1, then with probability 1/2 the top node or root of the binary tree will be marked, and thus only the top node will be visited. In the alternative we have to visit both left and right subtrees. Thus:

N(k+1) = 1/2 + (1/2)*[N(k) + N(k)] = 1/2 + N(k)

The solution of this recurrence relation + initial condition is simply:

N(k) = (k+1)/2

regardless of whether there are or are not marked nodes.

regards, hm

Correction: As Ross points out (see comment), the recurrence is N(k) = 1 + N(k), with solution N(k) = k, due to the fact that we will always visit the top node (before finding out whether it's marked).

share|improve this answer
    
It should be $N(k+1)=1/2+1/2*(2N(k)+1)$ as if the first node is not marked you still visited it. This is $N(k)=k$. It does depend upon marking-if the marking is probability p then $N(k+1)=p+(1-p)*(2N(k)+1)$ –  Ross Millikan Nov 9 '10 at 17:29

Assuming nodes are marked by independent coin flips, then the order that you visit nodes has no effect whatsoever. So the expected number of nodes visited is exactly the expected number of fair coin flips to get heads: 2.

share|improve this answer
    
Almost (there's a finite number of coins out there). –  Yuval Filmus Nov 9 '10 at 19:07
    
Plus, the algorithm doesn't stop "upon impact". –  Yuval Filmus Nov 9 '10 at 19:10

Idea: calculate recursively the expected number of nodes the algorithm visits on a complete binary tree of height $n$ assuming at least one node is marked. Note that this assumptions alters slightly the probabilities of relevant events.

EDIT: This idea only makes sense if you stop after the first marked node is found, in which case JeffE's solution is much much better.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.