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 ⁽¹⁾ 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 ⁽¹⁾ usually take the following form:

Average response time = μ ≤ t₁.
At least p percent of all response times must be less than t₂ ⇔ P(T < t₂) > p.

To satify these requirements tune the system such that its μ and σ satify: μ ≤ t₁ and μ + kσ < t₂ with p = 1 − 1/k².
NB. p = 1 − 1/k² ⇒ k = 1/√(1 &minus p).

Notice μ and σ can be measured (estimated ⁽²⁾). After which one can verify whether μ ≤ t₁ and μ + σ/√(1 &minus p) < t₂ 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₁ = 1s, t₂ = 4s and p = 90%. Let M and S be the measured (estimated ⁽²⁾) 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)Σ_it_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}.