{"entities":{"Q685893":{"pageid":687742,"ns":120,"title":"Item:Q685893","lastrevid":82627910,"modified":"2026-05-06T21:21:58Z","type":"item","id":"Q685893","labels":{"en":{"language":"en","value":"Block-distribution in random strings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 425544"}},"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":"Q685893$80F5188E-47D6-4A6A-8BB9-BB13FC6F8040","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ebc7404bc01b311185552f54929a343c68a044e0","datavalue":{"value":{"text":"Block-distribution in random strings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685893$E7FC3488-73BE-4B26-9287-75EF434FF232","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a1af636572c90683b114dfee9ac8d9c4a2f78bb8","datavalue":{"value":"0778.60023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$6B476DCB-B4CB-4114-BFB9-47D2D2BA89D2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"789c2723feb165355f6dd19b06d50d0da493a3ed","datavalue":{"value":{"entity-type":"item","numeric-id":269634,"id":"Q269634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$B51C92FD-58CC-45F4-8625-F528B4DBE415","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0c6922e1e2d821a621b39d1e22a031db881096ee","datavalue":{"value":{"time":"+1994-01-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685893$394EE81D-F28B-46BA-BDB0-4480DBA97006","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"19d20d8a99cf3ec5668f5a16ac0984a17bdafa18","datavalue":{"value":"http://www.numdam.org/item?id=AIF_1993__43_2_539_0","type":"string"},"datatype":"url"},"type":"statement","id":"Q685893$AB4E17CE-1CFC-4653-AE70-925D9224875B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ed6417009112d3a7c5d45be3173e219befbb71a9","datavalue":{"value":"https://eudml.org/doc/75009","type":"string"},"datatype":"url"},"type":"statement","id":"Q685893$E8352ED4-A4F4-4823-B590-181968542A25","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f9422f945206555916a496cfbb40a593b2aa72cb","datavalue":{"value":"A notion of \\(k\\)-discrepancy for infinite sequences of independent random variables taking the values 0 and 1 with probabilities \\(p\\) and \\(q\\) is introduced:  \\[ D^ k_ N(x_ 1,\\ldots,x_ N)=\\max_{A\\in\\{0,1\\}^ k}{1\\over\\sqrt{p^ k\\mu_ k(A)}} \\left|{\\#\\{1\\leq n\\leq N-k\\mid x_ nx_{n+1}\\cdots x_{n+k}=A\\}\\over N}-\\mu_ k(A)\\right|, \\]  where \\(p\\leq q\\), \\(A=a_ 1a_ 2\\cdots a_ k\\) and \\(\\mu_ k\\) is the \\(k\\)-fold product measure generated by \\(\\mu(\\{0\\})=p\\) and \\(\\mu(\\{1\\})=q\\). For an increasing sequence of integers \\(k(N)\\) a sequence of 0's and 1's \\(x_ 1,x_ 2,\\ldots\\) is called \\(k(N)\\)-uniformly distributed if  \\[ \\lim_{N\\to\\infty}D^{k(N)}_ N(x_ 1,\\ldots,x_ N)=0. \\]  It is proved that almost all sequences in \\(\\{0,1\\}^{\\mathbf N}\\) are \\(k(N)\\)- uniformly distributed, if and only if \\(\\log_{1/p}n-\\log_{1/p}\\log n- k(n)\\to\\infty\\). Otherwise the set of \\(k(N)\\)-uniformly distributed sequences has measure 0 which is an immediate consequence of Kolmogoroff's 0-1-law. This generalizes a result due to \\textit{P. Flajolet}, \\textit{P. Kirschenhofer} and \\textit{R. F. Tichy} [Probab. Theory Relat. Fields 80, No. 1, 139-150 (1988; Zbl 0638.68058)], who considered the case \\(p=q=1/2\\) and proved that in this case almost all sequences are \\(k(N)\\)-uniformly distributed, if \\(\\log_ 2n-\\log_ 2\\log_ 2n- k(n)\\to\\infty\\). \\textit{K. Grill} [A note on randomness, Stat. Probab. Lett. (to appear)] proved that almost no sequences are \\(k(N)\\)-uniformly distributed in the opposite case. \\textit{M. Goldstern} [J. Number Theory (to appear)] gave a general argument that almost all sequences are \\(k(N)\\)-uniformly distributed for all \\(k(N)\\) satisfying the above condition. The proof of the theorem uses a generalization of \\textit{L. J. Guibas}' and \\textit{A. M. Odlyzko}'s theory of correlation polynomials of strings [J. Comb. Theory, Ser. A 30, 183-208 (1981; Zbl 0454.68109)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q685893$A186CD42-F5F7-4BDD-85E8-C04DB365BF0B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f49dd74e6cfeea81a6a51567255e1c4853afd305","datavalue":{"value":"60F15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$04145447-0EEB-42CD-B6BC-CAAF3AD6327B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e52a86b600bbb05d9a7823bf91d423713b4b70ab","datavalue":{"value":"60G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$E67CC6ED-6B57-4D86-AC0C-80804A5A89B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f69528cea35ad35a0f81b1419c5bdc2905d27952","datavalue":{"value":"60F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$F6D8775E-0EA5-4F36-8DE0-1DAD4E7B9370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$CFAC1E35-3129-4635-9619-EC1017316C0A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae9dcc4b29bebc7f466e5dfd1815036f6d6b8c4e","datavalue":{"value":"425544","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$5DF40C26-79AC-4E82-9EE6-2A26B5C140E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b64475a1e58ce20530ee60b146061cf1cbbd34e8","datavalue":{"value":"coin tossing","type":"string"},"datatype":"string"},"type":"statement","id":"Q685893$B082EED1-9CE4-4108-BE4C-C5FFC05BA4D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15f48ed4787baedea8f978808eba84ed180892c1","datavalue":{"value":"uniform distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q685893$CD333B2F-5793-4A50-95F8-9A3A777B08D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08950beb392b39a8a05c791e05c66a44902935db","datavalue":{"value":"Kolmogoroff's 0-1-law","type":"string"},"datatype":"string"},"type":"statement","id":"Q685893$ED02D503-A75F-4E34-B293-40F4A2E71E5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3939adebb619ae04f775941ddb50d560fd7f6e88","datavalue":{"value":"theory of correlation polynomials of strings","type":"string"},"datatype":"string"},"type":"statement","id":"Q685893$DEF93062-E75E-41AA-BBE9-7C45856E878C","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":"Q685893$E6F71EDC-A39F-4D00-A29D-C2D614B52A74","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa58bc871705cfe6d7974fbb8b5968178524eb94","datavalue":{"value":"W2323580803","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$4974EA47-A9FB-4361-BE6D-36CC051A4D0E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad7b791f75c0f65d496354707ed7e3289e524eb0","datavalue":{"value":{"entity-type":"item","numeric-id":5541610,"id":"Q5541610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$CF3132D6-09A6-445B-8B38-A5030B3ACF01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e83fd60854af8bf0bf61959610a5f0aea0c6ed69","datavalue":{"value":{"entity-type":"item","numeric-id":1099625,"id":"Q1099625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$2E081DBB-C09F-4259-ADA0-2ACE263D7D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a7fed22f51e94ea89d5711379f67028160494ce","datavalue":{"value":{"entity-type":"item","numeric-id":1340899,"id":"Q1340899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$E8696E6F-EDED-44DA-B179-3E1221FBC893","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b724256772e1dc3961971ab8ed1f503f4953393","datavalue":{"value":{"entity-type":"item","numeric-id":1149796,"id":"Q1149796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$F03E57E6-CBEC-4215-9FB1-03A41D5ACD36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"674b74b1638f814dfd2b509510abe3e91c4d0cb8","datavalue":{"value":{"entity-type":"item","numeric-id":4192121,"id":"Q4192121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$9BF4DC2B-BECE-4483-8285-F73EF2696389","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b42d94d60266957e773272faa201baa47f178170","datavalue":{"value":{"entity-type":"item","numeric-id":4767350,"id":"Q4767350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$051FFAB8-2408-4A5F-9C99-69166EFE50CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d99651f73529e592113ead2fd22bfc9c67118f1b","datavalue":{"value":{"entity-type":"item","numeric-id":3740259,"id":"Q3740259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$AC5B6223-E9AD-4C0D-AFA3-63279A056A0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5b9564b979a9d0175ba3c8db086470676cce61b","datavalue":{"value":{"entity-type":"item","numeric-id":3931654,"id":"Q3931654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$82C84808-ECD4-41CE-87F7-FCBB91BA2A2D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad00780e5ba6627887a0bbb891652a2f8c68c4e1","datavalue":{"value":"10.5802/AIF.1345","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685893$E603D08D-7647-41DE-A8C2-E1A638FE1824","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dc1a1beeefbfbbcf5aa3adaae27b74e0e5ad168d","datavalue":{"value":{"entity-type":"item","numeric-id":4557581,"id":"Q4557581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685893$F43606D3-D15E-4748-8DC2-B47EE89DCE44","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02439ef830a8ca0526e742ceefbc92f5a7a6bb03","datavalue":{"value":{"entity-type":"item","numeric-id":1080465,"id":"Q1080465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbe9280d35db627c006215797304c4ff8972ed51","datavalue":{"value":{"amount":"+0.8707112073898315","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":"Q685893$64CDC2BF-C223-43AE-A42D-4B376882143C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"051d41e51b29e7e6fa9ff585d22631e994b50ae7","datavalue":{"value":{"entity-type":"item","numeric-id":1099625,"id":"Q1099625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03548c99af701ae3aa6c68fcf056bae9f469e1f7","datavalue":{"value":{"amount":"+0.8633790016174316","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":"Q685893$8B9F61AC-8BED-45AE-8325-6AED18913BCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94ca769a9bddada163aab7bf93188802d6807013","datavalue":{"value":{"entity-type":"item","numeric-id":1061165,"id":"Q1061165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f56db8e1bb62a5a3686278bd8112fa61da0e1c2","datavalue":{"value":{"amount":"+0.7989374399185181","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":"Q685893$3948E94F-000D-4C53-BB02-8CF855AA2DF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3108a4a83d9fe5cb4da1c8535692bea9bad53203","datavalue":{"value":{"entity-type":"item","numeric-id":3976961,"id":"Q3976961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70bcae81042f6fa19725934c65c18d49d5c20679","datavalue":{"value":{"amount":"+0.7773846387863159","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":"Q685893$096B3B62-3DF7-4024-9A04-CBAD6FBA7882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd1b7492d5af94c8e2dc8e51fe4cf35199f53e80","datavalue":{"value":{"entity-type":"item","numeric-id":3705528,"id":"Q3705528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02c5b8ec99e33b9fd63a6998f1e4cc834ad43574","datavalue":{"value":{"amount":"+0.7741273641586304","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":"Q685893$0DE6414A-3DA4-4009-8A7E-51EB4B14E605","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Block-distribution in random strings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Block-distribution_in_random_strings"}}}}}