Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 10, 2022, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Johannes Lengler
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.
Automatic MiSe System Software Version 1.4803M | admin login