{"entities":{"Q406701":{"pageid":408468,"ns":120,"title":"Item:Q406701","lastrevid":56902566,"modified":"2026-03-24T13:02:59Z","type":"item","id":"Q406701","labels":{"en":{"language":"en","value":"Capturing the drunk robber on a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6341631"}},"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":"Q406701$F88EF3C1-3A8C-4C77-B6F8-9952D57E227C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d367c84e47bb3d02d0a9b83af4cfe4734c2a1882","datavalue":{"value":{"text":"Capturing the drunk robber on a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q406701$B67D3E3A-0DA3-48F6-A6EA-C0CEF28401B2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"927d053d1493c2568e8a417d700148c84fdf6472","datavalue":{"value":"1298.05224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406701$5875781E-2E4E-420A-BA91-161623B5FD4A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e8794a273c6e734fb34c41a17ed10481744355a","datavalue":{"value":{"entity-type":"item","numeric-id":267176,"id":"Q267176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$5E89CC67-7378-43E8-AAAB-235CBF38676A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ed046cfa0f3aaebe7ee5a321838d2b14a94a270","datavalue":{"value":{"entity-type":"item","numeric-id":221782,"id":"Q221782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$10537BF2-1D71-44FB-B0C3-3CEE5D1F7634","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$132C3A27-13A6-4C75-985D-35A107F7163D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d460cc5018b7d6687b87ccaaf2ba1aff43b53078","datavalue":{"value":{"time":"+2014-09-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q406701$ED47EB76-7D59-4453-972A-35C79DE40197","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"03beacdd24bb8839f74da21b5ad6142edc57967c","datavalue":{"value":"https://arxiv.org/abs/1305.4559","type":"string"},"datatype":"url"},"type":"statement","id":"Q406701$34CD75C2-2846-4A4E-929E-8929C4DF2A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"77ea384af3ff0540670cecfe8f4c4b6b48e4ad3e","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p30","type":"string"},"datatype":"url"},"type":"statement","id":"Q406701$281395AD-A6FE-4B69-AD88-406510398BA0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b19ccbe5cb248d5491d5584be510406230011564","datavalue":{"value":"Summary: We show that the expected time for a smart ``cop'' to catch a drunk ``robber'' on an \\(n\\)-vertex graph is at most \\(n +o(n)\\). More precisely, let \\(G\\) be a simple, connected, undirected graph with distinguished points \\(u\\) and \\(v\\) among its \\(n\\) vertices. A cop begins at \\(u\\) and a robber at \\(v\\); they move alternately from vertex to adjacent vertex. The robber moves randomly, according to a simple random walk on \\(G\\); the cop sees all and moves as she wishes, with the object of ``capturing'' the robber -- that is, occupying the same vertex -- in least expected time. We show that the cop succeeds in expected time no more than \\(n+o(n)\\). Since there are graphs in which capture time is at least \\(n-o(n)\\), this is roughly best possible. We note also that no function of the diameter can be a bound on capture time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q406701$131FCB50-EB49-4520-856D-0A50FC666ED5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406701$DDEE6F37-84BB-4501-BAFA-46935351F1C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5b5126101ab4505674efcb5789319f63910d08f","datavalue":{"value":"05C81","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406701$151037AE-07E4-438A-A95B-93B678275AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406701$220A26CE-4522-433B-AB12-8C5897981092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406701$6E5F6188-0B05-4EE0-8003-B1FF3B52D374","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"47d7f23efeff79fd6e92dc1c4589914fab75e502","datavalue":{"value":"6341631","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406701$AFD47EC1-8CC3-4080-82C5-8A2823AFF9A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08099453cfa21d5ca2f3d44f900b12719a5474d0","datavalue":{"value":"random walks","type":"string"},"datatype":"string"},"type":"statement","id":"Q406701$2BB8296A-A4AC-4AB6-9702-FF40E9768500","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48bb47a5b39da982d014a2c96b877271e7e1be7d","datavalue":{"value":"pursuit games on graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q406701$7AC9826D-674F-48E4-B971-B5345BA7355B","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":"Q406701$A601F2BA-2363-464E-9E86-64A61F34330D","rank":"normal"}],"P223":[{"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":"Q406701$469EB221-2014-412B-B38D-1122EEB06814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92752981fd50e8e109138eea2d31ef97edb6c72e","datavalue":{"value":{"entity-type":"item","numeric-id":1569061,"id":"Q1569061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$BD89374C-3DBF-4048-8CE3-10E0368A3BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"708b582f744f52a8e3900a89c49353603b0e717d","datavalue":{"value":{"entity-type":"item","numeric-id":3136609,"id":"Q3136609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$522ABE1E-2248-4BB4-BCFD-2FC3AEB04245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebb5074ee36ed9bb9d929040b0c1d4214893958e","datavalue":{"value":{"entity-type":"item","numeric-id":5836618,"id":"Q5836618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$097D7B43-35C9-48D6-98D9-7ECD4B2A900E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcd7542caac5915c8f63a224b76605abf20c2235","datavalue":{"value":{"entity-type":"item","numeric-id":1837707,"id":"Q1837707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$4A7CF1A4-A521-480D-8FF9-B40603D4701F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae258d243fa694a3e36e8554bd1d1869c9395e91","datavalue":{"value":{"entity-type":"item","numeric-id":934815,"id":"Q934815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$8C5E4191-4A6D-46FA-9DB8-082954626C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9681784022b86162db543dda6c6ef131035bebcd","datavalue":{"value":{"entity-type":"item","numeric-id":4020701,"id":"Q4020701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$3048C7AB-76CA-4A17-A394-724313994F5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1de21e303de74ec4fe3fca88965c245b567a71c1","datavalue":{"value":{"entity-type":"item","numeric-id":3706274,"id":"Q3706274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$9352FED1-61E1-4180-83B1-6DE45C209129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cecd9bda39c19624acbfa8e5458da303b28ce9fd","datavalue":{"value":{"entity-type":"item","numeric-id":5846741,"id":"Q5846741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$EA3EA422-9FAB-412E-A0E5-0AE86378D856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d63b7c74d283e79458f08d4ec9e7d1c8f13a7fc","datavalue":{"value":{"entity-type":"item","numeric-id":1325748,"id":"Q1325748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$97356DFF-D67F-4ACA-BCCE-FFB96ABD02FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71ee2e5d2eb654980dd03a8675fb3cfc9ca12ca1","datavalue":{"value":{"entity-type":"item","numeric-id":1045043,"id":"Q1045043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$C3B55439-364D-4DC0-BA69-695DDE6A5F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d0939e65033e79f8b18f7fccd1693a20cb628d9","datavalue":{"value":{"entity-type":"item","numeric-id":1850039,"id":"Q1850039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$021CF936-E2AF-4C00-B9EA-CCA2FE57B088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4fc938bd8c0c7b17382aa0fa1cd7652406e0ce2","datavalue":{"value":{"entity-type":"item","numeric-id":2433710,"id":"Q2433710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406701$C7240486-6FF0-47E3-B3C0-E41E244931F5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a88fa4069e1cc83c666936d81baaab9751b778be","datavalue":{"value":"bafkreietoddj6y32l5hxlbycm4sjnts575xxst7zxlt3j6ct7yeau4vae4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406701$1F1774B4-08B0-410B-B54E-C96C4A9C9407","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45194d82d816cc60b090e6e317bc4db938a6089d","datavalue":{"value":{"entity-type":"item","numeric-id":2105709,"id":"Q2105709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1be8fe03490b0ebd485ec590e2fa5d738389391f","datavalue":{"value":{"amount":"+0.8881164789199829","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":"Q406701$B92009D5-F653-4833-819F-B05D94AF228C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cfd5893bf81b95145078902f7c48a70f708f950","datavalue":{"value":{"entity-type":"item","numeric-id":1929226,"id":"Q1929226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f71e3dc7e4b66512cc742b2b2a455d3a21f6c2a2","datavalue":{"value":{"amount":"+0.8754467964172363","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":"Q406701$240D866E-2350-41B1-90E7-E47056B69D9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0e1971bb7b045d91a4f34dff790b3a23d1b5f38","datavalue":{"value":{"entity-type":"item","numeric-id":267177,"id":"Q267177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02381930ae872caced58d12e8c79a60f45f50a9e","datavalue":{"value":{"amount":"+0.8512191772460938","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":"Q406701$DC576BA3-7C56-4691-AF01-FAFF9761D25E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77d6989dba02cb3ba858f6aac3133d05275e60fe","datavalue":{"value":{"entity-type":"item","numeric-id":385064,"id":"Q385064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba4be8df3b06fede2383d83a2b843518f2e2e8da","datavalue":{"value":{"amount":"+0.8226866126060486","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":"Q406701$C7E514FE-8C6D-4BEA-872A-BF25F68E05E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad843a8f3ddfc4b30f2594230eca55336b1184cb","datavalue":{"value":{"entity-type":"item","numeric-id":1945995,"id":"Q1945995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f02c70424a1fd7a9c09d0bb34212d2391c28167a","datavalue":{"value":{"amount":"+0.8178853392601013","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":"Q406701$367D9186-BCF8-41C0-87A9-2CE639B7CE1D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:406701","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:406701"}}}}}