{"entities":{"Q2494578":{"pageid":2505321,"ns":120,"title":"Item:Q2494578","lastrevid":57956058,"modified":"2026-04-03T05:50:15Z","type":"item","id":"Q2494578","labels":{"en":{"language":"en","value":"The overhand shuffle mixes in \\(\\Theta(n^2\\log n)\\) steps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5036880"}},"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":"Q2494578$3EB296EE-7A16-426B-8B15-B07F93FD7CB3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e903dae9837ae653005ec34023a854b644d9a3bd","datavalue":{"value":{"text":"The overhand shuffle mixes in \\(\\Theta(n^2\\log n)\\) steps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2494578$A8254924-5A04-409D-9D97-1A2C8DE400F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"86eb30c0fbb70b7859dcc9a534ba46da76a0478d","datavalue":{"value":"1095.60013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494578$9FE76831-2D16-410D-A617-DFB3C797C7BE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b69e8584fca0af71e769a855cbd8684d07a685cc","datavalue":{"value":"10.1214/105051605000000692","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494578$365A3B28-53D1-4EE0-A2AD-46D52EBD286B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0fdc3252ae578221fe0be2597e62927f8ed4209","datavalue":{"value":{"entity-type":"item","numeric-id":212963,"id":"Q212963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$270D3D1E-E44A-4E51-A530-21BE3A756387","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":"Q2494578$CF0AEB54-8EDA-4706-BC54-1986DA2661E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f7c7ad8d5b4a4d122fdfd012ff9b62e4a5f637dd","datavalue":{"value":{"time":"+2006-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2494578$5D2CE59B-BC21-41B9-92D8-733F954FDF88","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"29160207a29305673f06949e04ff1f7b98298e74","datavalue":{"value":"https://arxiv.org/abs/math/0501401","type":"string"},"datatype":"url"},"type":"statement","id":"Q2494578$315B5B2B-864F-48F6-A558-0F9068438D11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dc30adcb407ad0c16a84b4ac086057d41b76ae5e","datavalue":{"value":"The overhand shuffle is the shuffling technique where you gradually transfer the deck from, say, your right hand to your left hand by sliding off small packets from the top of the deck. \\textit{R. Pemantle} [J. Theor. Probab. 2, No. 1, 37--49 (1989; Zbl 0668.60060)] introduced and analyzed a probabilistic model for the overhand shuffle and established upper and lower bounds of order \\(n^{2}\\log n\\) and \\(n^{2}\\), respectively, for the mixing time on a deck of \\(n\\) cards. In this paper the author uses an extension of a lemma of \\textit{D. B. Wilson} [Ann. Appl. Probab. 14, No.~1, 274--325 (2004; Zbl 1040.60063)] to establish a lower bound of order \\(n^{2}\\log n\\), thereby showing that \\(n^{2}\\log n\\) is indeed the correct order of mixing time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494578$C352A1E5-B794-45FC-9326-86AB6DE01BF8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"07c259578e4daea8f68034612afe756bcdd16ef7","datavalue":{"value":"60G99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494578$ED462BBC-45F0-4E3C-A87B-28D3CE5BA2B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d662bd4a0a99fc0600e869450838775f3d287e8","datavalue":{"value":"60J99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494578$BD0CB1DE-247E-4CA5-A3A0-DAC9E2D2CB51","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1374c6dd6fc5776562cb9cc6839471437ab301a2","datavalue":{"value":"5036880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494578$6A5A9156-8B44-43B0-A9FA-FD98F6050B23","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06a0ded343c085005653a31a579d4ce087df5055","datavalue":{"value":"mixing time","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494578$489307A1-FD3C-4718-9F5C-E8F68F9FFE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cde0b5753e7bee56433fc0efda8d5d3fd8ff2812","datavalue":{"value":"coupling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494578$3D5E3728-870D-4AB1-B027-A3C376C1162F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3ebcb30b3a78046fce01c9ef32eef5814e22493","datavalue":{"value":"lower bound, Rudvalis shuffle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2494578$0912E293-9727-4EDB-B7E8-F31B7283FC6A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"33eeeed16b265f279ad58b09078124b704feda2a","datavalue":{"value":{"entity-type":"item","numeric-id":705274,"id":"Q705274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$C92521D3-59D1-4D77-8857-EC43277B879C","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":"Q2494578$3E19CA09-7446-419E-9B6A-C33DB468FDE3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6094c29975be971eb7d40ad7b994d2293b0b1c01","datavalue":{"value":"W3125833793","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2494578$B5FA9A09-AC65-4AA6-84DB-0830897AA928","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0db5d4cc23b2cd1469d102c9d70f19973895ec38","datavalue":{"value":{"entity-type":"item","numeric-id":3660628,"id":"Q3660628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$B096F1FB-7E08-4D8B-869C-8022AFFFD1B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd5d779ca5d24cfbe2cd90dca279be334aa9e6b2","datavalue":{"value":{"entity-type":"item","numeric-id":1198576,"id":"Q1198576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$9DCAEDFE-B137-4257-842D-31C78C93AE3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9efcf665e715ebd04552b0f310c03feba393550a","datavalue":{"value":{"entity-type":"item","numeric-id":3829850,"id":"Q3829850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$C990F61D-8FDA-48D7-B343-2EF2744CBC1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa8c03fa74a349ba711a7ee7d416bfece0d3c600","datavalue":{"value":{"entity-type":"item","numeric-id":1118258,"id":"Q1118258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$B566C0E2-AAFE-432E-A325-7C055DA4108D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51b51c876acadfa73a40e9b4ea1eca22b5dca6c","datavalue":{"value":{"entity-type":"item","numeric-id":1768198,"id":"Q1768198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$52A344F4-2212-4471-942A-DCEE4BDF3442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6058f7b186fa21835f7286abefe4dab3ecddfa75","datavalue":{"value":{"entity-type":"item","numeric-id":1431558,"id":"Q1431558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2494578$006F465D-E6BA-4712-A43F-25439791A5AD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ab60dd0fd819c8ad6f1e74756b99d6aeb45c343","datavalue":{"value":{"entity-type":"item","numeric-id":1118258,"id":"Q1118258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6505822cc768e30ac827d2b349c82aeb6608e63e","datavalue":{"value":{"amount":"+0.8661393523216248","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":"Q2494578$EF474F9A-A0E9-4A01-AFC2-668A1B34F16A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d6da0a098f553f38660554adf305f6592da491c","datavalue":{"value":{"entity-type":"item","numeric-id":744375,"id":"Q744375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffbde77039ca0146fa49adfad5eae19db697de61","datavalue":{"value":{"amount":"+0.8368824124336243","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":"Q2494578$EC692F7B-8BB4-44AE-A976-1D253CB69D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ecb1631edbf03f19092f0d63d93fa5cd30eea97","datavalue":{"value":{"entity-type":"item","numeric-id":638437,"id":"Q638437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5131ff518afbfb9b03fa7c0a2d20008209d2942c","datavalue":{"value":{"amount":"+0.8276717662811279","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":"Q2494578$23356649-89D2-4DDF-BB31-9CBD80BF72B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03d7aacfbd31d17a0740b162f08572c11e284bbc","datavalue":{"value":{"entity-type":"item","numeric-id":4903266,"id":"Q4903266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a19f7eb341e58d4270d3bc9396217e1218fd4d6","datavalue":{"value":{"amount":"+0.8272125124931335","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":"Q2494578$8C177C6C-C26B-48F4-8163-4F162B081688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14558e3bc72bfa8a329ce36a30f32d575fac1785","datavalue":{"value":{"entity-type":"item","numeric-id":2517245,"id":"Q2517245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f9569ad257f21afc38d014f035b856b9e28e25e","datavalue":{"value":{"amount":"+0.8224704265594482","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":"Q2494578$E60F8DA2-094B-41B4-BACB-5264BF2F206F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2494578","badges":[]}}}}}