Conference rusure::math

There does not appear to be any way (from .0) of predicting the structure 
of the tree; a tree consisting only of a root and n-1 children is equally
likely as a tree in which each node except the last has exactly one child.
In the first case you can only kill one child at a time, so the average is
O(n) kills; in the latter case you expect to kill n/2 children each time,
which takes O(log(n)) kills on average. So the calculation depends very
strongly on the likelihood of different structures. 

    Re .1:
    
    I am looking for an expression of the mean number of kills as a
    function of the tree (or some subset of its properties).
    
    By the way, the mean for a tree with a root and n-1 children is
    (n+1)/2.
    
    
    				-- edp

    0:  Any node can be deleted by killing either that node, or any
    	of its ancestors.
    
    1:  The Root Node can only be deleted by killing the root node.
    
    .:	If you have no nodes left, then you must have killed the Root
    	node at some point.
    
    2:  Killing the Root node at any time will delete all remaining nodes.
    
    .:  If you have killed the Root node then you have no nodes left.
    
    .:  All nodes are deleted, when and only when the Root node is deleted.

        
	....  now I am stuck.  Oh well, back to work...
    
    --  Barry

    Given the number of nodes, you can get a random tree by considering
    each possible distinct configuration as being equally probable.

    However, there's the question of whether the ordering of siblings
    is important.  For example, are these two trees considered different?

		  X		  X
		 /|\		 /|\
		X X X		X X X
		    |		  |
		    X		  X

    Re .4:
    
    The question is not what is the mean for a randomly-selected tree of
    some size, but what is the mean for each particular tree. 
    
    
    				-- edp 

    How should we characterize a tree arithmeticaly?
    
    --  Barry

    Re .6:
    
    I am not sure why you are asking, but do not worry about writing the
    function formally.  Just explain how to look at a tree and find the
    mean number of kills required.  It turns out to be very simple.
    
    
    				-- edp 

    Well, here's an analysis for two simple 'trees'.


    Consider a tree formed by a single root and n-1 children.  The expected
    number of kills for this n-node tree is:

	E(1) = 1
	E(n) = 1/n + (n-1)/n * (1 + E(n-1)) = 1 + (n-1)/n * E(n-1)

    As per Eric's suggestion, we conjecture that E(n) = (n+1)/2, and
    prove this by induction.  It's true for E(1), and for E(n) we have:
    E(n) = 1 + (n-1)/n * E(n-1) = 1 + (n-1)/n * n/2 = 1 + (n-1)/2 = (n+1)/2.


    Consider an n-node tree with each node but one having a single child
    (i.e., it looks like a list).  The expected number of kills is:

	E(1) = 1
		     n-1			n-1
	E(n) = 1/n + Sum (1+E(i))/n = 1 + 1/n * Sum E(i)
		     i=1			i=1

    The first few values are:

	E(1) = 1
	E(2) = 3/2
	E(3) = 11/6
	E(4) = 25/12
	E(5) = 137/60
	E(6) = 49/20
	E(7) = 363/140
	E(8) = 761/280


    In general, the expected number of kills for a tree T is:

			 n-1
	E(T) = 1 + 1/n * Sum E(T with node i and its descendants killed)
			 i=1

    But surely Eric is looking for something more than a restatement
    of the definition of the expectation.

Isn't the question when the last process is killed?  And isn't that coincident
with the killing of the root process?  And isn't that, for an n-node tree:

	1, 2, 3, ..., or n, all equally likely

?  And isn't the answer

	1/n * (1 + 2 + 3 + ... + n)  =  1/n * (n * (n+1) / 2)  =  (n+1) / 2

John

>...And isn't the answer

	1/n * (1 + 2 + 3 + ... + n)  =  1/n * (n * (n+1) / 2)  =  (n+1) / 2

No, if the tree is vertical with no siblings at any level, it is log[2](n).
You get to ignore parts of the tree that get pruned away, which in this 
case averages to half the tree with each hack.

    Re .9 & .10:  yes, thank you.
    
    John

The expected number of process kills is the sum of the reciprocals of the
depths of the nodes (starting at 1).  E.g. for a very flat tree, it's

	(n+1)/2 = 1 + 1/2 + 1/2 + ... + 1/2

and for a vertical tree, it's

	1 + 1/2 + 1/3 + ... + 1/n

Proof:  Suppose it's true for any tree with n nodes or fewer (it is true
for n = 1); try to demonstrate truth for n+1.

Consider a node N at maximum depth d (in the n+1-tree T').  Call the nodes
above it in the tree 1, 2, ..., d-1.  Call the other nodes in the tree
d, d+1, ..., n.  Let

	T	= n-tree which is T' with N removed
	E	= expected # of kills for T
	E'	= expected # of kills for T'
	F(j)	= expected # of kills for T with node j removed
	F'(j)	= expected # of kills for T' with node j removed

Then

	E	= 1  +  1/n * Sum (1 to n) of F(j)
	E'	= 1  +  1/(n+1) * E  +  1/(n+1) * Sum (1 to n) of F'(j)
			^^^^^^^^^^^
		       (N picked 1st)
    		= 1  +  1/(n+1) * E  +  1/(n+1) * Sum (1 to d-1) of F'(j)
			+  1/(n+1) * Sum (d to n) of F'(j)
		= 1  +  1/(n+1) * E  +  1/(n+1) * Sum (1 to d-1) of F(j)
			+  1/(n+1) * Sum (d to n) of F'(j)
[reason:  if an ancestor node to N is picked first, N is irrelevant]
		= 1  +  1/(n+1) * E  +  1/(n+1) * Sum (1 to d-1) of F(j)
			+  1/(n+1) * Sum (d to n) of [F(j)  +  1/d]
[reason:  induction for trees that are n-nodes or smaller]
		= 1  +  1/(n+1) * E  +  1/(n+1) * Sum (1 to n) of F(j)
			+  1/(n+1) * (n-d+1) * 1/d
[rearranging]
		= 1  +  1/(n+1) * E  +  1/(n+1) * n * (E-1)
			+  1/(n+1) * (n-d+1) * 1/d
[using the formula for E, above]
		= 1  +  E  -  n/(n+1)  +  1/d  -  1/(n+1)
[rearranging]
		= E  +  1/d
	and that's truth for T'

John

    Re .12:
    
    You got it, good work!
    
    
    				-- edp

    I give up.  How did you stumble onto this neat little problem?

    Re .14:
    
    Well, I was in high school, and I took Computer Math and Data
    Processing III and then just hung around the computer room all the time
    because there were not any higher courses, and eventually I got the PH
    (process handling) privilege for my account, and I experimented, and,
    wow, look at all those neat processes, I wonder how I get rid of them?
    
    
    				-- edp