{"entities":{"Q863483":{"pageid":865331,"ns":120,"title":"Item:Q863483","lastrevid":50008615,"modified":"2026-01-12T15:08:45Z","type":"item","id":"Q863483","labels":{"en":{"language":"en","value":"Faster mixing and small bottlenecks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5118918"}},"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":"Q863483$23EFB099-4126-4485-BD79-2727DB8366E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3739b87663c8fd18d63407a502f82778a6d4d569","datavalue":{"value":{"text":"Faster mixing and small bottlenecks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q863483$B3AC179E-37AA-4551-8A03-2C5C0C80932C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"370dc8a329d587a42f67e24c7cfd44d7589dbe3e","datavalue":{"value":"1113.60073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q863483$B39E0637-EF0E-43D1-BC38-59D0121C176D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6721e2b1eb987ba2390f9abdb34c9100dded7229","datavalue":{"value":{"time":"+2007-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q863483$A67E18CB-20D4-490B-955A-9848D33F6892","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9dd8bc4d9eb8eb7deab19ff4f975063de56f528","datavalue":{"value":"A new bound on the mixing time of Markov chain (MC) is proved by considering the conductance of its connected subsets. A finite MC is a digraph \\(G\\) on vertex set \\(V_n=\\{1,\\dots,n\\}\\) with transition matrix \\(P=\\| p_{ij}\\| _{i,j\\in V_n}\\) such that \\(p_{ij}>0\\) precisely iff \\(ij\\) is an edge of \\(G\\). MC is assumed to be ergodic and reversible, i.e. there exists \\(\\lim_{t \\to \\infty} P^t=\\pi>0\\) and \\(\\pi(i) p_{ij}=\\pi(j) p_{ji}\\) for all \\(i,j \\in V_n\\). The mixing time is defined as  \\[  T_{\\text{mix}}=\\sup_i \\min \\{t:d_{\\text{TV}}(P^t_i,\\pi)<1/e\\},  \\]  where \\(d_{\\text{TV}}\\) stands for the total variation distance and \\(P^t_i\\) is the probability distribution on MC at the time step \\(t\\) given that the initial state was \\(i\\). In the article the lazy MC is considered. The lazy MC stays at each time step at current state with probability 1/2 and takes a step of the original MC with probability 1/2. This does not change the limit distribution and at most doubles the mixing time.  For a set \\(S \\subset V_n\\) the conductance of \\(S\\) is defined as  \\[  \\Phi(S)=\\frac{\\sum_{i\\in S, j\\notin S} \\pi(i)p_{ij}}{\\pi(S)\\pi(V_n \\setminus S)}  \\]  and \\(\\Phi(p)= \\min \\Phi(S)\\), s.t. \\(S\\) is connected and \\(p/2 \\leq \\pi(S) \\leq p\\). For an ergodic reversible lazy MC the following upper bound is proved  \\[  T_{\\text{mix}} \\leq C \\sum_{j=1}^{\\log \\pi_{\\min}^{-1}} \\Phi^{-2}(2^{-j}),  \\]  where the constant \\(C\\) does not depend on the chain and \\(\\pi_{\\min} = \\min_{i \\in V_n} \\pi(i)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q863483$F1FCA9E6-B4FB-4EBE-832E-D3CBE33838C8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"280f101b1c750c0ba69a260fa420e20feae2066a","datavalue":{"value":{"entity-type":"item","numeric-id":629779,"id":"Q629779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$8BEEACF6-A164-40F6-B354-2F156318C92E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q863483$A2FA1B40-0264-4D2B-B674-D7A25E167D72","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5743423c386c05a44c88c4d447a89765f19520ff","datavalue":{"value":"5118918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q863483$50D79F1A-B2C2-4742-A810-B5BDE9AFEE32","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"397d9252ef89819a92633d8502b4000f6e56c083","datavalue":{"value":"Markov chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q863483$AF90F6A7-72C3-46FA-851D-7A76061EE309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85c9a1577f1cefb198cc5fea9807689b87b6a76d","datavalue":{"value":"stationary distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q863483$EC729414-E419-4ED8-91A5-1872AE56C00E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06a0ded343c085005653a31a579d4ce087df5055","datavalue":{"value":"mixing time","type":"string"},"datatype":"string"},"type":"statement","id":"Q863483$82706516-B01F-4DCB-81B8-E10090E1C0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a52e7cf74107ab26934cc2eeb4c482e30ddfac9","datavalue":{"value":"conductance","type":"string"},"datatype":"string"},"type":"statement","id":"Q863483$4777BA13-94E9-4B66-8161-E5FF37E7AAF3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1dbea549db01d8d0f71213a2cd1b82df699a91d7","datavalue":{"value":{"entity-type":"item","numeric-id":490411,"id":"Q490411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$9105483F-5B4A-442B-9364-6C8CA031F16F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$20D08E6A-FFA6-4F18-B451-F46244B86C0D","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":"Q863483$F4B52EFD-3A07-4869-B0B5-9046240B6B6A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c0ecda3820993374126164ec31bc8d7edc879938","datavalue":{"value":"https://doi.org/10.1007/s00440-006-0003-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q863483$D30C7C1D-F32B-45D4-BABF-4EF6E363FF5E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b9bf81a02068aec120551c26ee03ee30714b254e","datavalue":{"value":"W2013770427","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q863483$DFCDFD9D-1362-4F14-A4B0-688A2C66BD02","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c47b5c93f0cc6b78ce2c629e84ac9f8b248c5bd","datavalue":{"value":{"entity-type":"item","numeric-id":3951346,"id":"Q3951346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$7B5EB726-6899-45CF-A4BA-DD2083177DD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9822359b23a3ab607a2bcac1ad0618318136def","datavalue":{"value":{"entity-type":"item","numeric-id":1965874,"id":"Q1965874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$8BD7D725-9FA2-4731-93A5-D2B7CEEE2DF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d651b2dc8bc8372bed05f31d645fa06b2633100","datavalue":{"value":{"entity-type":"item","numeric-id":1400829,"id":"Q1400829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$BEF0EA3F-5097-46D5-9957-6E9215998A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b00364366594d6327ce1b6fe3db3f0413f3b759e","datavalue":{"value":{"entity-type":"item","numeric-id":1912568,"id":"Q1912568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$FC87A35E-0D7F-47FA-A85C-53E1F9B37D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec60cfaadb5f34b804e090cd4a4c2720c9aa8778","datavalue":{"value":{"entity-type":"item","numeric-id":4534221,"id":"Q4534221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$469353C7-1853-40AD-9D83-4075D62682D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae9262828d4c17bef03f5c77c7fc2ebb36bcbe9c","datavalue":{"value":{"entity-type":"item","numeric-id":3142597,"id":"Q3142597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$EA27656A-7D98-4AC6-BD26-733CD354B9BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a8c16c11a17ded9576ab3789ae77c5a09ac4a05","datavalue":{"value":{"entity-type":"item","numeric-id":5295401,"id":"Q5295401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$26827A1E-CD66-4F80-ADFA-5F7FC7B7A1CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9653fc0d970748464086c4f8f5dc309f94657e88","datavalue":{"value":{"entity-type":"item","numeric-id":2819555,"id":"Q2819555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$765FCF14-0B93-4183-998B-468DB3F52B58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeb312b46c318acf73004d738cd80d4eeb60615b","datavalue":{"value":{"entity-type":"item","numeric-id":4350884,"id":"Q4350884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$64356A1E-CAFD-47BA-9AED-22E82B79CB8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d79d51bef0037fe0288934f09d2095292b994078","datavalue":{"value":{"entity-type":"item","numeric-id":4284999,"id":"Q4284999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$17667483-D64F-4EF8-A609-0D2C9E05E1C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da38cab9ab921e8caec440748f3eb1d51dcb3440","datavalue":{"value":{"entity-type":"item","numeric-id":4234053,"id":"Q4234053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$3620F855-6E15-414A-BD4E-195C8B639D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"672b7c767d322e7abf654e0a6ad5e1961e56023b","datavalue":{"value":{"entity-type":"item","numeric-id":5218675,"id":"Q5218675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$F97CAAAE-4FCB-43F9-BC60-2E6FA06FD845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86b0a507d10db80339b0fa7c4fa0649ddb0ba533","datavalue":{"value":{"entity-type":"item","numeric-id":4697807,"id":"Q4697807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$443F544E-1247-4597-8E11-006CF2A477FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc0c2055ac1fe57ffba7fd79e6cbe6b165ba107e","datavalue":{"value":{"entity-type":"item","numeric-id":4252430,"id":"Q4252430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$627CB8FC-0C87-4F95-B6FA-A0FFBD8864D1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a6ace46b92e9df36a82eda692e7190fe40574b2b","datavalue":{"value":"10.1007/S00440-006-0003-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q863483$98491F66-D8B6-4917-B034-F9DC86B7D2C8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3e4ddda27c7b76772b0a1708a44a37e8574d8b29","datavalue":{"value":{"entity-type":"item","numeric-id":3036360,"id":"Q3036360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q863483$C8EF7890-D1EA-4282-B663-F1F96BC186D0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af7f3498cba73a14437613b228d2e06aede960f3","datavalue":{"value":{"entity-type":"item","numeric-id":3976407,"id":"Q3976407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f23d640524c89ca18e0b2997eba25a1c1300ca02","datavalue":{"value":{"amount":"+0.8662273287773132","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":"Q863483$49BED925-BFC6-4D1D-8719-B21DFF97C375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5206d97cdb468b03885da3a089b0347a14fddd71","datavalue":{"value":{"entity-type":"item","numeric-id":4667856,"id":"Q4667856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"792774c03b88df1ad8d03dc57e89989fe988a6bf","datavalue":{"value":{"amount":"+0.8601210713386536","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":"Q863483$9DABE9CD-E34C-486E-81F4-D7D3518D6ED2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00b2af29a453826bb7dec143b07db2ab99a89161","datavalue":{"value":{"entity-type":"item","numeric-id":1883396,"id":"Q1883396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ca31e93a0f058a5b49045e162e37d876201c0fb","datavalue":{"value":{"amount":"+0.8043428659439087","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":"Q863483$DF2B54C0-ACCC-445F-B032-3CD64C23C9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c85cd280ce4cdcb7da536e1f73da5c523ab24df","datavalue":{"value":{"entity-type":"item","numeric-id":4208451,"id":"Q4208451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2afd74ccb2d86a6659e32bd2da0c23ef31bba06a","datavalue":{"value":{"amount":"+0.8037410974502563","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":"Q863483$E6A923C7-83E5-4B30-8443-D90230EF89FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"588773c20de55d7522be8c61eaffcbe5d8bf82c6","datavalue":{"value":{"entity-type":"item","numeric-id":2571014,"id":"Q2571014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d7626588b6ce1eb8cb52cbbe9e7f898d236e651","datavalue":{"value":{"amount":"+0.8026648163795471","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":"Q863483$600ADA13-59C4-46DE-B339-8F6D9CAC05A8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:863483","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:863483"}}}}}