How large $\mathbb{E} \bigg[\max_{k \in \{1,\dots,K\}}\sum_{t=1}^T \mathbb{I}\{X_t=k\}\bigg] - \frac{T}{K}$ can be?

Question

For each $K \in \mathbb{N}$, assume that $X_1,X_2,\dots$ is an i.i.d. sequence of (discrete) uniform random variables on the set $\{1,\dots,K\}$ and, for each $T \in \mathbb{N}$, define the quantity $$ f(K,T):=\mathbb{E} \bigg[\max_{k \in \{1,\dots,K\}}\sum_{t=1}^T \mathbb{I}\{X_t=k\}\bigg] - \frac{T}{K} $$

I'm looking for a function $K^*:\mathbb{N} \to \mathbb{N}$ such that $$f\big(K^*(T),T\big) = \Omega(T^\alpha)\;,$$ for $\alpha>0$ as big as possible.

So far, what it seems clear to me is that for $K=2$ this is basically equivalent to computing the expected deviation of a symmetric random walk in dimension one from the origin, so $f(2,T)=\Omega\big(\sqrt{T}\big)$. On the other hand, if $K^*(T) \gg T$, the intuition suggests that $f\big(K^*(T),T\big)=O(1)$ (with high-probability, each $k \in \{1,\dots,K\}$ occurred just once). So, if we pick $K^*(T) = 2$ we get $\alpha = 1/2$, and if we get $K^*(T)$ too big, then $\alpha = 0$. However, what happens in between? What's a sensible way to select $K^*$ to get $\alpha$ as big as possible?

Any suggestions, pointers, or references?

Answer 1

The limit behavior is described in Kolchin, Sevast'yanov, Chistyakov Random allocations:

Denote $\eta_{K} = \max_{1\le k\le T} |\{t\le T: X_t=k\}|$, $\alpha = T/K$, $p_k = \alpha^k e^{-\alpha}/k!$, $k=0,1,\dots$

• If $\alpha/ \ln K \to 0$ as $K\to \infty$ and $r=r(\alpha,K)>\alpha$ is such that $K p_r \to \lambda$, then the limit distribution of $\eta_K$ concentrated in $r-1$ and $r$: $$ \mathrm{P}(\eta_K = r-1)\to e^{-\lambda}, \mathrm{P}(\eta_K = r)\to 1-e^{-\lambda}. $$
• If $\alpha/\ln K \to x$ as $K\to \infty$ and $r=r(\alpha,K)>\alpha$ is such that $K p_r \to \lambda$, then $$ \mathrm{P}(\eta_K \le r+k) \to \exp \Big\{ - \frac{\lambda \gamma^{k+1}}{1-\gamma}\Big\}, $$ where $\gamma\in (0,1)$ is the solution to $\gamma + x(\ln \gamma - \gamma + 1) = 0$.
• $\alpha/\ln K \to \infty$ as $K\to \infty$, then $\eta_K$, properly normalized$^*$, converges to the Gumbel distribution.

---

$^*$ This is quite cumbersome, so I won't write it.