{"entities":{"Q1825525":{"pageid":1836267,"ns":120,"title":"Item:Q1825525","lastrevid":69246231,"modified":"2026-04-13T05:44:28Z","type":"item","id":"Q1825525","labels":{"en":{"language":"en","value":"Lower bounds for covering times for reversible Markov chains and random walks on graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4121162"}},"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":"Q1825525$CCCBC894-FA1D-4AC3-86A4-6AE0A9B895D1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9b1eb8e4ee0b3b0f40e4ffc0fff5143eb85e026e","datavalue":{"value":{"text":"Lower bounds for covering times for reversible Markov chains and random walks on graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1825525$AB8AEE12-51AF-4D66-B497-BD4B59BFB884","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d9d46aab945f9d0571775c42cf29184a535a7c92","datavalue":{"value":"0684.60055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825525$2908ED70-5E02-4FC1-BA12-7B26C702476B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b5db605dfe6e8b4230bb2c48fb8da508dabfdffe","datavalue":{"value":"10.1007/BF01048272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825525$87923367-6836-4928-8EC9-5B4A5FC4E58F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0767dbe907f2b468d0869434c8ff22ebf5cc56e0","datavalue":{"value":{"entity-type":"item","numeric-id":189069,"id":"Q189069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825525$E36D537B-7980-4C83-94D9-F1F4D2028BD8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1825525$C5EEB9EF-9C1C-4867-BC5E-1B849C661B9A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"561825648042ae00eb810b01b9f0b3c8426bc5ec","datavalue":{"value":"For simple random walk on an N-vertex graph the mean time to cover all vertices is at least cN log N where c is an absolute constant. This result is deduced from a more general result about a lower bound for the mean coverage time for stationary finite-state reversible Markov chains, starting with the stationary distribution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825525$F2C3325D-F107-461E-B7ED-1C90F9CF39C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825525$5B84BD93-3C8D-4F4F-9926-E2BD23733CE5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db74c9b7ad034b5b8d212b4678ba4c79d5d6f07d","datavalue":{"value":"4121162","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825525$AFA470B1-6B11-4F01-BC36-F28981DCBECA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb78669d1e1fb8a3a19b3ab6cfa4ee987cacb82f","datavalue":{"value":"graph covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825525$64AC8C0D-3804-4DA5-81C6-664AC562ECAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29f90cd83dad24fc82d0e60664cc695c283ac5bf","datavalue":{"value":"random walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825525$AA7984C2-4B1D-412C-8727-958FF09ACBE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7053bf3f46a667a3df28524598e91bc6bda6cc7d","datavalue":{"value":"mean coverage time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825525$71F5B7E6-5C6E-4AAF-9E44-F803AFD152BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c7011df578cd2f611e416598389efb8a59ee84e","datavalue":{"value":"reversible Markov chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825525$24C97A55-92A3-4232-9D92-A8D2F1C9207B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85c9a1577f1cefb198cc5fea9807689b87b6a76d","datavalue":{"value":"stationary distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825525$1D53FF85-BF1C-4B96-9944-77E1D06FAD43","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a969a8b7a804be64a26f8df225f7e345032cb68d","datavalue":{"value":{"entity-type":"item","numeric-id":212984,"id":"Q212984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825525$491008FB-A4BE-4438-BEA0-82C5E51D8290","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4c568c5db1a8b15799638f8f459e7fd71ad7d2fe","datavalue":{"value":{"entity-type":"item","numeric-id":578831,"id":"Q578831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825525$71B1EA5B-2FB1-498B-A324-95ACBCAC26EA","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":"Q1825525$AE14BAF3-1CF7-43BE-A84E-197DA7EA4CA9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"db7e66a0379463f93fad07e8e97cb87d9a671811","datavalue":{"value":{"entity-type":"item","numeric-id":4153377,"id":"Q4153377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825525$0C04239F-DAA0-4F3C-B083-54093AAA793A","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":"Q1825525$655C65A9-ABE7-40E3-8DCC-06BD33533D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6745d4fc9f23d341e68a8f560771cdaba6a08b98","datavalue":{"value":{"entity-type":"item","numeric-id":3950588,"id":"Q3950588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825525$628A1899-DF68-4BE3-9A2A-8C614F181B7D","rank":"normal"}],"P1643":[{"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":"132ffeb1f0142a92a7f4bcb29c65388f594564ab","datavalue":{"value":{"amount":"+0.8778620958328247","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":"Q1825525$9BA2C670-6DB4-450A-AEE3-38D78D33358B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2848df0514908f7150c8a2efa1358b0c35ce5ff4","datavalue":{"value":{"entity-type":"item","numeric-id":1823547,"id":"Q1823547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0089ddf3bcd3f42a79cbe399f6559d27f795695b","datavalue":{"value":{"amount":"+0.858899712562561","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":"Q1825525$C906DB52-C1E0-4A8F-ADC3-D173FB5036E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6ef3299f0bec7a7388b50138edb47c712396d33","datavalue":{"value":{"entity-type":"item","numeric-id":3989014,"id":"Q3989014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"827e291572a97224fd58b1167c05854270ffbb20","datavalue":{"value":{"amount":"+0.8547634482383728","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":"Q1825525$656F2130-55FE-481C-8572-2E1D3D8B812F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15e02200f43c427330b90c1f459e677a195d245b","datavalue":{"value":{"entity-type":"item","numeric-id":1198987,"id":"Q1198987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f3d51bb0aeea10f6c072c9e464e2a3a9070b624","datavalue":{"value":{"amount":"+0.8546590209007263","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":"Q1825525$FF2372D8-73F7-46E0-8CBC-9BE1908793A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b544b9644bd01466bcac30b5455f6e9d8dc0f338","datavalue":{"value":{"entity-type":"item","numeric-id":2638665,"id":"Q2638665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a08bf4c2bb8fc798a1e06d02473f3cc3bd08bf13","datavalue":{"value":{"amount":"+0.8489488959312439","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":"Q1825525$58962090-14EE-4DC6-BCF3-2836A944ED61","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for covering times for reversible Markov chains and random walks on graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_covering_times_for_reversible_Markov_chains_and_random_walks_on_graphs"}}}}}