Die DPG-Frühjahrstagung in Dresden musste abgesagt werden! Lesen Sie mehr ...
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
DY: Fachverband Dynamik und Statistische Physik
DY 40: Data Analytics, Extreme Events, and Nonlinear Stochastic Systems (joint session DY/SOE)
DY 40.4: Vortrag
Mittwoch, 18. März 2020, 16:00–16:15, ZEU 118
The entropy of the longest increasing subsequences: typical and extreme sequences — Phil Krabbe1, •Hendrik Schawe1,2, and Alexander K. Hartmann1 — 1Carl von Ossietzky Universität Oldenburg, Germany — 2Laboratoire de Physique Théorique et Modèlisation, Université de Cergy-Pontoise, France
Consider a game, where you get a sequence of n numbers. Your objective is to circle the maximum amount of numbers such that each circled number is larger than all circled numbers to their left. To circle the maximum amount numbers, one can calculate the longest increasing subsequence (LIS). If the sequence of numbers is a random permutation, this problem is remarkably well studied and for the length L, or in our game the number of circles, not only the mean value, but the whole distribution is known [1,2]. In recent time it was shown that this problem is equivalent to certain surface growth and ballistic deposition models, which led to a large interest from physicists.
Note that the LIS is not unique, there are possibly multiple ways to circle L numbers. While this degeneracy M is expected to increase exponentially with the sequence length n [1], we introduce an algorithm to count the number of degenerate LIS and sample uniformly from all LIS of a given sequence. Especially, we obtain the distribution P(M) down into its far tails with probabilities smaller than 10−100 using sophisticated Markov chain sampling methods [3].
[1] D. Romik, The Surprising Mathematics of Longest Increasing Subsequences (2015); [2] J. Börjes, H. Schawe, A. K. Hartmann, Phys. Rev. E 99 (4), 042104 (2019); [3] A.K. Hartmann, EPJB 84, 627 (2011)