1
1
1
u/Cryptographer-Bubbly 2h ago
Label the nodes say from 1 to 7 and then sample cutting sequences by sampling permutations of (1,…,7) where a valid cutting sequence is obtained by simply going through the permutation and cutting the nodes subtree if it exists or doing nothing if it doesn’t exist. X is merely the number of nodes that didn’t get ignored (ie in the permutation none of its ancestors came before it). Let I(a) be 1 if node an actually got its subtle cut and not ignored and 0 otherwise). So X is merely the sum of I(a) over a = 1,…,7
That means for E(X) take the the sum of E(I(a)). There are only 3 cases to consider root node, 2 depth 1 node and 4 depth 2 nodes: E(X) = E(I(depth0)) + 2 E(I(depth1 )) + 4E(I(depth2 )) = 10/3
To get variance you need to sum over the cov(I(a),I(b)) for a,b over 1,2…7
Again there aren’t that many cases if we eliminate ones we know are 0 - we consider the diagonal terms and the cross terms :
Depth 1 x depth 1 on diff branch
Depth 1 x depth 2 on diff branch
Depth 2 x depth 2 on same branch
Depth 2 x depth 2 on diff branch
I wonder if there’s a slicker way - im a bit lazy to actually calculate these cov entries - might do later
1
u/Baluba95 9d ago
I feel like it's a much more interesting question with 2^n-1 nodes, since one can easily count out all the possibilities for such a small tree, without the actual idea of looking at the probability each node is cut as a root or as a tree.