{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T09:11:27Z","timestamp":1759741887689},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T00:00:00Z","timestamp":1604534400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Drift analysis is one of the state-of-the-art techniques for the runtime analysis of randomized search heuristics (RSHs) such as evolutionary algorithms (EAs), simulated annealing,<jats:italic>etc<\/jats:italic>. The vast majority of existing drift theorems yield bounds on the expected value of the hitting time for a target state, for example the set of optimal solutions, without making additional statements on the distribution of this time. We address this lack by providing a general drift theorem that includes bounds on the upper and lower tail of the hitting time distribution. The new tail bounds are applied to prove very precise sharp-concentration results on the running time of a simple EA on standard benchmark problems, including the class of general linear functions. On all these problems, the probability of deviating by an<jats:italic>r<\/jats:italic>-factor in lower-order terms of the expected time decreases exponentially with<jats:italic>r<\/jats:italic>. The usefulness of the theorem outside the theory of RSHs is demonstrated by deriving tail bounds on the number of cycles in random permutations. All these results handle a position-dependent (variable) drift that was not covered by previous drift theorems with tail bounds. Finally, user-friendly specializations of the general drift theorem are given.<\/jats:p>","DOI":"10.1017\/s0963548320000565","type":"journal-article","created":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T09:08:01Z","timestamp":1604567281000},"page":"550-569","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":17,"title":["Tail bounds on hitting times of randomized search heuristics using variable drift analysis"],"prefix":"10.1017","volume":"30","author":[{"given":"P. K.","family":"Lehre","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Witt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,11,5]]},"reference":[{"key":"S0963548320000565_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.08.021"},{"key":"S0963548320000565_ref21","unstructured":"[21] Johannsen, D. (2010) Random combinatorial structures and randomized search heuristics. PhD thesis, Universit\u00e4t des Saarlandes, Germany."},{"key":"S0963548320000565_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0048-0"},{"key":"S0963548320000565_ref15","doi-asserted-by":"publisher","DOI":"10.2307\/1426671"},{"key":"S0963548320000565_ref40","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000600"},{"key":"S0963548320000565_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"S0963548320000565_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4"},{"key":"S0963548320000565_ref13","first-page":"65","volume-title":"Proceedings of Foundations of Genetic Algorithms (FOGA 2013)","author":"Feldmann","year":"2013"},{"key":"S0963548320000565_ref27","first-page":"1239","volume-title":"Companion to GECCO 2012","author":"Lehre","year":"2012"},{"key":"S0963548320000565_ref38","doi-asserted-by":"crossref","unstructured":"[38] Sudholt, D. (2013) A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17 418\u2013435.","DOI":"10.1109\/TEVC.2012.2202241"},{"key":"S0963548320000565_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964899134016"},{"key":"S0963548320000565_ref32","doi-asserted-by":"publisher","DOI":"10.1108\/17563780910959893"},{"key":"S0963548320000565_ref22","doi-asserted-by":"publisher","DOI":"10.1145\/195613.195632"},{"key":"S0963548320000565_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3"},{"key":"S0963548320000565_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4"},{"key":"S0963548320000565_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/2908812.2908891"},{"key":"S0963548320000565_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4_5"},{"key":"S0963548320000565_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9387-z"},{"key":"S0963548320000565_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9396-y"},{"key":"S0963548320000565_ref26","first-page":"244","volume-title":"Proceedings of Parallel Problem Solving from Nature (PPSN 2010)","author":"Lehre","year":"2011"},{"key":"S0963548320000565_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9585-3"},{"key":"S0963548320000565_ref37","doi-asserted-by":"publisher","DOI":"10.1145\/42282.46160"},{"key":"S0963548320000565_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000275"},{"key":"S0963548320000565_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.06.014"},{"key":"S0963548320000565_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00058-3"},{"key":"S0963548320000565_ref35","unstructured":"[35] Oliveto, P. S. and Witt, C. (2012) Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation. arXiv:1211.7184"},{"key":"S0963548320000565_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0360-y"},{"key":"S0963548320000565_ref36","first-page":"1349","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012)","author":"Rowe","year":"2012"},{"key":"S0963548320000565_ref28","first-page":"686","volume-title":"Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014)","author":"Lehre","year":"2014"},{"key":"S0963548320000565_ref39","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/3-540-48224-5_6","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001)","author":"Wegener","year":"2001"},{"key":"S0963548320000565_ref17","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00212"},{"key":"S0963548320000565_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-012-9305-y"},{"key":"S0963548320000565_ref29","unstructured":"[29] Lehre, P. K. and Witt, C. (2018) General drift analysis with tail bounds. Preprint of this paper, including supplementary material. arXiv:1211.7184"},{"key":"S0963548320000565_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00182-7"},{"key":"S0963548320000565_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9622-x"},{"key":"S0963548320000565_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/2463372.2463565"},{"key":"S0963548320000565_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989707"},{"key":"S0963548320000565_ref2","doi-asserted-by":"publisher","DOI":"10.1142\/7438"},{"key":"S0963548320000565_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58115-2_45"},{"key":"S0963548320000565_ref6","first-page":"2083","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011)","author":"Doerr","year":"2011"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T14:13:35Z","timestamp":1697033615000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000565\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,5]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["S0963548320000565"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000565","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,5]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}