Conference rusure::math

To clarify the problem some more, here is a picture showing one configuration -

T = 5
D = 2
N = 3

One combination - 

	1	2	3	4	5
User 1          +----------------+
User 2  +---------------+
User 3                  +----------------+

Thus, at

K = 1, no overlaps occur
K = 2, 2 overlaps occur
K = 3, 2 overlaps occur (User 2's operation ends before K = 3)

bc


Here are some ideas:

a) I assume you intend that N and D are not randomly chosen, but that you
   treat them as constants in each particular problem.
   
b) "numops" is a significant parameter that you underemphasize when you 
   give it a lower case name.  Let us call it "M".
   
d) The equal probability assumption and the limited number of operations in
   any period may turn out to be mutually inconsistent.
   
      I suggest we replace the former with an assumption like:
      
   The probability that any user starts an operation at time K depends only
   on the number of operations already started (M-X).
   
We still need to specify _HOW_ the probability that a user starts an
operation at time K depends on the number of operations already started.

Your next to final question about multiple starts appears to be answered -
"no implications".  Nowhere do we use the identity of the user who starts the
operation.  Two operations started by one user look exactly like one each
for two users.

If the operations have distinct (but still non-random durations), you have
keep track of the type and duration, but your formulae will be similar (if
more complex).

After conversing with the poser by mail a few times I am becoming convinced 
that a queueing theory model is appropriate. Assume one queue with 
uniformly distributed arrival times, where each item in the queue stays until 
served or time D elapses. Then the length of the queue is the same as the 
number of active processes (of duration D)./

Unfortunately, I don't know any of the relevant formulas!

Re: .2

>a) I assume you intend that N and D are not randomly chosen, but that you
>   treat them as constants in each particular problem.

N and D are constants.

>d) The equal probability assumption and the limited number of operations in
>   any period may turn out to be mutually inconsistent.
>   
>      I suggest we replace the former with an assumption like:
>      
>   The probability that any user starts an operation at time K depends only
>   on the number of operations already started (M-X).

I am sorry for the confusing problem statement. In the initial
statement of the problem, each user executes the operation exactly once
in the time interval T, thus leading to the result that the probability
that the operation starts at time K is 1/T.

The clarifications and assumptions apply to the initial problem
statement. The latter questions I posed as extensions to the problem.
They may invalidate some of the earlier assumptions.

numops is the number of operations that are active at any given time.
It can vary between 0 (if no users start an operation) and N (if all
users start an operation).

I assume that "M" is the number of operations that *one* user can
perform in time T. This applies in the case of the first extension to the problem.

>Your next to final question about multiple starts appears to be answered -
>"no implications".  Nowhere do we use the identity of the user who starts the
>operation.  Two operations started by one user look exactly like one each
>for two users.

Consider the following -

	1	2	3	4	5
User 1	+---------------+---------------+        (M = 2)
User 2  +---------------+			 (M = 1)

In this case, the probability of overlap is higher than if M = 1 for User 1.

bc

    For any one of the users, let p(t) be the probability that an operation
    is ongoing at time t.  Then, since the time interval is 1..T, and each
    operation takes D ticks,
    
           min(t, T-D)
    p(t) =     Sum       1/(T-D) = (min(D,T-t) - 1)/(T-D)
          start = t-(D-2)
    
    Now for N users, what's the probability that there are NO operations
    at time t?
    
    	(1-p(t))^N
    
    And the probability that there is exactly ONE operation at time t?
    
    	N�p(t)�(1-p(t))^(N-1)
    
    And the probability that there are two or more operations at time t?
    
    	1 - Q^N - N�P�Q^(N-1) = 1 - Q^(N-1)�(Q+N�P)
    
    where P = p(t), and Q = 1 - p(t).

RE: .5

    In fact, the answer is, under these circumstances, the binomial
    distribution:

			     k N-k
	prob(k) = comb(N, k)P Q

    Where comb(N,k) = N!/k!(N-k)!

					Topher

There are some errors in the expression for p(t).  Let's try it again.

There are T-D equiprobable times when an operation can start,
t = 1, 2, ..., T-D (if it were to start at time T-D+1, it would end
at time T-D+1+D = T+1, which is outside the time range).

For an operation to be ongoing at time t, it must've started at time t, t-1,
... t-(D-1) (but not t-D, since that would cause the operation to end at time
t-D + D = t, which means it's no longer 'onging').

Adding:
	    min(t, T-D)
    p(t) =     Sum       1/(T-D) =
          start = max(t-(D-1),1)

	= (min(t,T-D) - max(t-(D-1),1) + 1)/(T-D)

	= ( min(t+D,T) - max(t,D) )/(T-D)

Which should be much better.  We can check that Sum(p(t)) = D-1

	       T          T		   T
	(T-D) Sum p(t) = Sum min(t+D,T) - Sum max(t,D)
	      t=1        t=1		  t=1

		  T-D		     T
		= Sum min(t+D,T) +  Sum min(t+D,T)
		  t=1		  t=T-D+1

		   D		   T
		- Sum max(t,D) -  Sum max(t,D)
		  t=1		 t=D+1

		  T-D					       T
		= Sum (t+D) + (T - (T-D+1) + 1) � T - D � D - Sum t
		  t=1					     t=D+1

		= (T-D)�(T-D+1)/2 + (T-D)�D + D�T - D�D - T�(T+1)/2 + D�(D+1)/2


		= (T-D)�(T-D+1)/2 + 2�D�T - 2�D�D - T�(T+1)/2 + D�(D+1)/2

		= ... = (D-1)�(T-D)

Hoorah!  It checks.

Thanks for your help, everybody.

Assuming that the pre-conditions for using it are valid, the binomial
formula provides a good estimate of the probabilities.

As Lynn suggests, Queueing Theory provides a model for the more general
problem (which I have not stated completely). For example, my model is
a simplified instance of a closed queueing network with multiple job
classes, which have been extensively studied by J.R. Jackson, J.P.
Buzen, P.J. Denning and others.

Computationally efficient algorithms for these networks are detailed in -

Computational Algorithms for Closed Queueing Networks

Steven C. Bruell
Gianfranco Balbo

North Holland

bc

    Re .8:
    
    What year is that book?
    
    I always use the Computer Performance Modelling Handbook, but I worry
    that it might be out of date (1984).
    
    --  Barry