Sökmönster av slumpmässigt orienterade steg av olika längder har observerats på alla skalor av den biologiska världen, allt från mikroskopiska till ekologiska, inklusive i proteinmotorer, bakterier, T-celler, honungsbin, marina rovdjur, med mera, se t.ex., [21, 22, 34, 36, 37, 38, 39]. Genom olika modeller har det visat sig att införandet av en mängd olika steglängder i hög grad kan förbättra sökeffektiviteten. Den exakta kopplingen mellan sökeffektiviteten och antalet steglängder i sökarens repertoar har dock inte identifierats. Motiverad av biologiska exempel i endimensionell terräng, studerade ett nyligen gjort papper den bästa omslagstiden på en n-node cykel som kan uppnås genom en slumpmässig gångprocess som använder k steglängder [8]. Genom att ställa in längder och motsvarande sannolikheter visade författarna däri att den bästa omslagstiden är ungefär n 1+ och (1/k). Även om denna gräns är användbar för stora värden av k, är det knappast informativt för små k värden, som är av intresse för biologi [2, 4, 27, 33]. I detta papper ger vi en snäv gräns för omslaget tiden för en sådan promenad, för varje heltal k > 1. Särskilt, upp till lägre order polylogaritmiska faktorer, är täcktiden n 1+ 1 2k−1. För k = 2, 3, 4 och 5 är gränsen alltså n 4/3, n 6/5, n 8/7, och n 10/9, respektive. Informellt innebär vårt resultat att så länge som antalet steglängder k inte är för stort, med en ytterligare steglängd till repertoaren av processen gör det möjligt att förbättra täckningstiden med en polynom faktor, men omfattningen av förbättringen gradvis minskar med k.
I REF visade författarna till den aktuella tidningen att, upp till lägre ordertermer, n 1+ 1 2k‐1 är en snäv gräns för omslaget tiden av cykeln genom den bästa slumpmässiga gångprocessen som använder k steg-längder.
Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Biology']}