Conference rusure::math

I've often thought about this sort of thing on the mass pike.

Say 5 cars come through the toll booth simultaneously, from 5 separate
lanes.

Now all 5 cars are on the mass pike, in some random order from front
to back.

If each has a slightly different desired driving speed, various passes
will occur until the fastest is in front, and the slowest in back.

What's the expected number of passes ?  (or something like that)

For any pair of cars i and j, there is an expected number of passes of 1/2: of
all the permutations of n cars, n!/2 have the faster of i and j starting in
front (0 passes), the rest have the faster starting in back (1 pass).

So the expected number of total passes is n(n-1)/4.

    The probability that AT LEAST k tasks out of n execute is
    
    	1/k!
    
    So the probability that EXACTLY k tasks out of n execute is
    
    	1/k! - 1/(k+1)!             (for k < n)
    	1/n!			    (for k = n)
    
    The expected number of tasks that complete is easily seen to be:
    
    	sum(k=1...n) 1/k! [consecutive terms nearly cancel.]
    
    which converges to e-1. [see Taylor's series for e^x.]
    
    Cheers,
    Andrew.
                                             

The messages .3 and .4 gave different sums (one starting at 0, the other at 1). 
I assume the second one supersedes the first.

                                         2
In any case, my sum was sum(k in 1..n-1)k /(k+1)! + 1/(n-1)! for the expected
number of executed tasks.  How did you get the simpler sum in .4?  (The
probabilities are correct.)

I withdraw the question... you are using a special case of the identity

 [sum(k in 1..n-1) k(a -a   )] + na = sum(k in 1..n) a  .
                      k  k+1       n                  k

Yes, the limit is e-1, which turned out to be a pretty close estimate of the
actual performance of the customer's program (I believe the actual number, with
n=4, was about 1.8).  Of course, the actual scheduling behavior wasn't random;
but the problem was that the initial application had run on a VAX where the Ada
scheduler (in effect) just happened to always order the tasks 1..n.  When it was
ported to Alpha Ada, the task ordering was determined by DECthreads, and was
more haphazard; the net effect was a slowdown by a factor of n/1.8 which was
only partly offset by the Alpha's better speed.  The customer was naturally
upset (though no blame could reasonably be laid on Digital), but some simple
re-engineering of the customer's application fixed the matter and made the Alpha
application run faster as expected.

Given
    	1/k! - 1/(k+1)!             (for k < n)
    	1/n!			    (for k = n)

then the sum is

	sum(k=0..n-1) [k/k! - k/(k+1)!]  + 1/n!

One way to go from here is to combine the term in brackets:

	k(k+1)! - k(k!)     k(k+1)k! - k(k!)      k+1
	---------------  =  ----------------  =  ------  = 1/k!
	    k!(k+1)!            k!(k+1)!         (k+1)!

-- but the second step involves division by zero when k=0.
Fortunately, the whole term in brackets is zero for k=0.
So the final result is

	sum(k=1..n-1) 1/k!  + 1/n!

which is simply

	sum(k=1..n) 1/k!

When I do the third step (after the second "=" on the last line) I don't get
k+1, but rather k*k.  (Also, there's no division by zero, because 0! = 1.)  That
is, the numerator should be k(k+1) - k = k*k + k - k.  I think some sort of
rearrangement or telescoping is needed to get the simpler form.

Oops -- I'm all wet.

From:	TPSYS::TREHAN "TP Arch, Standards, & Strategy  04-May-1995 0917"  I did
not solve for the expected number of tasks that will execute because I 
am getting very different vaules for the probabilities for m (of the n) tasks
executing than the previous replies. What is wrong with this logic???


	Task schedule for m tasks to execute must look like:

		 1,2,3,...m, (not m+1),....n


	Number of ways to achieve this schedule: 

		= {# of ways to schedule the remaining m+1, m+2,... tasks 
		   so (m+1) is not first}


		= (n-m)! - (n-m-1)!  for m < n
		
		  or	  1	     for m = n


	Probability that exactly m tasks will execute:

		  (n-m)! - (n-m-1)! 
		= -----------------  for m < n
			n!
			
		  or    1/n!	     for m = n		


Example m=5, n=2

	Of all the 5! different schedules only the following will result in
	in exactly 2 tasks executing

		1,2,4,3,5
		1,2,4,5,3
		1,2,5,3,4
		1,2,5,4,3

	(5-2)! - (5-2-1)! = 3! - 2! = 6 - 2 = 4

>	Task schedule for m tasks to execute must look like:
>
>		 1,2,3,...m, (not m+1),....n


Why do you say that the above is a schedule for m tasks to execute ?

If we write the above in a bit more detail, it might look like this:

		1,2,3,...m, m+2, m+1, ....n

From this detail, we can see that, although m+2 isn't allowed to execute,
m+1 is, and hence the what you originally claimed is a schedule for m tasks
has been shown to be a schedule of at least m+1 tasks executing.

/Eric

> Suppose there are n tasks numbered 1 to n, each of which (other than task 1) can
> only be done if the preceding one has already executed.  Say we put the tasks in
> random order, and then proceed once through from left to right executing each
> task if and only if it is executable (by virtue of its predecessor task having
> been executed).


The above is the wording of the original problem.  I just realized
that it is ambiguous.  Suppose we have tasks arranged like this:

	1, 3, 2 ...

Do we *allow* task 2 to execute because it's predecessor (in order of labels)
is "1" which as already executed ?

Or do we *disallow* task 2 to execute because it's predecessor (looking from
left to right) is "3" which didn't run ?

