Talk:Low-discrepancy sequence

Are these the same as quasi-random or sub-random sequences (that terminology is used in Numerical Recipes)? If so it would be good to say so. Josh Cherry 23:10, 15 May 2004 (UTC)

Hi Josh. Yes, they are the same. I have added quasi-random and sub-random as synomyms, and put NR on the list of references. The NR discussion will probably be more comprehensible to many readers. I've also made quasi-random, sub-random, quasirandom, and subrandom redirect to low-discrepancy sequence in an effort to head of duplication of the topic. Hope this helps, Wile E. Heresiarch 16:17, 16 May 2004 (UTC)

entry for Jurjen Ferdinand Koksma

Hi,

This page should have a reference to Jurjen Ferdinand Koksma, after whom some of the items on this page are named. He was a professor at the University of Amsterdam.

Explicit discrepancy calculations

Hello, I wonder if we can put in the discrepancy calculated for some examples. E.g. uniform distribution of points, pseudo-random, maybe some other patterns. I think that those examples would shed some light on low-discrepancy sequences in comparison. Have a good day. 64.48.193.123 18:36, 15 January 2006 (UTC)

Error in definition?

Is there perhaps an error in the definition given in the first sentence? It says, "for all N, the subsequences x₁, ..., x_N and x₁, ..., x_N+1 are almost uniformly distributed." But that x₁, ..., x_N+1 is almost uniformly distributed follows immediately from the fact thet x₁, ..., x_N is (for all N), when used for N + 1. -- Meni Rosenfeld (talk) 13:12, 15 August 2006 (UTC)

I noticed the same. Further, the intro promises that the notion "almost uniformly distributed" will be made precise, but it is never defined. Presumably the definition is something like "having a low discrepancy", but, although "discrepancy" ("Star-Discrepancy"?) is defined (in an unnecessarily hard-to-understand way; what the h*** is "Niederreiter's notation"?), it is never defined what counts as "low" here. Also, presumably, it is a stronger notion than equidistributed, but no relation is made. --Lambiam^Talk 21:50, 16 August 2006 (UTC)

Rearrangement

I've created discrepancy of a sequence as a redirect "with possibilities". I'm thinking of moving some of the definitions and properties from here and from equidistributed sequence across to make that into a proper article. Richard Pinch (talk) 06:26, 19 August 2008 (UTC)

Clarification needed

What is

$\prod _{i=1}^{s}[a_{i},b_{i})$

(in Definition of discrepancy). Is it an intersection of sets / intervals? Then one should be using $\cap$. TomyDuby (talk) 02:38, 26 September 2008 (UTC)

It's an s-dimensional interval or box which is the Cartesian product of s one-dimensional half-open half-closed intervals. I've expanded the definition in the article. Richard Pinch (talk) 05:51, 26 September 2008 (UTC)

Merge

It seems to me that the new article subrandom numbers should be merged here. Is anyone willing and able to do this? Sławomir Biały (talk) 11:48, 7 April 2011 (UTC)

 Done. The previous "low-discrepancy sequence" article seemed to be much more technical than the "subrandom numbers" article, so my first draft of a merged article simply put all the text of the "subrandom numbers" article up front, in accordance with WP:UPFRONT.

But I still wonder -- is "low-discrepancy sequence" really exactly synonymous with "subrandom numbers"? Originally one of these articles said yes, they are completely synonymous, while the other article implied they were not exactly synonymous, but there was a lot of overlap. I hope someone will improve this article by adding a clear explanation of what (if anything) is different between these two categories of sequences. I hope that now that it's been merged into one article, such inconsistencies will be easier to see and fix. --DavidCary (talk) 17:15, 4 January 2014 (UTC)

Constructions of low-discrepancy sequences

There seems to reason for that to be a separate article. Deltahedron (talk) 16:52, 26 August 2012 (UTC)

Conclusion from Koksma-Hlawka

In the article it is said that since the KH inequality is sharp

   "... the quality of a numerical integration rule depends only on the discrepancy D*N(x1,...,xN)."

I think that may lead people to wrong conclusions, as it's is valid only, if all that you know about the function to integrate is, that it has bounded variation. If you know more (e.g. continuity, differentiability, ...) there may indeed be better integration rules. Thus I would like to extend the sentence a little bit in that sense. Would that be ok? Ezander (talk) 16:58, 28 November 2012 (UTC)

Merge from Constructions of low-discrepancy sequences

Per the talk page suggestion by Deltahedron, I've boldly merged the prose from Constructions of low-discrepancy sequences into this article and rearranged the sections a bit. With two merges, there is more work to be done to get the article flowing nicely. --Mark viking (talk) 00:35, 20 February 2014 (UTC)

Per WP:MTAA it might be an idea to put the concrete examples first, to motivate the subject in a qualitative way, before the presentation of the more general theoretical results. Jheald (talk) 07:54, 20 February 2014 (UTC)

"Additive recurrence" section: Useful information removed & incorrect information added

Over the past few months, people seem to have removed the most useful information from the "Additive recurrence" section, namely a couple good examples that are valid and easily verifiable. When I happened upon this page before, I checked them, and they were indeed both better than the ones I'd already found; it's information that's hard to find but easy to verify. When I came back to this page today to check what the numbers were, (because I needed a good additive recurrence sequence again), the examples had been removed. Nobody is about to remove the useful examples on the Taylor series page for lack of citations, because they're easily verifiable, correct, and useful examples, so I'm going to add these easily verifiable, correct, and useful examples back. The importance of always using different coefficients for each dimension in multiple dimensions is also critical to note, since you'll effectively lose an entire dimension of coverage if even two of them are the same.

