{"entities":{"Q1060517":{"pageid":1071269,"ns":120,"title":"Item:Q1060517","lastrevid":69536715,"modified":"2026-04-13T07:40:29Z","type":"item","id":"Q1060517","labels":{"en":{"language":"en","value":"Asymptotically efficient adaptive allocation rules"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3907611"}},"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":"Q1060517$CA91A831-CC32-419B-B23B-C26F11E7C990","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"66bb044ea743c0f444c5f020be7d4b0a68c4b701","datavalue":{"value":{"text":"Asymptotically efficient adaptive allocation rules","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1060517$8715BAEE-1DDF-473A-B013-C6C55FFC5CAA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f4823902b3488a8fe2d8d9ee668ff3ab614cafb7","datavalue":{"value":"0568.62074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$0D9EB89A-4F52-49DC-986B-F345322024DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"23e65d244dd1bccded3cfc6b8245434219f2cd79","datavalue":{"value":"10.1016/0196-8858(85)90002-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$F3C8CDBB-6F8B-4E92-812F-BF39442AA8DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad0f36cdf77922073f5fd4a4062a1d40759bfe03","datavalue":{"value":{"entity-type":"item","numeric-id":477961,"id":"Q477961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060517$4DE36D3C-52DC-4D86-AB22-15FBB7FEFEAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c35bd3d310d66bbf113713c3fe6e9bdd0f2ecdc0","datavalue":{"value":{"entity-type":"item","numeric-id":6482590,"id":"Q6482590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060517$94819DCC-48CE-42E1-880B-9D9D13448963","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f171e2d358ed0c5ffcfe728031d35021527481f7","datavalue":{"value":{"entity-type":"item","numeric-id":103557,"id":"Q103557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060517$2181D520-FC43-42BB-AD4A-40EDA75B25AA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1060517$5279ED6F-8FF7-49E9-80FE-71464DFF1BA7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8321e6d18a55328955c47cbffe93d04674010707","datavalue":{"value":"\\(\\Pi_ j\\) \\((j=1,...,k)\\) denote statistical populations specified respectively by univariate density functions \\(f(x;\\theta_ j)\\) with respect to some measure \\(\\nu\\), where the form of f is known but the parameters \\(\\theta_ 1,...,\\theta_ k\\) are unknown. It is assumed that \\(\\int^{\\infty}_{-\\infty}| x| f(x;\\theta)d\\nu (x)<\\infty\\) for all possible values of \\(\\theta\\).    The problem is to sample \\(x_ 1,x_ 2,..\\). sequentially from the k populations in order to achieve the greatest possible expected value of the sum \\(S_ n=x_ 1+...+x_ n\\) as n approaches infinity. At each stage, we can use all the past observations to decide from which population to sample.    Define \\(\\mu(\\theta)\\) as \\(\\int^{\\infty}_{-\\infty}xf(x;\\theta)d\\nu (x)\\), and \\(\\mu^*\\) as \\(\\max\\{\\mu (\\theta_ 1),...,\\mu (\\theta_ k)\\}\\). Define \\(R_ n(\\theta_ 1,...,\\theta_ k)\\) as \\(n\\mu^*-E(S_ n)\\). Then our problem is equivalent to minimizing \\(R_ n(\\theta_ 1,...,\\theta_ k)\\) as n approaches infinity.    Let \\(I(\\theta,\\lambda)\\) denote \\(\\int^{\\infty}_{-\\infty}[\\log (f(x;\\theta)/f(x;\\lambda))]f(x;\\theta) d\\nu(x).\\) It is assumed that f is such that \\(0<I(\\theta,\\lambda)<\\infty\\) whenever \\(\\mu (\\lambda)>\\mu (\\theta)\\), and for all \\(\\epsilon >0\\) and all \\(\\theta,\\lambda\\) such that \\(\\mu(\\lambda)> \\mu(\\theta)\\), there exists \\(\\delta(\\epsilon,\\theta,\\lambda)\\) greater than zero for which \\(| I(\\theta,\\lambda)-I(\\theta,\\lambda')| <\\epsilon\\) whenever \\(\\mu (\\lambda)\\leq \\mu (\\lambda')\\leq \\mu (\\lambda)+\\delta (\\epsilon,\\theta,\\lambda).\\)    A sampling rule with the property that for any fixed values \\(\\theta_ 1,...,\\theta_ k\\) for which the \\(\\mu (\\theta_ j)\\) are not all equal, \\(R_ n(\\theta_ 1,...,\\theta_ k)/(\\log n)\\) approaches \\(\\sum_{j:\\mu (\\theta_ j)<\\mu^*}(\\mu^*-\\mu (\\theta_ j))/I(\\theta_ j,\\theta^*)\\) as n approaches infinity, where \\(\\theta^*\\) is defined by \\(\\mu^*=\\mu (\\theta^*)\\), will be called ''asymptotically efficient.'' (It is shown that this asymptotic value for \\(R_ n(\\theta_ 1,...,\\theta_ k)\\) is the smallest possible.)    An asymptotically efficient sampling rule is constructed as follows. Suppose \\(\\{h_ i(Y_ 1,...,Y_ i)\\}\\) and \\(\\{g_{ni}(Y_ 1,...,Y_ i)\\}\\) are sequences of real-valued functions \\((n=1,2,...\\); \\(i=1,...,n)\\) with the following properties: \\(g_{ni}\\) is nondecreasing in \\(n\\geq i\\) for every fixed \\(i=1,2,..\\). ; \\(h_ i\\leq g_{ni}\\) for all \\(n\\geq i\\). Assuming that \\(Y_ 1,...,Y_ i\\) are i.i.d. each with density \\(f(y;\\theta)\\), then for all \\(\\theta\\), \\(P_{\\theta}(r\\leq g_{ni}(Y_ 1,...,Y_ n)\\quad for\\quad all\\quad i\\leq n)=1-o(n^{-1})\\) for every \\(r<\\mu (\\theta)\\),  \\[ \\lim_{\\epsilon \\downarrow 0}( \\limsup_{n\\to \\infty}\\sum^{n}_{i=1}[P_{\\theta}\\{g_{ni}(Y_ 1,...,Y_ i)\\geq \\mu(\\lambda)-\\epsilon \\}]/(\\log n))\\leq 1/I(\\theta,\\lambda)  \\]  whenever  \\[ \\mu(\\lambda)>\\mu (\\theta);  \\]   \\[  P_{\\theta}\\{\\max_{\\delta n\\leq i\\leq n}| h_ i(Y_ 1,...,Y_ i)-\\mu (\\theta)| >\\epsilon \\}=o(n^{- 1})\\text{ for all }\\epsilon >0\\quad and\\quad 0<\\delta <1.  \\]  For \\(j=1,...,k\\), let \\(T_ n(j)\\) denote the number of times that the rule samples from \\(\\Pi_ j\\) up to stage n, and let \\(Y_{j1},...,Y_{j,T_ n(j)}\\) denote the successive observations. Define \\({\\hat \\mu}_ n(j)=h_{T_ n(j)}(Y_{j1},...,Y_{j,T_ n(j)}),\\) \\(U_ n(j)=g_{n,T_ n(j)}(Y_{j1},...,Y_{j,T_ n(j)}),\\) and let \\(0<\\delta <1/k.\\) At stage \\(j=1,...,k\\), the rule takes one observation from \\(\\Pi_ j.\\)    Now suppose the rule has taken \\(n\\geq k\\) observations. We choose \\(j_ n\\) such that \\({\\hat \\mu}_ n(j_ n)=\\max \\{{\\hat \\mu}_ n(j):\\quad T_ n(j)\\geq \\delta_ n\\}.\\) At stage \\(n+1\\), writing \\(n+1=km+j,\\) where m is a positive integer and j is one of the integers 1,...,k, we take an observation from \\(\\Pi_ j\\) only if \\({\\hat \\mu}_ n(j_ n)\\leq U_ n(j),\\) and sample from \\(\\Pi_{j_ n}\\) otherwise.    The sampling rule just described is asymptotically efficient. It is illustrated for the special cases of sampling from normal, Bernoulli, exponential, and Poisson distributions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060517$7EB6258E-AA77-4969-AE02-707B24FEED04","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"46b5c34ce8c233319220da380cff61aa0fb62b3c","datavalue":{"value":"62L10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$178996CA-4926-4FFB-84FF-7DF98D1D97C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2c0c09d2caba66ba44b1be99e80b2f2867b9bbb8","datavalue":{"value":"62L05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$529D784A-4303-4950-80DC-01C2F324A939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7388451dde188da6ebc313ef2e8d5b8082d7c260","datavalue":{"value":"62F07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$22AEC393-B6C4-4455-9394-A5EEC3BD78E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a4dbf529fe501a8125be9da861e7c4a1450806a","datavalue":{"value":"62F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$9461FD0E-4DC3-4A44-B58E-D94D16DB59B0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3a5d5fcae281406c43b6cecbc1388754d034ce73","datavalue":{"value":"3907611","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$A8FB97B1-FBA2-47C0-8702-DA718067AAA3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9dd550d4537f57da5c7a45e787255a1c77d97b6","datavalue":{"value":"adaptive allocation rules","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060517$21DFA381-0C5C-4068-BF0D-F367C1102716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac95fa51b7377080f6a93b98c92ba17035637fcf","datavalue":{"value":"asymptotically efficient sampling rule","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060517$6CEB39D3-3342-4137-9251-5D13A6E3ABAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d862d6e87c0f2c58f71494862d8493aa105d9fcd","datavalue":{"value":"normal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060517$FF866E5D-8A5C-41DE-8373-6CD72BE8DB66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ff5718985d4c8f4773972f5cf7a2957e2a81b48","datavalue":{"value":"Bernoulli","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060517$9F10CA61-4B18-4F79-8778-413CFA13CA54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"421438df799a8f4e9011afb54bdadfa916edb4f1","datavalue":{"value":"exponential","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060517$3A03FB50-E385-45BE-AB6B-E41AD76E064B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28748bb9e655dcc7a7fb9cafe1484d43f9be4420","datavalue":{"value":"Poisson distributions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060517$1FFE4273-C656-4D22-9A42-5C5075939F58","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1c4694b7cf19dd0b5ac0ce9f1cb5f2e7a0596365","datavalue":{"value":"Q56675673","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$7D3F80F2-A1B4-4AD5-AA45-71FB8771CAAC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9be030673dee2d9386d303e280d72687292960c1","datavalue":{"value":{"entity-type":"item","numeric-id":1171842,"id":"Q1171842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060517$04FEBC5E-F6DD-46F4-86C9-4B2B7D1F6A9A","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":"Q1060517$2F9DF4BE-ED58-45D8-8C88-B63FB8CAF612","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c38a654ced5204f17e34533fc69d6a674df94943","datavalue":{"value":"https://doi.org/10.1016/0196-8858(85)90002-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1060517$006E62ED-1012-442E-B453-FC424E397BCA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bd011331890224e0ac8a2334a187cf6809a7f91c","datavalue":{"value":"W2009551863","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060517$7E049F0A-38E2-4AAE-A99D-21934C46085E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea511dcc1703658a4f5af384a452940f16b52395","datavalue":{"value":{"entity-type":"item","numeric-id":4102533,"id":"Q4102533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060517$31D8A7E1-7FAD-4FD9-9A2A-9D4A4CD87751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a76e97a07c6556fa4bb9a593a9c33c91a7b479e","datavalue":{"value":{"entity-type":"item","numeric-id":3959314,"id":"Q3959314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060517$53AE2245-1FE9-4AD7-891A-9FD0E64C1A2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebcad68569814afb45a9580dddd347464f5bb0f2","datavalue":{"value":{"entity-type":"item","numeric-id":5817009,"id":"Q5817009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060517$3AF84665-B2B4-4CAB-9764-CB6833970BF2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a303a0b06c79db509fbd806130894fb745f018d","datavalue":{"value":{"entity-type":"item","numeric-id":3718014,"id":"Q3718014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b31c7615b562a389068934faada0052fc1b34110","datavalue":{"value":{"amount":"+0.9112499356269836","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":"Q1060517$1DB204CC-90A1-4B2E-80FE-8BC19704E1A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bd5d237cd59694f03e832be97577cc9a94bf85f","datavalue":{"value":{"entity-type":"item","numeric-id":4203564,"id":"Q4203564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fc367d1b8e332a9820187db2357fef385229ae5","datavalue":{"value":{"amount":"+0.8874592185020447","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":"Q1060517$3D8F433E-EAE4-4F89-9E5C-C99EBE378707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c762eb73b11ac9ab301e558f74fda83c01c89658","datavalue":{"value":{"entity-type":"item","numeric-id":3709695,"id":"Q3709695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a328a85288bf81fb9510922ac0c4451a8c341ff","datavalue":{"value":{"amount":"+0.8750355839729309","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":"Q1060517$375E4870-A234-43A9-953A-A6EAF28DF3EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a189116474a5f28b8ae9d73ce2d6a71ffc870bb","datavalue":{"value":{"entity-type":"item","numeric-id":1102059,"id":"Q1102059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1943ce0f8ec74941c66c0e45fc671e38db400d6","datavalue":{"value":{"amount":"+0.8708813190460205","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":"Q1060517$5B5CD378-FCC5-489F-BA61-8E454F6B3C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8500161f1b2c2efe0f54194bc2a2301afe71b1ca","datavalue":{"value":{"entity-type":"item","numeric-id":581980,"id":"Q581980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ddb223de41060ed1036f34b3e4e1e59370b865d","datavalue":{"value":{"amount":"+0.8556283116340637","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":"Q1060517$963E5C7E-8EC8-4D70-B5EC-76F342B64FF3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Asymptotically efficient adaptive allocation rules","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Asymptotically_efficient_adaptive_allocation_rules"}}}}}