/Eric

The intent was that the task numbered n was allowed to execute iff the task
numbered n-1 had executed.  That is, the first statement in the paragraph is
interpreted before the second statement is.  This removes the ambiguity, but I
can see that the wording isn't best.

WRT the probabilities in .10: they don't sum to 1 for n=2 or 3, so there must be
some missing orderings of tasks.  Thus, for n=3:

  m=3: 1/3! = 1/6
  m=2: (1!-0!)/3! = 0
  m=1: (2!-1!)/3! = 1/6

which sums to 1/3.  Similarly, for n=2:

  m=2: 1/2! = 1/2
  m=1: (1!-0!)/2! = 0

which sums to 1/2.

>> See corrections to .10 below

>> This solution assumes that the m must be ""immediately"" preceded by (m-1)
>> (for m=1,2,...n) in order to execute

I did not solve for the expected number of tasks that will execute because I 
am getting very different vaules for the probabilities for m (of the n) tasks
executing. What is wrong with this logic???


	Task schedule for m tasks to execute must look like:

		 1,2,3,...m, (not m+1),....n


	Number of ways to achieve this schedule: 

		= {# of ways to schedule the remaining m+1, m+2,... tasks 
		   so (m+1) is not first}


		= (n-m)! - (n-m-1)!  for m < n-1
>>
>>		  or      0	     for m = n-1
>>		
		  or	  1	     for m = n


	Probability that exactly m tasks will execute:

		  (n-m)! - (n-m-1)! 
		= -----------------  for m < n-1
			n!
>>			
>>		  or    0	     for m = n-1
>>
		  or    1/n!	     for m = n		


>> Example m=3
>>
>>	1,2,3	3 tasks execute
>>	1,3,2	1 tasks execute
>>	2,1,3	0 tasks execute
>>	2,3,1	0 tasks execute
>>	3,1,2	0 tasks execute
>>	3,2,1	0 tasks execute
>>
>>	p0 = 3!-2!/3! = 2/3
>>	p1 = 2!-1!/3! = 1/6
>>	p2 = 0
>>	p3 = 1/6
>>
>>	p0+p1+p2+p3 = 1

>> Example m=5
>>
>>	p0 = 5!-4!/5! = 96/120 
>>	p1 = 4!-3!/5! = 18/120
>>	p2 = 3!-2!/5! = 4/120
>>	p3 = 2!-1!/5! = 1/120
>>	p4 = 0
>>	p5 = 1/120
>>
>>	p0+p1+p2+p3+p4+p5 = 1

I see now that your probabilities do sum to 1, because you have an m=0 term that
isn't present with my assumptions.  (A case where no tasks execute.)

You are assuming that task 1 executes only if it occurs first.  Although my
problem statement was arguably foggy, I did say in problem 1 that "task 1 will
always execute."

For example, with n=3 and the tasks in order 2,1,3, your counting does not
include this for m>0 (so I assume you have 0 tasks executing) but under my
assumptions task 1 would execute.

With this and using your dependence rule, you would want to count all tasks
which occur in the patterns

  xxx 123...m (not m+1) xxx  -or-  xxx 123...m.

Now that we have a common understanding of the problem here is another 
shot at updating .10/.14

	(i)   This solution assumes that task m must be ""immediately"" 
	      preceded by (m-1) in order to execute

	(ii)  All schedules that look like -----,1,2,...m, (not m+1), -----
	      will execute exactly m tasks


	Number of ways to schedule n tasks so [1,2,3,...m] stay
	together

		= (n-m+1)! 

	Number of ways to schedule n tasks so [1,2,3,...m, m+1] stay
	together

		= (n-m)!
	
	Number of ways to schedule tasks so exactly m tasks will execute 

		= (n-m+1)! - (n-m)!	for m = {1,2,...,n-2}

		  1			for m = {n-1, n}


	Probability that exactly m tasks will execute:

		  (n-m+1)! - (n-m)! 
		= -----------------  for m = {1,2,...,n-2}
			n!

		  1/n!		     for m = {n-1,n}

	
	..............................................................

	Example m=5

	p1 = 5!-4!/5! = 96/120
	p2 = 4!-3!/5! = 18/120
	p3 = 3!-2!/5! = 4/120
	p4 = 1/120
	p5 = 1/120

	p0+p1+p2+p3+p4+p5 = 1

Based on .16 the expected number of tasks that will execute

	En 	= 1*p1 + 2*p2 + 3*p3 + ... + n*pn
	
		  1*[n!-(n-1)!] +  2*[(n-1)!-(n-2)!] + ....	
		= ------------------------------------------ 
					n!	

			n! + (n-1)! + (n-2)! + ......
		= -----------------------------------------
				n!

		      1     1         1
		= 1 + - + ------- + ------------- + ......
		      n   n*(n-1)   n*(n-1)*(n-2)

Let S(n) be the sum indicated.  Then S(n) = 1 + S(n-1)/n, and S(1) = 1; by
induction, we can verify S(n) <= 1 + 2/n, since this holds for n=1 or 2, and if
n>2

  S(n) <= 1 + (1+2/(n-1))/n = 1 + 1/n + 2/(n(n-1)) <= 1 + 1/n + 1/n

So it holds for all n; and S(n)>=1 always, so S(n) -> 1.