Sure enough, a highly misleading (effectively incorrect) sentence has also been added: "Note, however, that such a generator is known to have severe statistical flaws. The list of pseudorandom number generators provides better alternatives." It appears that someone was under the incorrect impression that the purpose of the additive recurrence is to generate independent random numbers, which is not at all the case. The entire point of low discrepancy sequences is to have better coverage than independent random numbers, so pseudorandom number generators are not "better alternatives" at all, and there is no "statistical flaw", let alone a "severe" one. They produce significantly higher discrepancy sequences. I'll change this sentence to a clarification that this does not generate random numbers, even though it's made fairly clear in the introduction of the article.

If anyone takes issue with these changes, please discuss here. Ndickson (talk) 03:49, 13 September 2014 (UTC)

I removed a sentence that was sourced to a blog here: the blog being http://mollwollfumble.blogspot.com. In general we don;t accept such things as reliable sources, see WP:SPS. In that case, the sentence was too terse to make sense. I see that this addition is sourced to the same blog. It seems that the material was originally at Subrandom numbers, created by User:Mollwollfumble. Even though it reads better now, we cannot accept material that is not attributable to an independent reliable source. Deltahedron (talk) 11:12, 13 September 2014 (UTC)

I completely appreciate the need to indicate that the material requires more independent reliable sources, since there's no reference to any independent, reliable source regarding the entire "Additive recurrence" section. (The reference to The Art of Computer Programming was actually about LCG random number generators, not low discrepancy sequences.) Despite that, I wouldn't recommend deleting the section, because it contains information that's verifiably true and useful. (At least, I've found it useful in two completely unrelated scenarios now.) It should really just be marked as needing more reliable sourcing.

I managed to find a published academic paper briefly discussing this type of low discrepancy sequence (http://www.math.ucla.edu/~caflisch/Pubs/Pubs1990-1994/Morokoffsisc1994.pdf in section 4), and it mentions this type before any other, but it doesn't cite anything for the origin of it or determine exact discrepancy for different coefficients, (just mentioning that its discrepancy scales as ((log N)^s)/N, where s is the number of dimensions), seeming to dismiss it as being too simple to be worth analysing. Everything else I looked at seems to be behind a paywall or not discussing this particular type of sequence. Ndickson (talk) 03:38, 15 September 2014 (UTC)

Missing documentation of the 2D sequence in the figure (c₁ = 0.5545497, c₂ = 0.308517)

A comment related to the topic "Additive recurrence": I am aware that an earlier contributor has done a thorough optimization study, and concluded that c1 = 0.5545497, c2 = 0.308517 are optimal for 2D additive recurrence sequences. However, some of this documentation seems to have been removed by later edits, and only the 2D figure remains, with caption text. I do not know which discrepancy criterion was used by the contributor. It would therefore be greatly appreciated if any contributor can add documentation about the source of these two coefficients (or re-calculate them), together with the discrepancy criterion. — Preceding unsigned comment added by Peter.schild (talk • contribs) 07:27, 19 July 2022 (UTC)

LHS

Hi, should LHS appear there ?195.83.81.127 (talk) 13:35, 24 October 2014 (UTC)

Latin hypercube sequences? If so, there are sources out there comparing the utility of LHS and LDS in Monte Carlo simulations, so I think it would be appropriate to include a summary of those comparisons. Latin squares are already mentioned in the article. --Mark viking (talk) 16:04, 24 October 2014 (UTC)

"Random numbers" section

The section Low-discrepancy_sequence#Random_numbers has no citations, and I think it's basically totally wrong. Meaning, alternating between r_i and r_i + 1/2 will reduce your discrepancy almost not at all compared to drawing samples from the full uniform distribution. Any objections to me removing the section? Danstronger (talk) 00:43, 1 February 2020 (UTC)

"QRNG" listed at Redirects for discussion

A discussion is taking place to address the redirect QRNG. The discussion will occur at Wikipedia:Redirects for discussion/Log/2021 December 8#QRNG until a consensus is reached, and readers of this page are welcome to contribute to the discussion. Chumpih. (talk) 08:02, 8 December 2021 (UTC)

Using Incorrect Sample Sizes

This article is filled with "Examples" of QMC sequences using invalid sample sizes. Using a Sobol sequence with 1,000 points, for example, is incorrect, as Sobol sequences must have exactly 2^n points. Using non-powers of 2 destroys the (t, m, s)-net (equidistribution) property, which is what guarantees faster convergence than you get from pseudo-random numbers. Closed Limelike Curves (talk) 00:48, 28 September 2022 (UTC)

+1 here. Art Owen wrote a paper about it, see Owen2020 for extended discussions. Tupui (talk) 09:17, 24 February 2023 (UTC)

+1. I read Owen2020 paper as pointed out by Tupui, and power of 2 should be indeed used. I am happy to change it by using R or Python scripts. Along the plots with the correct number of samples, I can provide its basic code in a specific code-cell. Rob Formi (talk) 12:16, 31 August 2024 (UTC)