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

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

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