2
$\begingroup$

This probability question is based on a real problem: My server gives an error if it gets hit by more than $5$ requests in one second. If I have $N$ daily users, and each one sends an average of $M$ requests to the server per day (assuming each request takes exactly one second), what are the chances that the server will give an error that day?

Specifically, for an average day, I'd like to know $P(\geq 1 \space error)$ (the probability that the server gives at least one error that day), as well as $E[\#errors]$ (the expected value of the total number of errors that day)--so that I can then calculate the expected number of errors over the course of one year, for example.


What I have so far: For any given user, whenever they send a request to the server, what are the chances another one of the $N-1$ users is doing it at the same time? There are $86,400$ seconds in one day, and each user is sending a request for $M$ of those seconds, so the chances are: $$1 - \left(\frac{86,400-M}{86,400}\right)^{N-1}$$ Is that correct? If so, what are the chances that this happens to any user, not just a given $one$?

$\endgroup$
  • 1
    $\begingroup$ The answer provided by Antoine Falck presumes that a single user cannot generate more than one request in a given second. Is that true in your problem? Is that what you mean by "each request takes exactly one second"? If so, then their answer should work. Otherwise, you should use a Poisson distribution with rate $\frac{MN}{86400}$. $\endgroup$ – Brian Tung Apr 2 at 16:12
  • $\begingroup$ @BrianTung Yes, that is correct: for the sake of simplicity, we can assume that each user can generate at most one request per second. $\endgroup$ – jamaicanworm Apr 3 at 12:45
  • $\begingroup$ I actually don't think that makes things simpler, but sure. :-) $\endgroup$ – Brian Tung Apr 3 at 15:33
1
$\begingroup$

This seems like a basic application of a Poisson distribution with $\lambda = \frac{NM}{86400}$. The probability that there are excatly $i$ events within any particular second is $P(i) = \frac{\lambda^i e^{-\lambda}}{i!}$. The probability that there are 0 to 4 requests in any particular second is:

$$\sum_{i=0}^4 P(i) = e^{-\lambda}\left(1 + \lambda + \frac{\lambda^2}{2} + \frac{\lambda^3}{6} + \frac{\lambda^4}{24}\right)$$

So the probability that a particular second will have 5 or more failures is the complement of that probability, call it $F_{sec}$.

Given that $F_{sec}$ is the probability that any particular second contains a failure, you will expect to see an average of $86400F_{sec}$ failures each day. This represents another Poisson distribution with $\lambda= 86400F_{sec}$, so the probability that the day will be error-free is $e^{-86400F_{sec}}$.

$\endgroup$
1
$\begingroup$

This is a typical problem in Queueing Theory, which was in fact initiated by studying the congestion on telephone lines and switches.
And calls for service to a central computer is just a modern version of that.

But let's approach the matter discretely first.
So you have N lines on average, and M calls per day and per line are placed on the average.

Let's assume that the calls occur independently from the previous ones (memoryless), either on the same line, and across different lines.
Since for each line you are discretizing the time in cells of $1$ second , then we can model each line as a Bernoulli process, i.e. as a binary string of length one day, which means $m=86400$ seconds. The probability that a call (a digit 1) occurs in a given cell on a given line is thus $p=M/86400$ and $q=1-p$ is the probability of not having a call.
Since $$ 1 = \left( {p + q} \right)^{\,m} = \sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,m} \right)} {\binom{m}{s}p^{\,s} q^{\,m - s} } $$ each term in the sum gives the probability to have $s$ calls on that line totally in a day.

Let's assume now that exactly $n$ lines are active in a given day. We can think of them as $n$ rows of binary strings of length $m$. Therefore at a given discrete time we have a column which is a binary string of length $n$, with probability $p$ that each cell of it contains a call. So the probability that a column contains exactly $c$ calls is $$ P(c|n) = \binom{n}{c}p^{\,c} q^{\,n - c} $$ and if $c$ is more than $5$, then the server will collapse in that second, with probability $$ P(5 < c|n) = \sum\limits_{6\, \le \,c\,\left( { \le \,n} \right)} {\binom{n}{c}p^{\,c} q^{\,n - c} } $$

Looking at the sequence of columns, and standing the assumed independence of calls, that also represents a sequence of $m$ Bernoulli trials, with $p$ (probability of congestion) given by the above. Then it is clear how to compute the probability of having a certain number of faults per day.

Coming then to the probability distribution for $n$, which we know to have a mean of $N$, you can take that to be binomial as well, or if the maximum number of users is limited you may take it to be uniform, or another distribution more adequate to the actual situation. Then $$ P(5 < c) = \sum\limits_n {P(5 < c|n)P(n)} $$

will make up the value for $p$ in the sequence of $m$ Bernoulli trials.

