Optimal support and condensation in random allocations

Andrea Ottolini

In the authors' words

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 \to 1/ (2 lo g 2)$ . 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} = \sum_{i} v (J_{i})$ at scale $V_{k} / n \approx ρ$ . For $v (j) = lo g (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 \dots$ , 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.

Main resultThe abstract does not state a limitation.

Optimal support and condensation in random allocations

In the authors' words

More on Probability that day

Feedback Coding Enables Inference-Time Covert Agentic Communication

The quasi-isometry classes of Galton--Watson trees

Interference-Free Capacity of a Binary Interference Channel with Causal Observation

Directed distances in spanning-tree-decorated planar maps: exact exponent, scaling limit and universality

Compressible stochastic fluid--structure interaction with transport noise and Navier slip: A stochastic-flow approach