# Dresden 2020 – wissenschaftliches Programm

# Die DPG-Frühjahrstagung in Dresden musste abgesagt werden! Lesen Sie mehr ...

## Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

# SOE: Fachverband Physik sozio-ökonomischer Systeme

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

### SOE 10.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 Krabbe^{1}, •Hendrik Schawe^{1,2}, and Alexander K. Hartmann^{1} — ^{1}Carl von Ossietzky Universität Oldenburg, Germany — ^{2}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^{−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)