Finally we know that the Binomial distribution is asymptotic to the Normal or to the Poisson distribution . In particular, if the Poisson approximation is applicable, we can apply one of the studied queue models, e.g. the M/D/C queue model.

-- Example --

Let's take for instance $M = 8640$, then $p=M/86400=1/10,\; q=0.9, \; p/q=1/9$.
So $P(5 < c|n)$ will be $$ \eqalign{ & P(5 < c|n) = \sum\limits_{6\, \le \,c\,\left( { \le \,n} \right)} {\binom{n}{c}p^{\,c} q^{\,n - c} } = \cr & = 1 - q^{\,n} \sum\limits_{0\, \le \,c\, \le \,5} {\binom{n}{c} \left( {{p \over q}} \right)^{\,c} } = \cr & = 1 - \left( {1 - {1 \over {10}}} \right)^{\,n} \sum\limits_{0\, \le \,c\, \le \,5} {\binom{n}{c} \left( {{1 \over 9}} \right)^{\,c} } \cr} $$

We shall consider this as a function of $n$, and for the moment let's waive from seeking an approximation.

Now, let's take for example $N=10$.
If we assume that $n$ is uniformly distributed with that mean, starting from $n=0$, then $n$ is uniformly distributed in the interval $0 \le n \le 2N-1=19$ with probability $1/20$. Therefore the probability to have a congestion at any second will be $$ \eqalign{ & P(5 < c) = \sum\limits_n {P(5 < c|n)P(n)} = \cr & = {1 \over {20}}\sum\limits_{0\, \le \,n\, \le \,19} {P(5 < c|n)} = \cr & = 1 - {1 \over {20}}\sum\limits_{0\, \le \,n\, \le \,19} {\left( {1 - {1 \over {10}}} \right)^{\,n} \sum\limits_{0\, \le \,c\, \le \,5} {\binom{n}{c} \left( {{1 \over 9}} \right)^{\,c} } } = \cr & \approx 1.435\; \cdot 10^{\, - \,3} =f \cr} $$

In a period of $T$ seconds, the probability of having exactly $s$ faults will follow the Binomial distribution $$ P\left( {f|T} \right) =\binom{T}{f}p^{\,f} \left( {1 - p} \right)^{\,T - f} $$

For instance, in one hour, the probability not to have any fault is: $$ P\left( {0|1\,h} \right) = P\left( {0|3600} \right) = \left( {1 - f} \right)^{\,T} \approx 5.7\; \cdot 10^{\, - \,3} $$ while in a hour you can expect a number of faults $$ \eqalign{ & E\left( {s|T,f} \right) = f\,T \approx 5.165 \cr & \sigma = \sqrt {f\,\left( {1 - f} \right)T} \approx 2.156 \cr} $$ and all the other parameters derivable for that distribution.

And since you have a sequence of $T$ bernoulli trials, following this link you can also compute the probability of having a certain number of consecutive seconds of blackout.

$\endgroup$
  • $\begingroup$ So what does that probability come out to? And is there a way to calculate the expected number of errors over the course of one day or year? $\endgroup$ – jamaicanworm Apr 10 at 13:35
  • $\begingroup$ @jamaicanworm: I added an example, wish it helps to clarify. $\endgroup$ – G Cab Apr 11 at 16:51
0
$\begingroup$

The probability that a specific user sends a request in a specific second is $p=\frac{M}{86,400}$. Then the number of requests received by the server in a specific second, noted $X$, follows a binomial law, $X\sim\mathcal{B}(N,p)$.

So $\mathbb{P}\{X\geq 5\}$ gives you the probability to have an error for a specific second. I'll let you compute this probability ; and then continue the computation for each second in the day.

$\endgroup$
0
$\begingroup$

This is my best approach:

Define the random variable X as $$X=\{\text{Max number of concurrency on a day }\}$$

