Dresden 2020 – scientific programme
The DPG Spring Meeting in Dresden had to be cancelled! Read more ...
Parts | Days | Selection | Search | Updates | Downloads | Help
SOE: Fachverband Physik sozio-ökonomischer Systeme
SOE 10: Data Analytics, Extreme Events, Nonlinear Stochastic Systems, and Networks (joint session DY/SOE)
SOE 10.4: Talk
Wednesday, March 18, 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)