{"entities":{"Q6670804":{"pageid":14281961,"ns":120,"title":"Item:Q6670804","lastrevid":55832965,"modified":"2026-02-17T23:37:44Z","type":"item","id":"Q6670804","labels":{"en":{"language":"en","value":"Linear cover time is exponentially unlikely"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7974365"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$85F3A2A1-81AA-42A9-8348-B83675296BA0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d0c338d334913d78d6f76f4ee5e3fa5c676a702a","datavalue":{"value":{"text":"Linear cover time is exponentially unlikely","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6670804$D5E48031-2C66-495A-BAFD-9C448ACC563E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e293a91db70b677cf3795781cef795baeda073a","datavalue":{"value":{"entity-type":"item","numeric-id":5854462,"id":"Q5854462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$B4AEDA52-15E0-47E1-8EA9-4829AF7D041E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1a8b239d5a7f549910817e61d8809ac746dac16","datavalue":{"value":{"entity-type":"item","numeric-id":762169,"id":"Q762169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$BDA0448D-B92B-45B7-B8B1-80344A13CA07","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c9d829dece3e2d330deed49a6cb836edc666e294","datavalue":{"value":{"entity-type":"item","numeric-id":107063,"id":"Q107063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$6CF50F01-CE70-4E65-B526-89DC95BE51CD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"80b205d07bea2ab271294e7a9fbb7ed69b706f14","datavalue":{"value":{"time":"+2025-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6670804$B6F9ED3A-CF3D-4F8A-AFD8-46454E815E5F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2e1867d25333621c785a05d83f82b5776c28cd8d","datavalue":{"value":"The article answers positively a longstanding conjecture of Benjamini (2009) that linear cover time is exponentially unlikely for random walks on graphs.\\N\\N\\textbf{Theorem.} For any \\(C > 0\\), there is an \\(\\varepsilon > 0\\) such that, for any simple graph \\(G\\) on a vertex set \\(V\\) with \\(n\\) vertices, if \\((X_t)_{t\\ge0}\\) is the usual simple random walk on \\(G\\), then\\N\\[\\N\\mathbb P\\bigl( \\{X_t\\}_{t=0}^{Cn} = V \\bigr) \\le e^{-\\varepsilon n}.\\N\\]\\N\\textit{I. Benjamini} et al. [Probab. Theory Relat. Fields 155, No. 1--2, 451--461 (2013; Zbl 1259.05154)] proved this when the maximum degree \\(\\Delta\\) of \\(G\\) is bounded -- with \\(\\varepsilon\\) depending on \\(\\Delta\\). \\textit{A. Yehudayoff} [Chic. J. Theor. Comput. Sci. 2012, Article No. 3, 6 p. (2012; Zbl 1286.05160)] proved it for trees, as well as observing that it holds for expanders from the large-deviation bound for random walks due to \\textit{D. Gillman} [SIAM J. Comput. 27, No. 4, 1203--1220 (1998; Zbl 0911.60016)].\\N\\NWith some minor adjustments, Dubroff and Kahn can show that, for any \\(C > 0\\), there exist \\(\\varepsilon, \\alpha > 0\\) such that\\N\\[\\N\\mathbb P\\bigl( \\bigl|\\{X_t\\}_{t=0}^{Cn}\\bigr| \\ge (1 - \\alpha) n \\bigr) \\le e^{-\\varepsilon n}.\\N\\]\\NThe majority of their work generalises from random walks to general reversible chains -- which can be viewed as \\textit{weighted} random walks.\\N\\N\\textbf{Theorem.} Let \\((X_t)_{t\\ge0}\\) be a reversible Markov chain on \\(V\\), with \\(|V| = n\\), with equilibrium distribution \\(\\pi\\). Suppose that there exists a subset \\(W \\subseteq V\\) with \\(|W| \\ge \\alpha n\\) such that \\(\\pi_v / \\pi_w \\le K\\) for all \\(v,w \\in W\\). Then,\\N\\[\\N\\mathbb P\\bigl( \\{X_t\\}_{t=0}^{Cn} = V \\bigr) \\le \\exp\\bigl( - \\Omega(n) \\bigr),\\N\\]\\Nwhere the implied constant depends on \\(C\\), \\(\\alpha\\) and \\(K\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6670804$2594F2F3-35D6-4E76-B126-4AAC5751381E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cbdbbeba883bfd452d57cd3abb49a921584c175c","datavalue":{"value":{"entity-type":"item","numeric-id":2028955,"id":"Q2028955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$7A3E8574-9FB4-4C92-BAAF-93EAE4A6FD54","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5b5126101ab4505674efcb5789319f63910d08f","datavalue":{"value":"05C81","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6670804$06ACFC13-B01C-439C-BEB2-D288EB6277DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6670804$CCB0E1B9-05FC-445A-9070-C7CFB14E92B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"314e54fbb18d33f780194e79b8f7d977d400cb90","datavalue":{"value":"60J05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6670804$166CFA4B-7828-43F0-B57D-67F679788AC2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7756b7e7ffee7b8a4a70c4b4f0f0e5a8b35b1ac5","datavalue":{"value":"7974365","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6670804$33650CAA-A16B-4E65-9AC0-ECD8F1CB8E41","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54386443767439a4565bd3fedc3d37d2c4a4f85d","datavalue":{"value":"Markov chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q6670804$60278727-F080-4CE6-B993-162D1A2150D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c84fc0d37b81c48fac237170dfbe1ece56cb50e3","datavalue":{"value":"random walks on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6670804$46C1244E-A4AA-453D-8520-A71ACC615022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ea82f361bc2e53f3f4b7676c1ab955297bc1c15","datavalue":{"value":"cover time","type":"string"},"datatype":"string"},"type":"statement","id":"Q6670804$86CF03A2-58DF-451D-A480-F1B63BDB5459","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$9840FD32-6B8F-4272-B0CE-85BD94F47849","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"060509cc375d6d3e0f4124aaee51fdd138a11af1","datavalue":{"value":{"entity-type":"item","numeric-id":1825525,"id":"Q1825525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$E5DE7C2D-F4C6-49BE-9B3C-890085F9F82E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdc15b269b44b1fbe6ceb7abd4728209de797595","datavalue":{"value":{"entity-type":"item","numeric-id":1939561,"id":"Q1939561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$11B8A6E7-5630-4A0A-8DC3-5BCFC6714C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68bbf8149e7111282351de87571af2948c0bb400","datavalue":{"value":{"entity-type":"item","numeric-id":2447331,"id":"Q2447331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$DDE05398-1B2A-4E97-8EC3-028DCDDEA24F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e1445a4e795e33691be5b9d3130a6adaec8e16b","datavalue":{"value":{"entity-type":"item","numeric-id":431644,"id":"Q431644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$D313889F-49A3-4A7E-9328-06A0DEEA0C90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4add356b145271b9757e772351bd3d4c25cdffd6","datavalue":{"value":{"entity-type":"item","numeric-id":4210091,"id":"Q4210091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$F45DA56C-382A-4042-9246-6EC01CF5DCA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76f98835e6f985f441b694d31322d18fce00bcfd","datavalue":{"value":{"entity-type":"item","numeric-id":1906118,"id":"Q1906118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$DE7B8DAC-C5A7-4850-AE8B-B219543FDD7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d738e694de5fb590baa9d0597ed26f0c2b51fbc6","datavalue":{"value":{"entity-type":"item","numeric-id":4076577,"id":"Q4076577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$46D49BDD-A541-4ED9-B596-6AE95B5227AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"912720a13d28229f567e09e063b6af9d00dd4cf5","datavalue":{"value":{"entity-type":"item","numeric-id":4595047,"id":"Q4595047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$E9C77BE7-ABA0-42C8-89DF-BDAB47DD3F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"115c5ecfdf490a436d3c22d9985fda8bfe039794","datavalue":{"value":{"entity-type":"item","numeric-id":4878667,"id":"Q4878667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$8346454D-2A6F-4519-9278-929E202A03BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb3059ae7bb817b98de7bddd0cb9377844ece374","datavalue":{"value":{"entity-type":"item","numeric-id":5414598,"id":"Q5414598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$80F0AEFA-79D1-4268-8872-BF756D5258C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c39b2b4591a0ec9659c1fc8589dab77d8013132","datavalue":{"value":{"entity-type":"item","numeric-id":1748936,"id":"Q1748936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6670804$F08CCED1-41F3-4278-AEE2-954D38F53248","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6e2ac614efe11a8bef545c92f5b830a2b7be4bcc","datavalue":{"value":"10.1214/24-AOP1699","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6670804$89AA30E9-D3AE-4BA0-B9A5-BF9E9609953C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c01d106159739562d04cf9c0d493529986d4f0b","datavalue":{"value":{"entity-type":"item","numeric-id":1939561,"id":"Q1939561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bbfbe51a0870ac26f14f285c566144ae9b829f1","datavalue":{"value":{"amount":"+0.9125831723213196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6670804$ACDC8491-97F2-4ED5-8663-922521404E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2f689b43787e6d94dd25c09bcea850e2664b302","datavalue":{"value":{"entity-type":"item","numeric-id":5414598,"id":"Q5414598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45b3eb0c46582ae3daa5ebb8fbed84bdf6405e46","datavalue":{"value":{"amount":"+0.8634439706802368","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6670804$8386B258-0ECA-43C1-832B-671C60E8A131","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f49380ad01ca7c4a1665978a9e0b35110f529e5","datavalue":{"value":{"entity-type":"item","numeric-id":1825525,"id":"Q1825525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63f324a190b668554b25fdb5d47bd1b2dfccab4f","datavalue":{"value":{"amount":"+0.8476123809814453","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6670804$0A10E768-68D1-4EE8-88B0-67F94A271B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1f4fb1b8fc99513eca83200d78628a44f7fe87f","datavalue":{"value":{"entity-type":"item","numeric-id":1823548,"id":"Q1823548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f709f5396b46068fd1a17dea4819eac38ca3fb0d","datavalue":{"value":{"amount":"+0.8180487751960754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6670804$92D4B495-FB3F-46C0-9D8D-98F0C1BD1C0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b2dc0678bfe6038deffa777d8715d8861232ee7","datavalue":{"value":{"entity-type":"item","numeric-id":3419608,"id":"Q3419608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"800f86aa0e6e671319f112e43ab89a74bfffb245","datavalue":{"value":{"amount":"+0.8111744523048401","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6670804$0CC0CA5F-F53C-4596-9C70-5EDFD2F3E587","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6670804","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6670804"}}}}}