## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, November 10, 2022, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Johannes Lengler

## Two-Dimensional Drift Analysis

I will discuss drift analysis in the case where we have a two-dimensional non-negative Markov chain X = (X_1,X_2) where the drift (= expected change) is essentially linear in X. More precisely, there is a 2x2 matrix A such that the drift is proportional to (1\pm o(1))A*X, where * here denotes a matrix-scalar product, and the factor (1\pm o(1)) is applied to all four summands of that product. We are interested in the hitting time of (0,0). I will show that this kind of processes allows a general solution that depends on the eigenvalues of A.
As motivation, I will present a minimal example of a dynamic environment which can be decpetive for evolutionary algorithms, thus answering a question by Emo Welzl.

Information for students and suggested topics for student talks