1
$\begingroup$

Suppose I have two different branching processes, which can be visualized as a tree.

Process A starts with a single node containing value 1, then at each recursive step, it splits into two nodes. Each node flips a coin, and with probability 1/2 the node's value is set to 0, otherwise it preserves the value of its parent.

Process B is similar, except that instead of two child nodes being created independently, only one node flips a coin, and the second node copies its value from the first.

At recursive step $k$ there are $2^k$ leaf nodes of this tree, and I am trying to figure out the expected number of those nodes which have value 1 for each process.

I figure that for Process A, the expected value should be 1, since the probability that a leaf node still has value 1 is simply $(1/2)^{k}$.

Intuitively, I think the expected value for Process B should be smaller, and in addition the assignment that I am doing right now asks me to show that it is smaller. But I have calculated the expected value via brute force for $k = 2, 3, 4$ and am getting the same result (1).

e.g., when $k = 2$, with probability 1/2 there will be 0 leaf nodes with a 1, and with probability 1/2 there will be 2 leaf nodes with a 1, leading to an expected value of 1. When $k = 3$, with probability 1/2 there will be 0 leaf nodes with a 1, and with probability 1/2 there will be 2 child nodes which branch to produce an expected 1 leaf still containing 1, for a total expected value of 1.

Am I doing something wrong here? Or am I being asked to prove something that is wrong?

$\endgroup$
1
  • $\begingroup$ I would expect the two processes to have the same expected value, but process B to have a greater variance for the number of leaf nodes with value $1$ $\endgroup$
    – Henry
    Sep 16, 2015 at 7:12

1 Answer 1

0
$\begingroup$

To rephrase: the first process has each node bearing one child with probability 1/2 or two children with probability 1/4, then dying. The second process has each node bearing two children with probability 1/2, then dying.

The expected number of children of each individual is 1 in each case. The expected size of the $n$th generation is $\mu^n$ where $\mu$ is the expected number of children of each individual. Therefore, the expected size is 1 at each generation.

The variance is $n \sigma^2$ where $\sigma^2$ is the variance of the offspring distribution - that is, $(1/2 + 1) - 1 = 1/2$ in the first case, or $2-1$ = 1 in the second case. Therefore the variance is $\frac{1}{2} n$ vs $n$ in the two cases.

You're being asked to prove something wrong.

$\endgroup$

Your Answer

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

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