# Chebyshev's inequality and Response Times

by Ronald Koster, version 1.0, 2004-04-14

**Keywords:** Chebyshev's inequality, response times, performance requirements

## Introduction

Response times of a computer system generally have an unknown propability distribution. However, using Chebyshev's inequality one
can still make accurate predictions on a system's response times. That way one can determine whether certain perfomance requirements
have been statisfied or not.
#### Definitions

The response time T of a functionality ^{(1)}
of a computer system is a stochast with a probabilty distribution f with mean μ and standard deviation σ.
As mentioned above the exact form of f is usually unknown. The following analysis now applies.
## Chebyshev's inequality

**Chebyshev:** For all possible distributions: P(|T − μ| ≥ kσ) ≤ 1/k², with k > 0

⇒ P(T − μ ≥ kσ) = P(T ≥ μ + kσ) = 1 − P(T < μ + kσ) < 1/k²

⇒ P(T < μ + kσ) > 1 − 1/k².
## Satifying the performance requirements

Performance requirements for a functionality ^{(1)} usually take the following form:
- Average response time = μ ≤ t
_{1}.
- At least p percent of all response times must be less than t
_{2} ⇔ P(T < t_{2}) > p.

To satify these requirements tune the system such that its μ and σ satify: μ ≤ t_{1}
and μ + kσ < t_{2} with p = 1 − 1/k².

NB. p = 1 − 1/k² ⇒ k = 1/√(1 &minus p).

Notice μ and σ can be measured (estimated ^{(2)}). After which one can verify whether
μ ≤ t_{1} and μ + σ/√(1 &minus p) < t_{2}
are satisfied.

The following table displays some values of k and p.

k | p |

2 | 0,75 |

3 | 0,89 |

3,16 | 0,90 |

4 | 0,94 |

4,47 | 0,95 |

5 | 0,96 |

NB. √10 = 3,16 and √20 = 4,47.
## Examples

#### Example 1

Suppose t_{1} = 1s, t_{2} = 4s and p = 90%. Let M and S be the
measured (estimated ^{(2)})
values for μ and σ. Thus all one needs to verify is whether M ≤ 1s and M + 3,16S < 4s are satisfied.

NB. Suppose the requirements have been satified and M = 1s (worst case scenario). Combining this
with M + 3,16S < 4s gives S < (4 − 1)/3,16 = 0,95s ⇒ M + 4,47S < 5,24s, meaning 95% of all responses will be within 5,24s.
#### Example 2

Suppose M = 1,3s and S = 0,85s. Then M + 3,16S = 4,0s. Thus 90% of all response times will be less than 4,0s.
## Conclusion

Chebyshev's inequalty can be used to make accurate predections on a system response time. Also it can be used to test whether certain
performance requirements have been statisfied.

(1): For example a screen or an API.

(2): Unbiased estimates for μ and σ : M = (1/n)Σ_{i}t_{i} and
S = √((1/(n-1))Σ_{i}(t_{i} − M)²), with n = number of measured
response times, t_{i} = measured response time i, i ∈ {0, 1, ..., n − 1}.