Thread: Probability for two events to be simultaneous

Hi every ones,

First, I an an old folk that have completed some statistics classes 25 years ago. But now, I am to rusty to solve this by myself. ( However, I tried).

And I really need an answer. Your help would be appreciated.

Here is the problem:





A computer update its clock once every 1xE-8 seconds. Therefore, 3.1536xE15 times per years.


So, since the computer update its time every 1xE-8 seconds, if two events happen into this interval of time,the computer will see them as being simultaneous.


This computer receive some information requests and it takes about 2xE-3 second to process each one of them (However, it can be some minutes, between each request)


1) The computer cannot process more than 1 request at the time.
2) Each time that the computer receive a request, it records the time where the request was received and puts a "time stamp" on the request.

request can be received at any time during a day, but:
the probability for a request to be received at certain time during the day is as follow:


-Between 8:00 and 17:00, = 0.801 with equal probability at any time of this interval (ie: 80.1% are received in this interval)
-Between 17:00 and 21:00, = 0.177 with equal probability at any time of this interval (ie: 17.7% are received in this interval)
-Between 21:00 and 8:00, = 0.022 with equal probability at any time of this interval (ie: 2.2% are received in this interval)




The computer will receive "X" requests each year


NOW:


Assuming that we have "Y" computers receiving requests (each one of them receiving "X" requests every year), what is the probability that 2 requests, or more, gets the same "Time Stamp" at the end of the year(In other words: that two computers, or more, have received request simultaneously during the year)

Please clarify something: if a request is received at time 0, and a 2nd request comes E-8 seconds later, does the computer record the "correct" time for each, or does it gve a time stamp on the second that is 2E-3 seconds after the fact (I'm trying to understand why the compute time matters at all)? And what happens if a computer receives two requests within the E-8 second "window" - does it give both the same time stamp? if all you're concerned about is the probability that two different computers will generate the same time stamp that's pretty straight forward....

Let suppose we have 3 computers receiving requests

and here a scenario that may show what I need

In a first time, computer 1 receive a request at time=0. Then computer 1 will put to the request the time stamp T=0

Now, computer 1 need to process this request, therefore, computer 1 cannot receive any more request for a period of 2xE-3 seconds.

While this is going on, Computer 2 and computer 3 are not busy and can receive some requests. if any of these 2 computers receive a request before time = 1xE-8 then, this computer will also put to the request the time stamp T=0 ( Since 1x10E-8 seconds has not elapsed ).

therefore there will be two request with the time stamp T=0 , One from the computer 1 and one from the computer 2 : ( Time stamp Collision)

Now, why the time to process matter? Because,
if computer 1 receive a request at T=0,
Computer 2 gets one at T= 5xE-8
and finally computer 3 get one at T=20E-8

then, no more request can be received before one of the computers get free again, which will only happen 2xE-3 seconds later.

And also, there will not be any possible Time Stamp collision before at least 2 computers get free. (This will happen in the example when computer 2 will get free,
at [2E-3 + 5E-8] seconds)

Basicaly, if a computer get a request at time T=t, if its time stamp didn't make a collision at this time, this computer cannot possibly make another collision before 2xE-3 seconds later, the time it takes it to get free to receive another request.

OK, that helps. One more question - what determines which computer receives a request? If a request comes in while computer 1 is busy and compurter 2 is not, will that request be sent to computer 2? Or is it randomly assigned, so that even though computer 1 is busy it may be assigend to computer 1 and won't be processed until computer 1 is freed up?

All free computers have an equal probability to be the one to receive the next request. No request are schedule towards a busy computer if one is free.

If all computer are busy, the next request is queued and will be assign to the first free computer

OK, so here's a scenario: you have 2 computers, and both happened to receive a request at t=0, so both get the same time stamp and both computers are busy for the next 2E-3 seconds. Now suppose a request comes at T= 1E-4 seconds, and a second at t=1.5E-4 seconds (while both computers are busy), so they get queued to wait for a free computer. So at T=2E-3 seconds both computers become free at the same instant, and so each gets assigned a new request and those requests get time stamped the same time - is that right?

It seems that the conditions under which two requests can have the same time stamp are:

1. Two (or more) requests arrive at the same time (meaning within 1E-8 seconds of each other) and two (or more) computers are free.
2. All computers are busy and two (or more) have the same ending time, and at the time they become free there and two (or more) requests in queue.

Are there any other scenarios that result in two (or more) identical time stamps?

The scenarios that will cause collision:

1) no computer is busy and 2 requests comes within 1E-8 seconds

2) only one computer is busy and 2 requests comes within 1E-8 seconds after the busy computer gets free

3) 2 computers are busy but one will get free more than 1E-8 seconds before the other one than
A) no request comes before both gets free == we are going back to scenario 1)
B) only one request comes while they were both busy == The request will be given to the computer that will free first therefore no collision can happen
C) two requests or more came while they were both busy, when the first get free it will get a request and when the second gets free it will get a request. Since they will get free with a longer than 1E-8 interval, there will be no collision

4) the 2 computers became busy simultaneously ( causing a collision ) . they will then became free simultaneously. So
A) if 2 requests came while they are busy they will be given simultaneously to both computer, causing another collision.
B) if 1 request came while they were busy, A collision will only happen if a second request comes within 1E-8 second after they got free
C) if no request came while they were busy, then we are back to scenario 1)

It is also to be understand that when 2 computers or more are free, there is a possibility of collision every E-8 seconds

if only one computer is free, it is impossible to get a collision.


----------------------

There is a number of "X" computers

If this can help you to help me:

I created a program that simulate this.

with 2 computers and 1,000,000 requests per day

I simulated 100 Years of processing and got an average of 152 collisions per day