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 sequencesPhil Krabbe1, •Hendrik Schawe1,2, and Alexander K. Hartmann11Carl 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)

100% | Bildschirmansicht | English Version | Kontakt/Impressum/Datenschutz
DPG-Physik > DPG-Verhandlungen > 2020 > Dresden