{"entities":{"Q808102":{"pageid":809950,"ns":120,"title":"Item:Q808102","lastrevid":49524088,"modified":"2026-01-07T11:27:13Z","type":"item","id":"Q808102","labels":{"en":{"language":"en","value":"Geometric bounds for eigenvalues of Markov chains"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4209240"}},"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":"Q808102$80D5EABF-2E01-428A-BBEB-25DF37E5741B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa9b02048e74fdff2a9005da7860f282e0719c64","datavalue":{"value":{"text":"Geometric bounds for eigenvalues of Markov chains","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q808102$3F84A95A-86EF-47D2-A7C7-E8F933648F84","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f910ddd5e5744358b7aa88e3a7aa53f16eefd2a","datavalue":{"value":"0731.60061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$4843A563-F97D-4CD5-8C64-CC6B9B66EEF8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ce31ab18e150aa908445d0cf2c30d4bd8d9193d","datavalue":{"value":{"entity-type":"item","numeric-id":221887,"id":"Q221887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q808102$A253EC97-6C28-4CDF-9FE3-81151E0756BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a90a14cf56e3b59b78b57421b105264e21f07b47","datavalue":{"value":{"entity-type":"item","numeric-id":215615,"id":"Q215615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q808102$26919596-8257-4DBF-BFE4-379B65423A5B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e04a4b352e727282a8f30f5809a3df145fda07dd","datavalue":{"value":{"entity-type":"item","numeric-id":81240,"id":"Q81240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q808102$0868DB93-AA4E-407A-98D8-D0505D3BAB19","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q808102$872841B0-8530-41AF-81D9-F7DC9C8428D7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c00e220ef53ab1dc5aeaa6a137d332237432e826","datavalue":{"value":"Consider an irreducible Markov chain with a finite state space x and denote by P(x,y), x,y\\(\\in X\\), its transition probability. Assume that it has a stationary distribution \\(\\pi\\) and P(x,y) is reversible with respect to \\(\\pi\\). If so, as well-known, the Markov associated operator P is a self-adjoint contraction \\(L^ 2(\\pi)\\), whose eigenvalues are \\(1=\\beta_ 0>\\beta_ 1\\geq...\\geq \\beta_{m-1}\\geq -1\\), where \\(m=| X|\\). The first aim of this paper is to develop methods for deriving bounds for \\(\\beta_ 1\\), \\(\\beta_{m-1}\\) and \\(\\beta_*=\\max (\\beta_ 1,| \\beta_{m-1}|).\\) The bounds depend on geometric quantities such as the maximum degree, diameter and covering number of associated graphs. Then simple examples (involving random walks on graphs) are given where the bounds are easily obtained and compared with the exact values. These examples seem to point out that the bounds obtained by the present authors are better than those derived through Cheeger-like inequalities. Finally, the bounds are used to get improved rates of convergence for a random walk associated with a problem of interest in theoretical computer science.","type":"string"},"datatype":"string"},"type":"statement","id":"Q808102$6159B5D0-8D58-49F1-B3A5-35E65346D6BF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"03ca6ec0bd4437c2756bbab26db9f3323e4b4f76","datavalue":{"value":{"entity-type":"item","numeric-id":794052,"id":"Q794052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q808102$B9BA4941-36F3-483F-A040-9EA48B922896","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$AC1B5409-6A4D-452C-893A-3D666C8BCB91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$0EB34379-1FDF-45EA-B68E-48770DB3D1EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$9D12DB3F-F041-4546-A519-BB5A94677671","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c64b44d19026be3d3187e7a93612784a82d7750d","datavalue":{"value":"4209240","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$8FD56DF7-0631-4632-99A2-47F5B7195FEC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efefea548f8a9d6d66a36c34395621fab693bc61","datavalue":{"value":"eigenvalues of Markov chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q808102$B9323906-D27D-459A-9E1C-A7CC227A586F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85c9a1577f1cefb198cc5fea9807689b87b6a76d","datavalue":{"value":"stationary distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q808102$3ECC771A-09F8-41A5-AFAE-04114FF2705C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1e9ed245d0a53d9076fcdbc2a95dcd00f854e31","datavalue":{"value":"Cheeger-like inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q808102$BD062CBF-A561-4A00-9917-CAA37B6AB3B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb92758a9464644a9a762be5a774aae78a1763be","datavalue":{"value":"rates of convergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q808102$5EE8FAD8-DEB9-4E7C-B139-C4B19286B582","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":"Q808102$D26E6843-BB80-4C5B-B8E6-0F5CCA6FE6D7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4dd621ed8e84715cd387568660fae5680a021213","datavalue":{"value":"https://doi.org/10.1214/aoap/1177005980","type":"string"},"datatype":"url"},"type":"statement","id":"Q808102$1632A31E-666B-46C7-95FE-2E6A051D510F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1c9acbbaed60a3cd46ba32636b01b9d2b2151524","datavalue":{"value":"W2043694962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$C1ADEF1D-47E6-4ADD-B433-1B2DA5E1495E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3f6e73f47f559fbcf8585d283474243fb67aa738","datavalue":{"value":"Q98839744","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$F4624399-C176-4CBE-A605-A6B8BD3F3B08","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"967c89f69746bff86fb90e5941d9fc48dc04cec2","datavalue":{"value":"10.1214/AOAP/1177005980","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q808102$BB355F15-B7A1-4D95-8715-40EB87AB1854","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bfdb4ce2ac6eaf5d79ead7cf483f05197280c1c","datavalue":{"value":{"entity-type":"item","numeric-id":1877387,"id":"Q1877387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29850c98f754a92c05cfa8175c848c52c0463c8b","datavalue":{"value":{"amount":"+0.867348313331604","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":"Q808102$9BDA0A7F-DD4A-4E2A-BCB3-795F7CF9106E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e990f2f2d965db2c8238e75d2f01786fafd0d99","datavalue":{"value":{"entity-type":"item","numeric-id":1308697,"id":"Q1308697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22b0a2cacbf68db723fd33bea5860b449e728f00","datavalue":{"value":{"amount":"+0.8429239988327026","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":"Q808102$DB0DF294-CA38-4091-B571-EEE791F2F6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e875d65daa7bee4aba6cc7a279eeb7ebd481931","datavalue":{"value":{"entity-type":"item","numeric-id":3142601,"id":"Q3142601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"775c86bd9697facf5980043d215597775c2b2d83","datavalue":{"value":{"amount":"+0.8325175046920776","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":"Q808102$F77F2488-D30B-4BC8-9B53-91339BDBED43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80d1f0ee8d37e14cc1762a2b9a48f93feab859dd","datavalue":{"value":{"entity-type":"item","numeric-id":4529130,"id":"Q4529130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e44f758bf8719911694b15f5dc5ec41656f75b5","datavalue":{"value":{"amount":"+0.829552173614502","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":"Q808102$074D2C05-C723-4C19-8D85-29CD0BAD098B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08fa2d2e19346bbb5dfd6fe4c6e224f7b2989b6c","datavalue":{"value":{"entity-type":"item","numeric-id":1296583,"id":"Q1296583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ada55faa1794ada9957e8786e5ff7e9720171a6","datavalue":{"value":{"amount":"+0.8224233984947205","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":"Q808102$958DDBEC-65D3-41CA-9BDC-BCBD2F6A3788","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:808102","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:808102"}}}}}