Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of $[1,N]$ each time, I send you the identifier of a node. when you receive a sent node. you mark it and also invoke the following marking rule, which takes effect before I send out next node.

  • If a node and its sibling are marked, its parent is marked.
  • If a node and its parent are marked, the other sibling is marked.

The marking rule is applied recursively as much as possible before the next node is sent.

Process 1 : each unit of time, I send the identifier of a node chosen independently and uniformly at random from all of the N nodes.

Process 2: each unit of time I send the identifier of a node chosen uniformly at random from those nodes that I have not yet sent.

Process 3: each unit of time I send the identifier of a node chosen uniformly from those nodes that you have not yet marked.

  1. For the first process, prove that the expected number of nodes sent is $\Omega(N \log N)$
  2. For the second process, you should find that almost all $N$ nodes must be sent before the tree is marked. Show that , with a constant probability, at leas $N - 2 \sqrt N$ nodes must be sent.
  3. The behavior of the third process might seem a bit unusual. Explain it with a proof.

I need some hint how to proceed to analyze this process ??

  • 1
    $\begingroup$ This seems to be a programming question and so out of scope here. $\endgroup$ – Yuval Filmus Jan 13 '15 at 22:39
  • $\begingroup$ @YuvalFilmus I edited the question to suit this website. $\endgroup$ – Rathma Jan 14 '15 at 4:53
  • $\begingroup$ @HadiAmiri But there's no question in your... question. $\endgroup$ – nouney Jan 14 '15 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.