Heterogeneous sampling setting

Wieder (2007) introduced the heterogeneous sampling setting for the \(\DChoice \) process where each of the \(d\) bins are sampled from a skewed distribution \(\mathcal {S}\), where \(\frac {1}{an} \leq \mathcal {S}_i \leq \frac {b}{n}\) for some fixed \(a := a(n)\) and \(b := b(n)\).

Below, we give a formal definition for any \(\DSample \) process.

\(\Heterogeneous (\mathcal {P}, \mathcal {S}^t)\) Setting:
Parameters:

• \(\mathcal {P}\): A \(\DSample (Q^t)\) process.
• \(\mathcal {S}^t\): A probability vector for sampling the bins.

Iteration: At step \(t \geq 0\), allocate ball \(t+1\) using the allocation vector

\begin{align*} q_i^t(\mathfrak {F}^t) & = \sum _{j_1, \ldots , j_d \in [n]} \sum _{k \in [d] : j_k = i} Q^t(\mathfrak {F}^t, j_1, \ldots , j_d, k) \cdot \prod _{\ell = 1}^d \mathcal {S}_{j_{\ell }}^t. \end{align*}

They show that there exist \(d' := d'(a, b)\) such that for any \(d > d'\), the gap of the \(\DChoice \) process diverges while for \(d < 1 - \eps \) (for any small constant \(\eps > 0\)) it is \(\Theta (\log \log n)\). This implies that for \(\TwoChoice \) has a \(\Theta (\log \log n)\) gap only when \(a\) and \(b\) are sufficiently small constants. In contrast, it was shown in [1] that for arbitrary constants \(a\) and \(b\), the \(\Memory \) process has a \(\Theta (\log \log n)\) gap (“power of memory”).

References

[1] Dimitrios Los, Thomas Sauerwald, and John Sylvester. “Balanced Allocations with Heterogeneous Bins: The Power of Memory”. In: 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’23). SIAM, 2023, pp. 4448–4477. doi: 10.1137/1.9781611977554.ch169.
[2] Udi Wieder. “Balanced allocations with heterogenous bins”. In: 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’07). Ed. by Phillip B. Gibbons and Christian Scheideler. ACM, 2007, pp. 188–193. doi: 10.1145/1248377.1248407. url: https://doi.org/10.1145/1248377.1248407.