{"entities":{"Q1194485":{"pageid":1205234,"ns":120,"title":"Item:Q1194485","lastrevid":47086933,"modified":"2025-12-31T15:25:29Z","type":"item","id":"Q1194485","labels":{"en":{"language":"en","value":"Expected cover times of random walks on symmetric graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 64462"}},"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":"Q1194485$D26E0F22-8868-4D19-BE30-EF179D50B096","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"813bb9c5ba18a541a2a61ed0e698eaae531392f5","datavalue":{"value":{"text":"Expected cover times of random walks on symmetric graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1194485$3E9F4235-073A-4895-BDE8-23D5A6B10DAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"93e3794deae6082dfba39ccc7ddb15e19aedfce6","datavalue":{"value":"0754.60077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194485$25DFFB4C-D1D6-44C9-99FF-31E47F7CD5C8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b647944fdc0a204394450b4d2e57d2e00495c129","datavalue":{"value":"10.1007/BF01060439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194485$0D176D9D-5237-487F-B34B-F96737F43E5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"281f1db8b9c9d6440cc430f8988afc6c0d943135","datavalue":{"value":{"entity-type":"item","numeric-id":221987,"id":"Q221987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$7E3E7312-8A14-4881-97CF-62C50381F916","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":"Q1194485$D31C0F89-73F1-4CB8-BB25-EAC37D537BE9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1194485$79A17731-F6F0-4BE4-A99D-BA1864EAD282","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f18c55eff3be919fe41a64a13a511123f115145","datavalue":{"value":"A simple random walk on a finite connected undirected graph, \\(G=(V,E)\\), is the Markov chain \\(X_ n\\), \\(n\\geq 0\\), that from its current vertex \\(v\\) jumps to one of the \\(d(v)\\) neighboring vertices with uniform probability. The hitting time \\(T_ v\\) of the vertex \\(v\\) is the minimum number of steps the random walk takes to reach that vertex, and the cover time \\(C\\) is the minimum number of steps the random walk takes to visit all vertices in the graph, i.e.: \\(C=\\max_ v T_ v\\).   It is proved that if \\(v\\) is any vertex of a symmetric graph (symmetric here is understood as both vertex- and edge-symmetric), the expected cover time \\(E_ v C\\) is bounded below by \\((N-1)H_{N-1}\\) and is bounded above by \\(2(N-1)^ 2\\). The lower bound is an extension of similar results obtained by \\textit{L. Devroye} and \\textit{A. Sbihi} [J. Theor. Probab. 3, No. 4, 497-514 (1990; Zbl 0711.60068)]. The upper bound is a weak version of a result proved by \\textit{J. D. Kahn, N. Linial, N. Nisan} and \\textit{M. E. Saks} [ibid. 2, No. 1, 121-128 (1989; Zbl 0681.60064)]. A (nonessential) error in this latter paper and the way to fix it are also pointed out.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194485$CB929BF6-F574-4B72-982D-00B2F1D0AB47","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194485$FDFBFC59-3591-4163-99DF-15BC26ACFDF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194485$B7E45C49-593C-449A-8202-99D5AAC4E82E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fdc1c6763797a452beb4a2c2d95658448ab99d0b","datavalue":{"value":"64462","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194485$2E3E294B-1980-4F07-B4C6-FAF7BF4999E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29f90cd83dad24fc82d0e60664cc695c283ac5bf","datavalue":{"value":"random walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194485$3C25321C-D30E-49AC-B8F5-9A55607F3570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"824b626add478fc62311fe0b92554a6efc1bb6ac","datavalue":{"value":"symmetric graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194485$BD33FB5B-EDBA-45BC-8A08-FAD24BE59D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ea82f361bc2e53f3f4b7676c1ab955297bc1c15","datavalue":{"value":"cover time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194485$6F24C8EA-FAB3-4B9A-A3D9-1668A57E0DDE","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":"Q1194485$ECCFDE3D-A10B-460A-8480-C609191E41D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e108574e4804668e0bb33c186caffef2c8c738ad","datavalue":{"value":{"entity-type":"item","numeric-id":1825524,"id":"Q1825524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$922219F6-E4E2-4867-9D21-47013D1D2D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02264d5ffdee50219b903ea31c4440a6a214ae3d","datavalue":{"value":{"entity-type":"item","numeric-id":4692391,"id":"Q4692391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$28C6AC1E-DCB7-4724-8A5B-B5811369C5DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba77d33ed22f5aeb56ecdc48677663cb8b26cc47","datavalue":{"value":{"entity-type":"item","numeric-id":1386176,"id":"Q1386176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$D0684332-858E-4A1C-B741-BC4493BB4723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c51f599330367518cb59a94e64007ab47a9fe0b","datavalue":{"value":{"entity-type":"item","numeric-id":923511,"id":"Q923511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$B35A3AF9-0575-4975-B925-363C619C421C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2edbef85d69daa33fcf28ddf8577bb77803accc4","datavalue":{"value":{"entity-type":"item","numeric-id":1823548,"id":"Q1823548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$82EAEC26-501E-48E8-9691-F3D4D9FDA791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb7df93d6f6a0113c53a7ef7d3a45eb826626d6f","datavalue":{"value":{"entity-type":"item","numeric-id":749044,"id":"Q749044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$4BE026A1-3F4A-475D-ACD4-C7E4CB4BADC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8828598c2978e6f0ae03fc3814ce18ee1700fee4","datavalue":{"value":{"entity-type":"item","numeric-id":3415987,"id":"Q3415987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194485$938F2A48-EF7F-40F9-A540-CA3BB6725D8C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2701b4966601971f847d8947f5c0f1d7c0ba2914","datavalue":{"value":"https://doi.org/10.1007/bf01060439","type":"string"},"datatype":"url"},"type":"statement","id":"Q1194485$CE45741A-E6B8-41B7-8807-85FA0653B87C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"83d63dafe4688d9de61b6e5dca8aa083fa7213f5","datavalue":{"value":"W2001528257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194485$5EDA3216-B52A-4250-8313-03B22558D478","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8b840b28c0d3461282cef8619b577c3e67291e9","datavalue":{"value":{"entity-type":"item","numeric-id":923511,"id":"Q923511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44f2e734316c6f44faafb4c77912e6ab45a4a56a","datavalue":{"value":{"amount":"+0.8848578929901123","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":"Q1194485$49B05376-4CF1-4C4A-9ED5-455BF21C7D48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f5a159253726a9ad709bbb676257e54caa8ec0a","datavalue":{"value":{"entity-type":"item","numeric-id":4288887,"id":"Q4288887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff498e85c8c66e129bb3275df26b49ccb10ed9d2","datavalue":{"value":{"amount":"+0.8760328888893127","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":"Q1194485$9EDACD9F-0A66-49D7-8B3A-A3D057240C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da9cbce391f586a32bd682e7b8a17c94289f3554","datavalue":{"value":{"entity-type":"item","numeric-id":4881294,"id":"Q4881294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75328e2e84a8c2b196b7bf0d877abd072f02cf76","datavalue":{"value":{"amount":"+0.8750565648078918","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":"Q1194485$A5E4AB7C-C9B5-4DAF-AF59-686C57EAC8E2","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":"43bfc9923a415de717290b98e8cde78ea24c95ab","datavalue":{"value":{"amount":"+0.8650129437446594","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":"Q1194485$67DDF36E-B946-492E-9E7C-5F0307501B83","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":"c402e4b68a9b97d62763ee6eb5815c9e50912d90","datavalue":{"value":{"amount":"+0.834820032119751","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":"Q1194485$6AA6003B-BC33-4037-AD1E-D1809D837120","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1194485","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1194485"}}}}}