# 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 = μ ≤ t1.
• At least p percent of all response times must be less than t2 ⇔ P(T < t2) > p.

To satify these requirements tune the system such that its μ and σ satify: μ ≤ t1 and μ + kσ < t2 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 μ ≤ t1 and μ + σ/√(1 &minus p) < t2 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 t1 = 1s, t2 = 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.