{"entities":{"Q2279090":{"pageid":2289833,"ns":120,"title":"Item:Q2279090","lastrevid":57829116,"modified":"2026-04-02T17:17:46Z","type":"item","id":"Q2279090","labels":{"en":{"language":"en","value":"Slowdown for the geodesic-biased random walk"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7142644"}},"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":"Q2279090$43211E22-705C-41AD-B08C-95B39888C874","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b7a9a859e9c9db22924584cf720dc280c5000904","datavalue":{"value":{"text":"Slowdown for the geodesic-biased random walk","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2279090$2EB72013-9536-4FFD-AB74-5741E0736732","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4ceb1a81999bb35fb62591349d20d26b475e0e5d","datavalue":{"value":"1448.60096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2279090$B6DE05AC-B047-4CE1-ADE5-B9725486FE28","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"57e05e6faa696c798907d8223a46c0e1d508601e","datavalue":{"value":"10.1214/19-ECP276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2279090$3825F3D0-4B97-474E-BFCF-DEC2BDB22C06","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c267f372751a4852171b458af726a9f1282d6423","datavalue":{"value":{"entity-type":"item","numeric-id":2279088,"id":"Q2279088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$310EEAE3-9E68-401A-A13D-5A5A57C89E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb9dab9753d74571beabea6a2a6d998dc956d689","datavalue":{"value":{"entity-type":"item","numeric-id":2279089,"id":"Q2279089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$2A3ED236-FCF0-4C3F-9E83-C583C0F58319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e64191a192594be50c0f47da0c78dc27125eff50","datavalue":{"value":{"entity-type":"item","numeric-id":2037572,"id":"Q2037572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$84FDA4D8-BF68-4F5E-AFA4-2F0821BFA08F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1530c3f11f279ff941934a2442d3915c1a03734e","datavalue":{"value":{"entity-type":"item","numeric-id":402595,"id":"Q402595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$9A7AA316-ACA5-4D80-9DD1-A4A676AF4AB2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f68eb9de5f4e69a3d49dfc41c006f96a150ae946","datavalue":{"value":{"entity-type":"item","numeric-id":187954,"id":"Q187954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$FC4F121A-5185-4D5B-A9F4-5FD52C212FD9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b59fb3af1fc435d619b3c51ed9fbb031a0316176","datavalue":{"value":{"time":"+2019-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2279090$AC803A3B-B662-42EB-855E-4B528B2E3C09","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"93deef8626c18fbf5627f51527086e68be3da7ca","datavalue":{"value":"https://arxiv.org/abs/1909.05616","type":"string"},"datatype":"url"},"type":"statement","id":"Q2279090$0F493D50-D80B-4D15-B851-FCCAE4580B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"04b24b32b05c9dcfacb0d05d82061be958500358","datavalue":{"value":"https://projecteuclid.org/euclid.ecp/1573722086","type":"string"},"datatype":"url"},"type":"statement","id":"Q2279090$35A6F747-8655-437C-8925-18817E0EF5B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9bf397c76a1863ff972fc9c3a712b18066f4806e","datavalue":{"value":"Let \\(G\\) be a connected graph with \\(n\\) vertices. The \\emph{geodesic-biased random walk on \\(G\\)} is a Markov process on the vertices of \\(G\\) constructed as follows. A target vertex \\(b\\) is defined, as well as a set \\(\\mathcal{X}\\) of vertices of \\(G\\) which are considered exited. When at a non-exited vertex, the geodesic-biased random walk jumps to a neighbour chosen uniformly at random, whereas on an exited vertex, the walker jumps to a neighbour on a geodesic path towards the target vertex.  The aim of this article is to show that, perhaps counter-intuitively, the expected hitting time of the target vertex \\(b\\) by the geodesic-biased random walker can be significantly larger than in a regular random walk. Recall that in a graph of \\(n\\) vertices with bounded degree, the expected hitting time of a target vertex is at most of order \\(n^2\\). In this article, the authors construct explicitly a sequence of graphs with \\(n\\) vertices and only one excited vertex such that the expected hitting time of the target vertex is of order \\(\\exp(\\frac{n^{1/4} \\log n}{100})\\) as \\(n \\to \\infty\\). They also construct a sequence of graphs with \\(n\\) vertices and degree bounded by \\(3\\), among which \\(O(n^{1/2})\\) are exited vertices, such that the expected hitting time of the target vertex is of order \\(\\exp(\\frac{n^{1/4}}{100})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2279090$378BBC97-78BA-4B06-85BF-4B974DD2D3AC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"855e24edaaac44cf527f28570ed1d202b9908b00","datavalue":{"value":{"entity-type":"item","numeric-id":492962,"id":"Q492962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$E9B8C8C7-9082-4C22-908E-BEB760A9EF47","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2279090$82090418-EBD3-47F9-81BC-D28C26A7FCE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2279090$5C550A87-601C-40B4-80FD-90B591B2D3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2279090$EF83E6B3-1964-434E-A8F7-F4E085E7CA03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c0953b5e5decb2179a4ae7032cdc92dc3c1153eb","datavalue":{"value":"7142644","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2279090$69997E20-EC0C-4B2A-A4DA-5C6B9784FD57","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"250c314aca40fc28a3cad7b4f09b3614850781b8","datavalue":{"value":"excited random walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q2279090$1E60EE85-948D-4EBC-85D7-2B722411E9A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"672110074645f96af6e03f97b2cfc2a8cbea3dc4","datavalue":{"value":"hitting times","type":"string"},"datatype":"string"},"type":"statement","id":"Q2279090$CB83BCB1-CBDD-4B7F-BAED-E9C693D514FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f4db39ad1b340194847d2c2d751c8c931bd34d2","datavalue":{"value":"slowdown estimates","type":"string"},"datatype":"string"},"type":"statement","id":"Q2279090$3AEEF8E7-2413-4F98-9DF5-317102FDA778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d2e7ff13e7d44015f5295336f9fd3856ce22e6f","datavalue":{"value":"random walk on a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2279090$44B80B4B-6F9D-4682-B8FE-70E9DF3EFE24","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":"Q2279090$6AE8B346-D912-4617-A302-87A72084EEC2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb8ba2cc0064c21954f70b2532232a4acd49bcd5","datavalue":{"value":{"entity-type":"item","numeric-id":2464669,"id":"Q2464669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$468CA8C8-8655-47AF-BF78-36746C5C632E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12d114c365f8646d44856046ae20c353f0c7dd55","datavalue":{"value":{"entity-type":"item","numeric-id":533991,"id":"Q533991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$74934785-E892-4461-93B6-04D4A34FCEB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e7992c9ac75979f6b2ed480e1f7f272d2096b3","datavalue":{"value":{"entity-type":"item","numeric-id":1768199,"id":"Q1768199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$FACBB9CA-514D-40AD-971C-CCEFA788B714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63d29fabc400904e8238e1d9a684125bb265caae","datavalue":{"value":{"entity-type":"item","numeric-id":5009618,"id":"Q5009618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$0C78DBF0-9477-4970-A47C-82AFD92C032A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"811d4bda40df58c780094e7d88fc1d17348ebf90","datavalue":{"value":{"entity-type":"item","numeric-id":3970909,"id":"Q3970909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$8E84610C-0F85-40A2-9BAA-0D355B80CC64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"493aaeb6c819cf548d05812c57723379031b2e98","datavalue":{"value":{"entity-type":"item","numeric-id":5176212,"id":"Q5176212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$C39E18FD-FB19-4DD4-936B-B8A26226D4B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"491ed57dc72a485692e13596a129847d61cc9f1d","datavalue":{"value":{"entity-type":"item","numeric-id":2517269,"id":"Q2517269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$954F7003-313B-4C10-AE17-882AAE6D9A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14ff52114b742ba734585af51baa6f8c06b0151e","datavalue":{"value":{"entity-type":"item","numeric-id":5747111,"id":"Q5747111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$B4D24F29-9630-4239-97D2-E599997E2322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0428f81d29efcdd8e60b399e22b35703a55c0346","datavalue":{"value":{"entity-type":"item","numeric-id":1080258,"id":"Q1080258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$1BB1208D-6AF4-48ED-9925-0B72676873CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8aec64cd0492c9814270adc8e3c5f4a3f5555c88","datavalue":{"value":{"entity-type":"item","numeric-id":980761,"id":"Q980761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$3B381C8E-0D1F-4FA5-A847-386042B51EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a105c421e5b8345ea325a5c23e21e658343323a","datavalue":{"value":{"entity-type":"item","numeric-id":456188,"id":"Q456188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$E8F9B4F5-D101-419F-8909-2EF59238B768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b5ddaec573ec13aed0252f5af0e66654442e171","datavalue":{"value":{"entity-type":"item","numeric-id":2512842,"id":"Q2512842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$B411C00E-D518-4ECF-B967-D5C472ACA0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f949b47bcb830f633a7943a989c4567419ba6282","datavalue":{"value":{"entity-type":"item","numeric-id":2515939,"id":"Q2515939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$BB7FC64F-05DA-415D-8EF4-2A82013E830F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b6be21b31e605414524e5b416543d0a86e8705c","datavalue":{"value":{"entity-type":"item","numeric-id":338070,"id":"Q338070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$48BCBEBA-81D2-44B1-AED8-9FB7EBEFAF18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9cb50bdf35c0dd864897876c2346eccc56dad84","datavalue":{"value":{"entity-type":"item","numeric-id":2570836,"id":"Q2570836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2279090$1D1A8C04-2EC6-4F71-98C8-5180066D75C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d4705d755254f57949bb81e2d22e63bc6fc9f36f","datavalue":{"value":"W2984624435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2279090$64BC9C45-B733-4446-9246-36424861F70F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"788155bfee90ade7e9f0750b1c13779604a91ffc","datavalue":{"value":{"entity-type":"item","numeric-id":2449093,"id":"Q2449093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da87bd04108fe21ee60785280638b83fbb9f1b1c","datavalue":{"value":{"amount":"+0.7965494394302368","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":"Q2279090$21C25D66-89FD-4317-8B91-4EB43A7389F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf69bcae2f7999cef8576878806a07e568543293","datavalue":{"value":{"entity-type":"item","numeric-id":3970909,"id":"Q3970909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e1a604038008fa533943ad7a3222e73fc32bee4","datavalue":{"value":{"amount":"+0.7414358258247375","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":"Q2279090$5DD7E583-55D6-494C-86E8-163B7C0A00C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d734ef60a1f121b3916fb6ec9b6ff55d6a8d699","datavalue":{"value":{"entity-type":"item","numeric-id":1080258,"id":"Q1080258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95c64852465c31f2ba73a2d45be2ed3a25b1aa19","datavalue":{"value":{"amount":"+0.7407820224761963","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":"Q2279090$27308C6F-0B54-4FF7-8B18-8D6BF70220E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d6f499ef8d9fbd2db7519d3fd1349a10b52607e","datavalue":{"value":{"entity-type":"item","numeric-id":922556,"id":"Q922556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0626d6c1e92e55bef7dde9a519965cab052f5bf","datavalue":{"value":{"amount":"+0.7407099604606628","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":"Q2279090$B2541600-41C4-4434-AA01-1FD10654DAD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c3ddaa34f225949f1fb5068f985b34af7197df5","datavalue":{"value":{"entity-type":"item","numeric-id":1849735,"id":"Q1849735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8f04ff92348c597ebc0c8b435e421dea552f6b8","datavalue":{"value":{"amount":"+0.7400206327438354","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":"Q2279090$40B50696-DA99-4A70-BDBA-716ECFA043A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2279090","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2279090"}}}}}