Distributed systems are everywhere. Core element is the scheduling of elements on limited resources, from access t0 CPU cores up to a fleet of vehicles becomes balanced in its access to charging stations. In its roots a queue is a simple list like data structure following some guiding rules (aka discipline). From time perspective the queue theory distinguishes between the following three sub-processes:
- Arrival process
- Service process
- Serving process
One common queue type is MM1 what stands for
- Arrival process = multiple arrive at the queue,
- Service process = multiple have to wait until get served,
- Service process = 1 can be served at a time.
Common properties are estimated as follows:
- λ = Arrival rate = Number of visitor per unit of time
- μ = Working rate = Number of visitor per unit of time
- ρ = Load rate = Arrival rate / Working rate
- Utilization = Arrival rate * Working rate
- Lead time = 1 / (Working rate – Arrival rate)
- Waiting time = Arrival rate / ( Working rate * (Working rate – Arrival rate) )
- Queue length = Arrival rate^2 / (Working rate * (Working rate – Arrival rate) )
- Work in progress = Arrival rate / (Working rate – Arrival rate)
For afore mentioned use cases of operating system or charging point scheduling the processes the probability distribution are best described by
- Arrival rate/ process = e.g. Poisson distribution
- Service rate / process = e.g. Exponential distribution
- Serving rate / process = e.g.Gaussian distribution
The probability assumption helps to determine tech probability that more or less visitor are to process.
But why process, probability and distribution?
A process is simply a sequence on activities, state changes, etc. A process can be quite good illustrated via process diagram e.g.
Another representation is a transition table (aka matrix, M), e.g.
| S1 | S2 | S3 | |
| S1 | 0.3 | 0.3 | 0 |
| S2 | 0.7 | 0 | 0.95 |
| S3 | 0 | 0.7 | 0.05 |
Having the transition table in place an individual journey can be simulated. Let’s assume Dirk start at state S1- The respective Transition vector is v = (1,0,0). This results in the first transition distribution M * v = v’. The result is the vector (0.3, 0.7, 0). Lets do it 3 times:
- (0.3, 0.7, 0)
- (0.3, 0.21, 0.49)
- (0.153, 0.6755, 0.1715)
Lets now put the values of the three simulated steps in a density function with
- x = values S1…S3 and
- y = sum of probabilities.
S1 –> 0.753, S2 –> 1.5855 , S3 –>1
The results somehow looks like the ?Gaussian distribution?.
Probability distributions of one variable
Knowing this, the formula could just be applied. Compare e.g., https://vowi.fsinf.at/images/1/14/TU_Wien-Statistik_und_Wahrscheinlichkeitstheorie_VO_%28Gurker%29_-_Formelsammlung.pdf
Let’s look at a poisson distribution. In general the Poisson distribution requires an expected value and a present value. Let’s assume our charging station usually services in mean 2 vehicle (lambda, expected value). How likely is it that it, that 6 vehicles (random variable x) are served. The probability that this happens is roughly 1% (0.01203). Check for example the calculator here. The probability that less than 6 vehicles appear is 1-0.01203 = roughly 99%.
The probability of one variable
Let’s start with frequency while observing one event of one feature (variable) e.g.,
- the absolute frequency for getting the number 6 while dicing is 1.
- The relative frequency (aka probability) is 1/6.
- The commutative frequency is 1/6+1/6+1/6+1/6+1/6+1/6 = 6/6= 1. This is also called a class frequency e.g., the class of getting values 1-3 is 1/6+16+1/6 = 3/6 = 1/2 = 0.5.
Getting statistic figures of one variable
If multiple events, of one variable, are assessed we call it statistics e.g., “what is the expected value?”. Simplified it is the mean value e.g., e.g., for variable “dicing value” in the data series of absolute frequencies 1, 1, 4, 5, 6 the mean value is: (1 + 1 + 4+ 5 + 6) / 5 = 3.4.
Note: It can also be calculated for the relative as well as commutative frequency.
Next is the standard deviation (sigma) as the scattering around the mean value. Or as question: “How much deviate values from the mean?”. Per definition
- 1 sigma contains 68% of all possible values
- 2 sigma contains 95% of all possible values
- 3 sigma contains 99% of all possible values
Note: 100% is also called the confidence interval, as the range containing all possible values.
Extended it to multiple variables
The variance of multiple variable is called co-variance. For two variables is tells something of the relationship between these two – if one changes, how does the other change.
Starting from co-variance, the mean value is known as correlation. If we compare the correlation of multiple observations. And so on…
Probability permutation of one variable
The number of permutations that a vehicle visits 5 charging stations in different order is 5! = 120. If 4 vehicle trying to approach these 5 charging stations the number of possible combinations is 5 x 120 = 600.
Note: If we do have 2 outcome-options the binomialcoefficient with the binomial distribution supports (take and put back). If we do have more than 2 options the binomial coefficient with the (hyper)geometric distribution supports (take and not put back).
Let us consider a fleet of 30 vehicles has 3 charging points C1, C2 and C3 to choose.
Overall after 2 turns:
| C1,C1 | 0.09 |
| C1,C2 | 0.02 |
| C1,C3 | 0.18 |
| C2,C1 | 0.09 |
| C2,C2 | 0.05 |
| C2,C3 | 0.15 |
| C3,C1 | 0.09 |
| C3,C2 | 0.08 |
| C3,C3 | 0.12 |
or as transition table:
| C1 | C2 | C3 | |
| C1 | 0.09 | 0.09 | 0.09 |
| C2 | 0.02 | 0.05 | 0.08 |
| C3 | 0.18 | 0.15 | 0.12 |
The overall probability that C3 will be visited is 0.18+ 0.15 = 0.32 = 32%.
Probability calculus
The product rule = AND rule (the multiplication or product theorem) states that the probability of a single result in a multi-stage random experiment is equal to the product of all individual probabilities on the path to this result. Afore C1 followed by C1 = 0.09.
The addition rule = OR rule (the addition or summation theorem) states that the probability of an event is equal to the sum of all individual probabilities of outcome at this level of the tree diagram. Afore to C1 is = C2 + C3 = 0.33 + 0.33 = 0.66.
Note: The “set of Bayes” is and extension on how if conditions can be expressed with the product and sum rules.
