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.
- For the first process, prove that the expected number of nodes sent is $\Omega(N \log N)$
- 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.
- 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 ??