Notice that the max outcome of $X$ is N (it's the worst case: when all the users do a request in the same second).

The min outcome of $X$ is more difficult to find: for example, if the total number of requests ($MN$) is greater than $86400$, you can be sure that there will be at least one second with more than one request. So we will assume that $86400>MN$, so the support of $X$ is {1,...,N}.

We are intereseted in $P(X\geq 5)$, but I will compute $P(X\geq2)$, in fact, the probability of the max concurrency being at least 2 is pretty straighforward because: $$P(X\geq2)=1-P(X=1)$$ where $P(X=1)$ is the probability that any request colision with each other, which is not as hard to compute:

The total number of requests outcomes that do not colision with each other is: $$ \binom{86400}{M}\binom{86400-M}{M}\binom{86400-2M}{M}\cdots\binom{86400-(N-1)M}{M}$$ which is a kind of telescopic product: $$\require{cancel}\frac{86400!}{M!\cancel{(86400-M)!}}\cdot\frac{\cancel{(86400-M)!}}{M!\cancel{(86400-2M)!}}\cdots\frac{\cancel{(86400-(N-1)M)!}}{M!(86400-NM)!} =\frac{86400!}{(M!)^N(86400-NM)!}$$ and the total request outcomes are $$\binom{86400}{M}^N$$ so the probability of $P(X=1)$ is: $$P(X=1)=\frac{\frac{86400!}{(M!)^N(86400-NM)!}}{\binom{86400}{M}^N}= \frac{86400!}{(M!)^N(86400-NM)!}\,\cdot\,\frac{(M!)^N((86400-M)!)^N}{(86400!)^N} =\frac{((86400-M)!)^N}{(86400!)^{N-1}(86400-NM)!}$$

hence: $$P(X\geq2)=1-\frac{((86400-M)!)^N}{(86400!)^{N-1}(86400-NM)!}$$

$\endgroup$
  • $\begingroup$ Do you mean X = {Max number of occurrences in a SECOND}? $\endgroup$ – jamaicanworm Apr 8 at 13:28
  • $\begingroup$ yes, but take into account that X does not depend on a single second: it's the max number of occurence of the most concurrent second. $\endgroup$ – Wilem2 Apr 8 at 19:59
0
$\begingroup$

I think we can convert this problem to bins and balls problem, and in that too we can go to the specific problem of Bose-Einstein statistics, where we have $n$ distinguishable bins (number of seconds in a day) and $MN$ indistinguishable requests to the server(we don't care who sends the request, just the frequency matters).

Now, $n = 8640 $ i.e. the number of one-second bins that we have in a day. Let $r = MN$ be the total requests to the server in a day. The requests can be seen as identical balls being thrown at the bins. Now if you will follow this link, you will see that the probability of a having $i$ balls in a given bin is given by $$P_i = \frac{n+r-i-2 \choose r-i }{n+r-1 \choose n-1}$$

In our case, we want the total probability of having more than 5 balls in one bin. which can be written as,

$$P_{total} = \sum _{i=5}^{r} P_i$$


I see that what I have written is not immediately evident. Hence I have written this small python2 snippet with the above reasoning. Although it can not handle large $n$. But I think it will definitely convince you of the reasoning.

from math import factorial as fact
from itertools import combinations_with_replacement as cwr
import numpy as np
nCr = lambda n, r: fact(n) / fact(n-r) / fact(r)

def partitions(n, b):
    partition_array = np.empty((nCr(n+b-1, b-1), b))
    masks = np.identity(b)
    for i, c in enumerate(cwr(masks, n)):

        partition_array[i,:] = sum(c)

    return partition_array

b = input("Number of seconds: ")
n = input ("Total Number of requests: ")
fault_min = input("Maximum number of allowed requests per second: ")
array = partitions(n,b)
print("\nFollowing is the list of all possible cases \n ")
fault = 0
fault_value = 0
for row in array:
    print(row)
    if row.max() >= fault_min:
        print("The above case will give error")
        fault_value = fault_value + 1
P_fault = float(fault_value) / float(len(array))
print(fault_value)
print("................................................")
print("Probability of server failure = %f "% (P_fault))

For an input of 3 seconds and 5 requests (with maximum allowed requests per second set to 3) it gives the following output.

Number of seconds: 3
Total Number of requests: 5
Maximum number of allowed requests per second: 3

Following is the list of all possible cases

[5. 0. 0.]
The above case will give error
[4. 1. 0.]
The above case will give error
[4. 0. 1.]
The above case will give error
[3. 2. 0.]
The above case will give error
[3. 1. 1.]
The above case will give error
[3. 0. 2.]
The above case will give error
[2. 3. 0.]
The above case will give error
[2. 2. 1.]
[2. 1. 2.]
[2. 0. 3.]
The above case will give error
[1. 4. 0.]
The above case will give error
[1. 3. 1.]
The above case will give error
[1. 2. 2.]
[1. 1. 3.]
The above case will give error
[1. 0. 4.]
The above case will give error
[0. 5. 0.]
The above case will give error
[0. 4. 1.]
The above case will give error
[0. 3. 2.]
The above case will give error
[0. 2. 3.]
The above case will give error
[0. 1. 4.]
The above case will give error
[0. 0. 5.]
The above case will give error
18
................................................
Probability of server failure = 0.857143
$\endgroup$
  • $\begingroup$ Thanks! I'm a bit confused about your bins... they shouldn't be 5-second long timestamps, but rather the chance of getting hit with 5 requests in the same second. $\endgroup$ – jamaicanworm Apr 3 at 12:46
  • $\begingroup$ I am sorry! I read the question wrong, I thought we don't want 5 requests within the period of 5 seconds. Now that it is 5 requests within the period of one second. We can check for the probability of 5 balls falling in 8460 bins instead of (8460/5) bins. I have made the corresponding edits, I hope it is clearer now. $\endgroup$ – SagarM Apr 3 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.