Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 32 min ago
PreprintarXiv licencearXiv

Optimal support and condensation in random allocations

  • Andrea Ottolini
Open at sourcePDFDOICite

Abstract

How many distinct symbols should a password use? If its length is fixed at n and an observer learns only which symbols appear, the number of compatible passwords is maximized asymptotically when k/n→1/(2log2). We ask what changes when, in addition to the length, aggregate information about the repetition pattern is revealed. We model this by fixing a second additive profile Vk=∑i v(Ji) at scale Vk/n≈ρ. For v(j)=log(j!), the profile records the reduction in the logarithm of the number of compatible words caused by repetitions; we show that once the normalized profile ρ exceeds 0.507834…, the limiting optimal fraction is pinned at 1/2. For a typical multiplicity profile at the optimal support above this threshold, the excess in Vk is carried by a vanishing fraction of used symbols. We interpret this as a form of non-equivalence of ensembles and extend the mechanism to other profiles and non-uniform allocation models.

Related

  1. Envy-Free Allocations for Random Non-Additive Valuations
    Pasin Manurangsi
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. PAIR: Conditional Support Repair of Square-Root Allocations Under Fixed Data Budgets
    Seda Kul, Mehmet Zeki Konyar, Kaplan Kaplan +1
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  3. Analytically Optimal Sample Allocations for Nested Multivariate Multifidelity Control Variate Estimators
    Atticus Rex, Elizabeth Qian
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  4. Reflected BSDEs under random horizons: Sharp support criteria, irregular reflection, and Cox reconstruction
    Youssef Ouknine, Badr Elmansouri
    arXivPreprintCC BY-SA 4.0Full textProbabilityarXiv
  5. Optimal Support Size Testing
    Qisheng Wang
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ottolini2026optimal,
  title = {{Optimal support and condensation in random allocations}},
  author = {Andrea Ottolini},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.24848},
  eprint = {2609.24848},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.24848},
}
RIS
TY  - UNPB
TI  - Optimal support and condensation in random allocations
AU  - Andrea Ottolini
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2609.24848
UR  - https://arxiv.org/abs/2609.24848
AB  - How many distinct symbols should a password use? If its length is fixed at n and an observer learns only which symbols appear, the number of compatible passwords is maximized asymptotically when k/n→1/(2log2). We ask what changes when, in addition to the length, aggregate information about the repetition pattern is revealed. We model this by fixing a second additive profile V_k=∑_i v(J_i) at scale V_k/n≈ρ. For v(j)=log(j!), the profile records the reduction in the logarithm of the number of compatible words caused by repetitions; we show that once the normalized profile ρ exceeds 0.507834…, the limiting optimal fraction is pinned at 1/2. For a typical multiplicity profile at the optimal support above this threshold, the excess in V_k is carried by a vanishing fraction of used symbols. We interpret this as a form of non-equivalence of ensembles and extend the mechanism to other profiles and non-uniform allocation models.
ER  -