Dresden 2020 – scientific programme

The DPG Spring Meeting in Dresden had to be cancelled! Read more ...

Parts | Days | Selection | Search | Updates | Downloads | Help

DY: Fachverband Dynamik und Statistische Physik

DY 40: Data Analytics, Extreme Events, and Nonlinear Stochastic Systems (joint session DY/SOE)

DY 40.4: Talk

Wednesday, March 18, 2020, 16:00–16:15, ZEU 118

The entropy of the longest increasing subsequences: typical and extreme sequences — Phil Krabbe¹, •Hendrik Schawe^1,2, and Alexander K. Hartmann¹ — ¹Carl von Ossietzky Universität Oldenburg, Germany — ²Laboratoire 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⁻¹⁰⁰ 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)