{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:43:59Z","timestamp":1775054639346,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:00:00Z","timestamp":1604016000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:00:00Z","timestamp":1604016000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hasso-Plattner-Institut f\u00fcr Digital Engineering gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Drift analysis aims at translating the expected progress of an evolutionary algorithm (or more generally, a random process) into a probabilistic guarantee on its run time (hitting time). So far, drift arguments have been successfully employed in the rigorous analysis of evolutionary algorithms, however, only for the situation that the progress is constant or becomes weaker when approaching the target. Motivated by questions like how fast fit individuals take over a population, we analyze random processes exhibiting a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\delta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-multiplicative growth in expectation. We prove a drift theorem translating this expected progress into a hitting time. This drift theorem gives a simple and insightful proof of the level-based theorem first proposed by Lehre (2011). Our version of this theorem has, for the first time, the best-possible near-linear dependence on <jats:inline-formula><jats:alternatives><jats:tex-math>$$1\/\\delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (the previous results had an at least near-quadratic dependence), and it only requires a population size near-linear in\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b4<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (this was super-quadratic in previous results). These improvements immediately lead to stronger run time guarantees for a number of applications. We also discuss the case of large <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b4<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and show stronger results for this setting.<\/jats:p>","DOI":"10.1007\/s00453-020-00775-7","type":"journal-article","created":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T16:06:53Z","timestamp":1604074013000},"page":"3017-3058","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Multiplicative Up-Drift"],"prefix":"10.1007","volume":"83","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"K\u00f6tzing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,30]]},"reference":[{"key":"775_CR1","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Yang, Q.: The efficiency threshold for the offspring population size of the (\u03bc, \u03bb) EA. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1461\u20131469. ACM (2019)","DOI":"10.1145\/3321707.3321838"},{"key":"775_CR2","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","volume":"22","author":"D Corus","year":"2018","unstructured":"Corus, D., Dang, D.-C., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. IEEE Trans. Evol. Comput. 22 707\u2013719 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"775_CR3","doi-asserted-by":"crossref","unstructured":"Colin, S., Doerr, B., F\u00e9rey, G.: Monotonic functions in EC: anything but monotone! In: Genetic and Evolutionary Computation Conference, GECCO 2014, pp. 753\u2013760. ACM (2014)","DOI":"10.1145\/2576768.2598338"},{"key":"775_CR4","doi-asserted-by":"publisher","first-page":"1658","DOI":"10.1007\/s00453-017-0354-9","volume":"80","author":"B Doerr","year":"2018","unstructured":"Doerr, B., Doerr, C.: Optimal static and self-adjusting parameter choices for the (1 + \u03bb, \u03bb) genetic algorithm. Algorithmica 80, 1658\u20131709 (2018)","journal-title":"Algorithmica"},{"key":"775_CR5","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65, 224\u2013250 (2013)","journal-title":"Algorithmica"},{"key":"775_CR6","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"775_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2014.03.015","volume":"561","author":"B Doerr","year":"2015","unstructured":"Doerr, B., K\u00fcnnemann, M.: Optimizing linear functions with the (1 + \u03bb) evolutionary algorithm\u2013different asymptotic runtimes for different instances. Theoret. Comput. Sci. 561, 3\u201323 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"775_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B., K\u00f6tzing, T.: Multiplicative up-drift. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1470\u20131478. ACM (2019)","DOI":"10.1145\/3321707.3321819"},{"key":"775_CR9","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","volume":"75","author":"D-C Dang","year":"2016","unstructured":"Dang, D.-C., Lehre, P.K.: Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica 75, 428\u2013461 (2016)","journal-title":"Algorithmica"},{"key":"775_CR10","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1007\/s00453-018-0507-5","volume":"81","author":"D-C Dang","year":"2019","unstructured":"Dang, D.-C., Lehre, P.K., Nguyen, P.T.H.: Level-based analysis of the univariate marginal distribution algorithm. Algorithmica 81, 668\u2013702 (2019)","journal-title":"Algorithmica"},{"key":"775_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.spl.2018.03.016","volume":"139","author":"B Doerr","year":"2018","unstructured":"Doerr, B.: An elementary analysis of the probability that a binomial random variable exceeds its expectation. Stat. Probab. Lett. 139, 67\u201374 (2018)","journal-title":"Stat. Probab. Lett."},{"key":"775_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2018.09.024","volume":"773","author":"B Doerr","year":"2019","unstructured":"Doerr, B.: Analyzing randomized search heuristics via stochastic domination. Theoret. Comput. Sci. 773, 115\u2013137 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"775_CR13","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Benjamin, D., Frank, N., (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 1\u201387. Springer (2020). arXiv: org\/abs\/1801.06733","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"775_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B., Zheng, W.: Sharp bounds for genetic drift in estimation-of-distribution algorithms. In: IEEE Transactions on Evolutionary Computation (2020). To appear","DOI":"10.1145\/3377929.3397489"},{"key":"775_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/EJP.v20-3496","volume":"20","author":"X Fan","year":"2015","unstructured":"Fan, X., Grama, I., Liu, Q.: Exponential inequalities for martingales with applications. Electron. J. Probab. 20, 1\u201322 (2015)","journal-title":"Electron. J. Probab."},{"key":"775_CR16","doi-asserted-by":"crossref","unstructured":"Gie\u00dfen, C., K\u00f6tzing, T.: Robustness of populations in stochastic environments. In: Genetic and Evolutionary Computation Conference, GECCO 2014, pp. 1383\u20131390. ACM (2014)","DOI":"10.1145\/2576768.2598227"},{"key":"775_CR17","unstructured":"G\u00f6bel, A., K\u00f6tzing, T., Krejca, M.S.: Intuitive analyses via drift theory. CoRR. arxiv:1806.01919 (2018)"},{"key":"775_CR18","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.spl.2013.12.009","volume":"86","author":"S Greenberg","year":"2014","unstructured":"Greenberg, S., Mohri, M.: Tight lower bound on the probability of a binomial exceeding its expectation. Stat. Probab. Lett. 86, 91\u201398 (2014)","journal-title":"Stat. Probab. Lett."},{"key":"775_CR19","volume-title":"Probability and Random Processes","author":"RG Geoffrey","year":"2001","unstructured":"Geoffrey, R.G., David, R.S.: Probability and Random Processes. Oxford University Press, Oxford (2001)"},{"key":"775_CR20","doi-asserted-by":"crossref","unstructured":"Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitness-proportional selection for optimizing linear functions. In: Genetic and Evolutionary Computation Conference, GECCO 2008, pp. 953\u2013960. ACM (2008)","DOI":"10.1145\/1389095.1389277"},{"key":"775_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0004-3702(01)00058-3","volume":"127","author":"J He","year":"2001","unstructured":"He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 57\u201385 (2001)","journal-title":"Artif. Intell."},{"key":"775_CR22","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1023\/B:NACO.0000023417.31393.c7","volume":"3","author":"J He","year":"2004","unstructured":"He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Nat. Comput. 3, 21\u201335 (2004)","journal-title":"Nat. Comput."},{"key":"775_CR23","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.tcs.2007.02.042","volume":"379","author":"J J\u00e4gersk\u00fcpper","year":"2007","unstructured":"J\u00e4gersk\u00fcpper, J.: Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theoret. Comput. Sci. 379, 329\u2013347 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"775_CR24","doi-asserted-by":"crossref","unstructured":"Jansen, T.: On the brittleness of evolutionary algorithms. In: Foundations of Genetic Algorithms, FOGA 2007, pp. 54\u201369. Springer (2007)","DOI":"10.1007\/978-3-540-73482-6_4"},{"key":"775_CR25","unstructured":"Johannsen, D.: Random Combinatorial Structures and Randomized Search Heuristics. Ph.D. thesis, Universit\u00e4t des Saarlandes (2010). http:\/\/scidok.sulb.uni-saarland.de\/volltexte\/2011\/3529\/pdf\/Dissertation_3166_Joha_Dani_2010.pdf"},{"key":"775_CR26","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T.: Andrei Lissovoi, and Carsten Witt. (1+1) EA on generalized dynamic OneMax. In: Foundations of Genetic Algorithms, FOGA 2015, pp. 40\u201351. ACM (2015)","DOI":"10.1145\/2725494.2725502"},{"issue":"3","key":"775_CR27","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","volume":"75","author":"T K\u00f6tzing","year":"2016","unstructured":"K\u00f6tzing, T.: Concentration of first hitting times under additive drift. Algorithmica 75(3), 490\u2013506 (2016)","journal-title":"Algorithmica"},{"key":"775_CR28","unstructured":"Krejca, M.S.: Theoretical Analyses of Univariate Estimation-of-Distribution Algorithms. Ph.D. thesis, Universit\u00e4t Potsdam (2019)"},{"key":"775_CR29","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Fitness-levels for non-elitist populations. In: Genetic and Evolutionary Computation Conference, GECCO 2011, pp. 2075\u20132082. ACM (2011)","DOI":"10.1145\/2001576.2001855"},{"key":"775_CR30","doi-asserted-by":"crossref","unstructured":"Lengler, J.: Drift analysis. In: Benjamin, D., Frank, N., (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer (2020). https:\/\/arxiv.org\/abs\/1712.00964","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"775_CR31","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: Level-based analysis of the population-based incremental learning algorithm. In: Parallel Problems Solving From Nature, PPSN 2018, pp. 105\u2013116. Springer (2018)","DOI":"10.1007\/978-3-319-99259-4_9"},{"key":"775_CR32","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1108\/17563780910959893","volume":"2","author":"B Mitavskiy","year":"2009","unstructured":"Mitavskiy, B., Rowe, J.E., Cannings, C.: Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intell. Comput. Cybernet. 2, 243\u2013284 (2009)","journal-title":"Int. J. Intell. Comput. Cybernet."},{"key":"775_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"775_CR34","first-page":"29","volume":"19","author":"P Neumann","year":"1966","unstructured":"Neumann, P.: \u00dcber den Median der Binomial- and Poissonverteilung. Wissenschaftliche Zeitschrift der Technischen Universit\u00e4t Dresden 19, 29\u201333 (1966)","journal-title":"Wissenschaftliche Zeitschrift der Technischen Universit\u00e4t Dresden"},{"key":"775_CR35","doi-asserted-by":"crossref","unstructured":"Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Genetic and Evolutionary Computation Conference, GECCO 2009, pp. 835\u2013842. ACM (2009)","DOI":"10.1145\/1569901.1570016"},{"key":"775_CR36","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theoret. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"775_CR37","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1214\/aoms\/1177731235","volume":"15","author":"A Wald","year":"1944","unstructured":"Wald, A.: On cumulative sums of random variables. Ann. Math. Stat. 15, 283\u2013296 (1944)","journal-title":"Ann. Math. Stat."},{"key":"775_CR38","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Theoretical aspects of evolutionary algorithms. In: Automata, Languages and Programming, ICALP 2001, pp. 64\u201378. Springer (2001)","DOI":"10.1007\/3-540-48224-5_6"},{"key":"775_CR39","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1017\/S0963548304006650","volume":"14","author":"I Wegener","year":"2005","unstructured":"Wegener, I., Witt, C.: On the optimization of monotone polynomials by simple randomized search heuristics. Comb. Probab. Comput. 14, 225\u2013247 (2005)","journal-title":"Comb. Probab. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00775-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00775-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00775-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T15:32:07Z","timestamp":1633102327000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00775-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,30]]},"references-count":39,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["775"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00775-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,30]]},"assertion":[{"value":"28 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}