{"entities":{"Q2304533":{"pageid":2315276,"ns":120,"title":"Item:Q2304533","lastrevid":73897779,"modified":"2026-04-14T17:39:42Z","type":"item","id":"Q2304533","labels":{"en":{"language":"en","value":"Uniform van Lambalgen's theorem fails for computable randomness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7179699"}},"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":"Q2304533$9D430DD3-C916-47DF-B3A0-988A0347554D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a48d0ae990ec94afece8535e5f4d75f94a59202","datavalue":{"value":{"text":"Uniform van Lambalgen's theorem fails for computable randomness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2304533$1CAB790A-812D-4002-ADF8-98CCBB772994","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61504771c095911e489d07b86c6d3669ca8d001f","datavalue":{"value":"1441.68110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$B1EF90DE-27EF-4FD6-9B52-B7A32D1BFFC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"951664c0fe1f3ea13003323bbac5c43c5934955d","datavalue":{"value":{"entity-type":"item","numeric-id":285519,"id":"Q285519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$BE39EDCD-3432-43C3-A170-68AA51AD44CC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$A8FDA1C5-CAD1-44A7-B654-F7BFCD7CAE16","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a3ddeab2841725759b2e820b7ea1589750ac80ae","datavalue":{"value":{"time":"+2020-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2304533$34E59D59-5194-447C-B684-0FFEA6F3F5A1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82360580458c0e438001f1e695976a898ca8086a","datavalue":{"value":"https://arxiv.org/abs/1510.00554","type":"string"},"datatype":"url"},"type":"statement","id":"Q2304533$008D4D7C-D8AC-43B5-8184-7B6AB8C72958","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43ccba06253303d0b31dec1cfe97fdd369c6ecfd","datavalue":{"value":"It is not possible to have a successful strategy in a game of chance. However, formalizing this statement is not easy, even for simple situations when the outcome of a game is determined by a (potentially infinite) sequence \\(a_1a_2\\ldots a_n\\ldots\\) of truly random bits: head or tail, red or black, etc. The usual formalization takes into account that the gambler starts with some amount of money. The gambler can stop after each \\(n\\); in this case, he/she will have the amount of money \\(f(a_1\\ldots a_n)\\). Instead of taking this amount, the gambler can ask for one more cycle, with values \\(f(a_1\\ldots a_n0)\\ge 0\\) and \\(f(a_1\\ldots a_n1)\\ge 0\\) whose mathematical expectation \\((f(a_1\\ldots a_n0)+ f(a_1\\ldots a_n1))/2\\) is equal to the current amount. The resulting function \\(f(a)\\) from finite binary sequences to non-negative real numbers is known as a \\textit{martingale}. For each gambling strategy (i.e., for each computable martingale \\(f(a)\\)), if a sequence \\(\\{a_i\\}\\) is truly random, then, while the gambler may earn some money, we do not expect the gambler with finite initial funds to be earning an unlimited amount of money -- so all the amounts \\(f(a_1\\ldots a_n)\\) should be bounded.  This idea underlies one of the natural definitions of randomness: an infinite sequence \\(a_1a_2\\ldots\\) is \\textit{computably random} if for each computable martingale \\(f(a)\\), the set of all the values \\(f(a_1\\ldots a_n)\\) is bounded. This paper provides an unexpected counter-intuitive  example of a sequence in which odd bits are computably random, even bits are computably random relative to the odd bits, but the whole sequence is not computably random: it has a martingale allowing infinitely increasing wins!   Such examples are impossible if we use other definitions of randomness; so maybe computable randomness does not fully capture our intuitive idea of randomness? From the technical viewpoint, this paper's example is very subtle -- e.g., if we also require that odd bits are computably random relative to even bits, then the whole sequence is always computably random.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2304533$B009C6B2-192D-4697-9568-C5C349B9FF8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$6DCA30AD-9601-46AD-B9AE-C9D09B7B7B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bfc1b1c272474384546bcd37c9164f9d239a9903","datavalue":{"value":"03D32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$8FD02819-9713-4D1C-9EB4-5920FCAFEE5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"88c8d0405ee76c2940780cfb4e0febabc9eae933","datavalue":{"value":"60G48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$FFC8A6F2-1C6B-43AE-8273-03AD0A12FABF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dcbab04778469cd1a9ba8bc7a6455a0dd16fc4e3","datavalue":{"value":"7179699","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$51C133AE-CA69-402E-889C-D756BFB130BD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c35ff20c2409c5acf398e3e58f29e36ad784af70","datavalue":{"value":"algorithmic randomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2304533$FF6F229D-E800-482B-B504-6BBA7851BD8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8303a89e5e979e44e65aa210688e1071093c7c30","datavalue":{"value":"martingale","type":"string"},"datatype":"string"},"type":"statement","id":"Q2304533$1ADA762E-2B71-4A5E-929B-3BE59103929A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ea3c033236b5563e4109c923c8dab83abb0dd2e","datavalue":{"value":"computable randomness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2304533$42CAE8DB-E60B-4B77-AD75-8A8A5552BA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bc0068e5ff2bc125a236f712a67b194ea1a05e7","datavalue":{"value":"van Lambalgen's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2304533$049AE514-5FB0-471D-88B3-1815E99A6837","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7a7a7a3dd3a08360856ececf3d8a629dcc430503","datavalue":{"value":{"entity-type":"item","numeric-id":592003,"id":"Q592003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$D2BDF5DB-9DE3-4E26-A820-70C10A926BA7","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":"Q2304533$6E840855-B365-4AFA-AB43-73935125D7D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"650b117f2cf5514bb22f399beecedd7ce0878c2e","datavalue":{"value":"W2987945584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$B4467CCA-AD31-48F3-A9F6-BA2B75039606","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"efe72a0aa4ae4cd9afe27b1e7fa5d4af61d0869e","datavalue":{"value":"Q126784902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$D2AB0E19-7CB5-4505-A0CD-76020C5A8333","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"54d65409dfa4e8ed2a803aac5db06b4633180d91","datavalue":{"value":{"entity-type":"item","numeric-id":2988817,"id":"Q2988817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$EDEBBE75-C113-487D-9469-A2178418C0E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c81cb6dd6a9a4640d1141873a1079e01fb4c894b","datavalue":{"value":{"entity-type":"item","numeric-id":5737987,"id":"Q5737987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$ABBB60A2-A842-42D7-83BF-8CB36C97784D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45131a38ff53f12b9952d52e2962c28740fef2f7","datavalue":{"value":{"entity-type":"item","numeric-id":3161424,"id":"Q3161424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$54A106FE-FF4A-479C-8977-8E192CF4C45B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23d58d763f96d02ae16e113087f99c3ff59ef118","datavalue":{"value":{"entity-type":"item","numeric-id":540405,"id":"Q540405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$1ACA3A02-38DC-4687-AA1C-C3BC13EDC21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"269cc02ae7c1fc0239e2e2df5074c90539bab0cb","datavalue":{"value":{"entity-type":"item","numeric-id":3764139,"id":"Q3764139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$3CD88934-126E-4156-A2D4-C7DAC8E8163E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69f71c65f6603cecb67d9b8266a9670a9f8a421e","datavalue":{"value":{"entity-type":"item","numeric-id":3758821,"id":"Q3758821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$91F3052C-3BDF-4791-B189-E60A998B6849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b1cce22b91f6c3d9ffb57dd1a4047080b2d4a7","datavalue":{"value":{"entity-type":"item","numeric-id":5737995,"id":"Q5737995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$07E151CF-0B04-4C31-881A-9FA9FB526842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"314cf986ef59db314ebb52ef308b46a4d1b48865","datavalue":{"value":{"entity-type":"item","numeric-id":3420060,"id":"Q3420060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2304533$4A633B5F-498E-4ECF-9C86-F260488B0B1F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4b8a9936dd71b1d203cf2c08313704257e6bc746","datavalue":{"value":"10.1016/J.IC.2019.104486","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2304533$2B6AB995-F323-4EC4-B366-E446BEDDC84A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32d548cbb08ef1add3823f521f2e263784617d3f","datavalue":{"value":{"entity-type":"item","numeric-id":5737995,"id":"Q5737995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cee916e3e251c35c5a7ba7892ef92c785d74329","datavalue":{"value":{"amount":"+0.8539712429046631","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":"Q2304533$7616C6FD-73E4-44DA-8F8C-FDD8D33DA1EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a2c677917344ae1d897af21cbc86218468792d0","datavalue":{"value":{"entity-type":"item","numeric-id":519903,"id":"Q519903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"215b800b18e4d1acf2ed52414f956b052775efd0","datavalue":{"value":{"amount":"+0.832974910736084","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":"Q2304533$97C4135E-F6FD-4315-BB7B-0853BA595320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"407ac514e59a99c82263c38c5fa066caed79f803","datavalue":{"value":{"entity-type":"item","numeric-id":540405,"id":"Q540405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd272985520f51fdc5d23eed425faa0f6532aa8b","datavalue":{"value":{"amount":"+0.8329733610153198","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":"Q2304533$A91D8AA2-2B9B-4E57-B08D-2BFDF79E4967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c846c366b6a66104a669f97844e5fea96dcdb1b4","datavalue":{"value":{"entity-type":"item","numeric-id":4355680,"id":"Q4355680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d33217257eec8dcdcc9257e62b8b9eead1d39cca","datavalue":{"value":{"amount":"+0.8232410550117493","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":"Q2304533$D6D10D7C-7506-4478-8877-40514965D36C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cab6b6f0954e4e04cb2a173bdbf30015f5004477","datavalue":{"value":{"entity-type":"item","numeric-id":4513960,"id":"Q4513960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15c3c10343a4a30e9725a48147ae70760fb200dd","datavalue":{"value":{"amount":"+0.8152390718460083","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":"Q2304533$DF02DDA7-4C3E-4CA0-A46B-B95B7A5A9AA7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Uniform van Lambalgen's theorem fails for computable randomness","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Uniform_van_Lambalgen%27s_theorem_fails_for_computable_randomness"}}}}}