{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:50:53Z","timestamp":1747198253490,"version":"3.40.5"},"reference-count":14,"publisher":"Walter de Gruyter GmbH","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In many Monte Carlo applications, one can substitute the use of pseudorandom numbers with quasirandom numbers and achieve improved convergence. This is because quasirandom numbers are more uniform that pseudorandom numbers. The most common measure of that uniformity is the star discrepancy. Moreover, the main error bound in quasi-Monte Carlo methods, called the Koksma\u2013Hlawka inequality, has the star discrepancy in the formulation. A difficulty with this bound is that computing the star discrepancy is very costly. The star discrepancy can be computed by evaluating a function called the local discrepancy at a number of points. The supremum of these local discrepancy values is the star discrepancy. If we have a point set in <jats:inline-formula id=\"j_mcma-2022-2125_ineq_9999\">\n                     <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:msup>\n                              <m:mrow>\n                                 <m:mo stretchy=\"false\">[<\/m:mo>\n                                 <m:mn>0<\/m:mn>\n                                 <m:mo>,<\/m:mo>\n                                 <m:mn>1<\/m:mn>\n                                 <m:mo stretchy=\"false\">]<\/m:mo>\n                              <\/m:mrow>\n                              <m:mi>s<\/m:mi>\n                           <\/m:msup>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_mcma-2022-2125_eq_0043.png\"\/>\n                        <jats:tex-math>{[0,1]^{s}}<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula> with <jats:italic>N<\/jats:italic> members, we need to compute the local discrepancy at <jats:inline-formula id=\"j_mcma-2022-2125_ineq_9998\">\n                     <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:msup>\n                              <m:mi>N<\/m:mi>\n                              <m:mi>s<\/m:mi>\n                           <\/m:msup>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_mcma-2022-2125_eq_0029.png\"\/>\n                        <jats:tex-math>{N^{s}}<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula> points. In fact, computing star discrepancy is NP-hard. In this paper, we will consider an approximate algorithm for a lower bound on the star discrepancy based on using a random walk through some of the <jats:inline-formula id=\"j_mcma-2022-2125_ineq_9997\">\n                     <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:msup>\n                              <m:mi>N<\/m:mi>\n                              <m:mi>s<\/m:mi>\n                           <\/m:msup>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_mcma-2022-2125_eq_0029.png\"\/>\n                        <jats:tex-math>{N^{s}}<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula> points. This approximation is much less expensive that computing the star discrepancy, but still accurate enough to provide information on convergence. Our numerical results show that the random walk algorithm has the same convergence rate as the Monte Carlo method, which is <jats:inline-formula id=\"j_mcma-2022-2125_ineq_9996\">\n                     <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mrow>\n                              <m:mi>O<\/m:mi>\n                              <m:mrow>\n                                 <m:mo stretchy=\"false\">(<\/m:mo>\n                                 <m:msup>\n                                    <m:mi>N<\/m:mi>\n                                    <m:mrow>\n                                       <m:mo>-<\/m:mo>\n                                       <m:mfrac>\n                                          <m:mn>1<\/m:mn>\n                                          <m:mn>2<\/m:mn>\n                                       <\/m:mfrac>\n                                    <\/m:mrow>\n                                 <\/m:msup>\n                              <\/m:mrow>\n                           <\/m:mrow>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_mcma-2022-2125_eq_0035.png\"\/>\n                        <jats:tex-math>{O(N^{-\\frac{1}{2}}}<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>).<\/jats:p>","DOI":"10.1515\/mcma-2022-2125","type":"journal-article","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T09:00:11Z","timestamp":1666256411000},"page":"341-348","source":"Crossref","is-referenced-by-count":1,"title":["A random walk algorithm to estimate a lower bound of the star discrepancy"],"prefix":"10.1515","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9131-814X","authenticated-orcid":false,"given":"Maryam","family":"Alsolami","sequence":"first","affiliation":[{"name":"Department of Computer Science , Florida State University , Tallahassee , FL 32306-4530 , USA ; and College of Computers and Information Systems, Umm Al-Qura University, Mecca, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3058-4580","authenticated-orcid":false,"given":"Michael","family":"Mascagni","sequence":"additional","affiliation":[{"name":"Department of Computer Science , Florida State University , Tallahassee , FL 32306-4530; and National Institute of Standards & Technology, ITL, Gaithersburg, MD 20899-8910 , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"key":"2023040101453612288_j_mcma-2022-2125_ref_001","doi-asserted-by":"crossref","unstructured":"J.  Dick and F.  Pillichshammer,\nDigital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration,\nCambridge University, Cambridge, 2010.","DOI":"10.1017\/CBO9780511761188"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_002","doi-asserted-by":"crossref","unstructured":"C.  Doerr and F.-M.  De Rainville,\nConstructing low star discrepancy point sets with genetic algorithms,\nProceedings of the 15th annual conference on Genetic and evolutionary computation,\nAssociation for Computing Machinery, New York (2013), 789\u2013796.","DOI":"10.1145\/2463372.2463469"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_003","doi-asserted-by":"crossref","unstructured":"C.  Doerr, M.  Gnewuch and M.  Wahlstr\u00f6m,\nCalculation of discrepancy measures and applications,\nA Panorama of Discrepancy Theory,\nLecture Notes in Math. 2107,\nSpringer, Cham (2014), 621\u2013678.","DOI":"10.1007\/978-3-319-04696-9_10"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_004","doi-asserted-by":"crossref","unstructured":"M.  Gnewuch, A.  Srivastav and C.  Winzen,\nFinding optimal volume subintervals with k-points and calculating the star discrepancy are NP-hard problems,\nJ. Complexity 25 (2009), no. 2, 115\u2013127.","DOI":"10.1016\/j.jco.2008.10.001"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_005","doi-asserted-by":"crossref","unstructured":"M.  Gnewuch, M.  Wahlstr\u00f6m and C.  Winzen,\nA new randomized algorithm to approximate the star discrepancy based on threshold accepting,\nSIAM J. Numer. Anal. 50 (2012), no. 2, 781\u2013807.","DOI":"10.1137\/110833865"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_006","unstructured":"Y.  Li,\nThe computational measure of uniformity,\nMaster\u2019s thesis, Florida State University, Department of Computer Science, 2000."},{"key":"2023040101453612288_j_mcma-2022-2125_ref_007","doi-asserted-by":"crossref","unstructured":"W. J.  Morokoff and R. E.  Caflisch,\nQuasi-random sequences and their discrepancies,\nSIAM J. Sci. Comput. 15 (1994), no. 6, 1251\u20131279.","DOI":"10.1137\/0915077"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_008","doi-asserted-by":"crossref","unstructured":"W. J.  Morokoff and R. E.  Caflisch,\nQuasi-Monte Carlo integration,\nJ. Comput. Phys. 122 (1995), no. 2, 218\u2013230.","DOI":"10.1006\/jcph.1995.1209"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_009","doi-asserted-by":"crossref","unstructured":"G.  \u00d6kten, M.  Shah and Y.  Goncharov,\nRandom and deterministic digit permutations of the Halton sequence,\nMonte Carlo and Quasi-Monte Carlo Methods 2010,\nSpringer Proc. Math. Stat. 23,\nSpringer, Heidelberg (2012), 609\u2013622.","DOI":"10.1007\/978-3-642-27440-4_35"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_010","unstructured":"M.  Shah,\nQuasi-Monte Carlo and genetic algorithms with applications to endogenous mortgage rate computation,\nPh.D. thesis, The Florida State University, Department of Mathematics, 2008."},{"key":"2023040101453612288_j_mcma-2022-2125_ref_011","doi-asserted-by":"crossref","unstructured":"M.  Shah,\nA genetic algorithm approach to estimate lower bounds of the star discrepancy,\nMonte Carlo Methods Appl. 16 (2010), no. 3\u20134, 379\u2013398.","DOI":"10.1515\/mcma.2010.014"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_012","doi-asserted-by":"crossref","unstructured":"E.  Thi\u00e9mard,\nAn algorithm to compute bounds for the star discrepancy,\nJ. Complexity 17 (2001), 850\u2013880.","DOI":"10.1006\/jcom.2001.0600"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_013","doi-asserted-by":"crossref","unstructured":"E.  Thi\u00e9mard,\nOptimal volume subintervals with k points and star discrepancy via integer programming,\nMath. Methods Oper. Res. 54 (2001), no. 1, 21\u201345.","DOI":"10.1007\/s001860100141"},{"key":"2023040101453612288_j_mcma-2022-2125_ref_014","doi-asserted-by":"crossref","unstructured":"P.  Winker and K.-T.  Fang,\nApplication of threshold-accepting to the evaluation of the discrepancy of a set of points,\nSIAM J. Numer. Anal. 34 (1997), no. 5, 2028\u20132042.","DOI":"10.1137\/S0036142995286076"}],"container-title":["Monte Carlo Methods and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2022-2125\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2022-2125\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,1]],"date-time":"2023-04-01T21:44:47Z","timestamp":1680385487000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2022-2125\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":14,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,10,19]]},"published-print":{"date-parts":[[2022,12,1]]}},"alternative-id":["10.1515\/mcma-2022-2125"],"URL":"https:\/\/doi.org\/10.1515\/mcma-2022-2125","relation":{},"ISSN":["0929-9629","1569-3961"],"issn-type":[{"type":"print","value":"0929-9629"},{"type":"electronic","value":"1569-3961"}],"subject":[],"published":{"date-parts":[[2022,10,21]]}}}