Model of Maximum Load on a Distributed Cache

Given gaps distributed by $Exp\Big(n)$, we replace $1 - p$ and $\lambda$ with $1 - n/\Big(n + 1)$ and $n$ respectively.

I have previously written about the gap between consecutive order statistics of $U\Big(0, 1)$. In this post I’m just going to note several ways to estimate the expectation of the maximum gap from a sample of $U\Big(0, 1)$ draws. This isn’t a purely academic exercise, estimating gaps of the uniform is of particuar interest when analyzing load patterns in distributed load balancing algorithms (e.g. consistent hashing).

$\textbf{Figure 1.0}$ — Estimates for Expected Max Gap

Adjacent order statistics of $n$ draws of $U\Big(0, 1)$ are distributed as $Beta\Big(1, n)$. We’ll approximate $Beta\Big(1, n)$ as $Exp\Big(n)$ and use the inverse CDF of the exponential to estimate the expectation of the maximum gap as a function of $n$.

$$\begin{equation} F_{\lambda}^{-1}\Big(p) = -\log\Big(1-p)/\lambda \implies E\Big[X] \approx \log\Big(n + 1)/n \end{equation}$$

We can still arrive at $Exp\Big(n)$ without this handy fact about order statistics memorized. Consider a point $a \in \Big(0, 1)$ and a ball centered at $a$ with radius $r$. The probability that any of $n$ other points fall inside $\operatorname{Ball}\Big(a, r)$ is $1 - \Big(1 - 2r)^n \approx 1 - e^{-2rn}$. This is the CDF for $Exp\Big(n)$ and the argument proceeds as above. $\blacksquare$

If we want to be more precise we can calculate the CDF of the maximum of $n$ instances of $Beta\Big(1, n)$. This more complicated calculation yields a result that is on the order of $log\Big(n)/n$.

$$\begin{equation} \int_0^1 n\Big(1 - x)^{n - 1} dx = 1 - \Big(1 - x)^{n} \implies \Big(1 - \Big(1 - x)^{n})^{n} \end{equation}$$

$$\begin{equation} 1 - \int_0^1 \Big(1 - \Big(1 - x)^{n})^{n} dx = 1 - \int_0^1 \Big(1 - x^{n})^{n} dx \end{equation}$$

Now we can calculate the expectation of the largest gap from it’s CDF. This is made easier because Wolfram Alpha catches that $\int_0^1 \Big(1 - \Big(x)^{n})^{n} dx = \frac{\Gamma\Big(1 + 1/n)\Gamma\Big(1 + n)}{\Gamma\Big(1 +n + 1/n)}$. From there we get the following result by noticing this is $\textit{almost}$ the Beta function.

$$\begin{equation} E\Big[X] \sim \left(1 - \Big(1 + n + \frac{1}{n}) \int_0^1 \Big(1 - x)^{\frac{1}{n}} x^{n} dx \right) = 1 - \Big(1 + n + \frac{1}{n}) \cdot \textbf{B}\Big(1 + \frac{1}{n}, 1 + n) \end{equation}$$