possiblywrong

letzten Monatdiscuss

The article deserves several clarifications:

> The deck has to be cut more or less in half before shuffling.

"More or less" is doing some heavy lifting here. The original GSR shuffling model cuts the deck at a point that is binomially distributed, so that for example about one-fifth of the time the cut may be at least as asymmetric as a 21-31 card split, which I think most would agree is nowhere near "the precision of a professional magician."

Also note that the theorem in the paper really focuses only on relaxing the cutting model; the model of subsequent interleaving of the resulting piles is the same, dropping a card from a pile with probability proportional to the size of the pile. (Equivalently but perhaps less intuitively, for the original GSR model with the binomial cut, imagine flipping a fair coin for each card in the deck, then "de-interleaving" by sliding the "heads" cards out, preserving their relative order, and placing that pile on top of the remaining "tails" cards.)

> But with that seventh shuffle, the deck suddenly tips into a highly unstructured state.

More accurately, the total variation distance from a uniform distribution first drops below 0.5 at seven shuffles[0]. The actual cutoff phenomenon's asymptotic result would suggest 3/2 lg n shuffles for a deck with n cards, which for n=52 would be closer to nine shuffles.

[0] https://possiblywrong.wordpress.com/2018/09/02/arbitrary-pre...

possiblywrong

vor 7 Monatendiscuss

Following is the closed form solution linked in the article (from a since-deleted Reddit comment):

    from functools import reduce

    def recurrence(ops, a0, n):
        def transform(x, op):
            return eval(repr(x) + op)
        ops = ops.split()
        m = reduce(transform, [op for op in ops if op[0] in ('*', '/')], 1)
        b = reduce(transform, ops, 0)
        for k in range(n + 1):
            print('Term 0: ', a0 * m ** k + b * (m ** k - 1) / (m - 1))

> This is really only interesting if a particular (potentially really large) term of the sequence is desired, as opposed to all terms up to a point. The key observation is that any sequence of the given set of operations reduces to a linear recurrence which has the given solution.

possiblywrong

vor 7 Monatendiscuss

It's interesting that the two forward versions of the algorithm were added to Wikipedia just a few months ago. (The OP article is from 2020.)

possiblywrong

letztes Jahrdiscuss

> Second, the least significant bits that come from this generator are biased.

I don't think this is true; I'm guessing that the author borrowed this observation from one of the various other articles linked in this thread, that address the situation where we draw a 64-bit random unsigned integer and divide by `1<<64`, instead of drawing 53 bits and dividing by `1<<53`. The former does introduce a bias, but the latter doesn't (but does still limit the fraction of representable values).

possiblywrong

vor 2 Jahrendiscuss

You are correct. The first example time in the article, "2024-12-25 at 18:54:53 UTC", corresponds to POSIX timestamp 1735152893, not 1735152686. And there have been 27 leap seconds since the 1970 epoch, not 29.

possiblywrong

vor 2 Jahrendiscuss

Author of the linked article here; you're right that just the expected number of guesses is roughly monotonic. However, that expected number of guesses (along with Ballmer's expected payout) increases, not decreases, as N increases, with a sharp step downward, not upward, each time N reaches a power of two.

The intent here is to reasonably compare hypothetical job interview questions for different N. If N=100, then Ballmer offers 6 dollars in exchange for one dollar per guess, and the linked Gukov article shows that Ballmer's expected return is negative.

What if he instead challenged an interview candidate with N=127? What about N=255, or N=511, etc.? He presumably wouldn't continue to offer only 6 dollars to play in these cases, but also presumably a similarly nice round number of dollars... and now the question/conjecture is interesting: from the updated graph, it looks like Ballmer's expected return decreases as N=2^k-1 increases, but does it always remain positive? Or is there some sufficiently large key space beyond which even an optimal guesser can't ever win on average?

To me, this question seems easier to ask when the expected return is presented in this way. That is, does each sawtooth interval always span zero expected return?

possiblywrong

vor 2 Jahrendiscuss

> Note that if F(x,y)=0, then the point (x,y) is exactly on the circle. If F(x,y)>0, then the point is outside of the circle, and if F(x,y)<0 then the point is inside of it. In other words, given any point (x,y), F(x,y) is the distance from the true circle line [my emphasis].

This last is not quite true. The exact distance from the circle, call it G(x,y), is the corresponding difference of square roots, i.e.,

  def G(x, y, r):
    return math.sqrt(x * x + y * y) - math.sqrt(r * r)

and G(x,y) isn't just the square root of F(x,y), and indeed doesn't behave monotonically with respect to F(x,y).

It's an interest property of Bresenham's algorithm, that I've never seen even stated let alone proved in the literature, that this doesn't matter, and the algorithm is indeed exact in the sense that it always chooses the next point based on which is truly closest to the circle... despite using an error function that is only an approximation.

possiblywrong

vor 3 Jahrendiscuss

There was some amount of "standardization" of checksum methods to help with debugging typos. For example, Nibble magazine used a couple of programs-- the one I remember using was Key Perfect-- that would scan your program in memory after you typed it in, and report a series of short hex checksums, one for each reasonably small chunk of program (bytes for machine language, or lines of BASIC code). The magazine article would include the correct Key Perfect checksums for the program; compare against the generated report, and a difference meant you "only" had to scan a dozen lines of source instead of hundreds.

possiblywrong

vor 3 Jahrendiscuss

Author of the linked article here; re marking movement of shadows, I wrote a follow-up that discusses some alternatives, mainly that one:

https://possiblywrong.wordpress.com/2014/07/05/using-a-watch...

possiblywrong

vor 7 Jahrendiscuss

> You don't need to manually count, just make sure all the circles are the correct colors.

I guess this takes me a while, and seems significantly more error-prone to me than the corresponding re-count when they are sorted. Granted, it's pretty easy when the Skittles are sorted as they are in these images. But how quickly can you scan this image: https://imgur.com/a/KpddGdH and check whether there are any errors? And how confident are you in that visual check?

You are right that this approach may be good enough to find a duplicate, which was the primary objective of the experiment. But I had hoped that this might also serve as a useful dataset for future student exercises, in probability, or even in just this sort of computer vision project... but I wanted to have accurate ground truth, so to speak. Inspecting your spreadsheet, it looks like this algorithm is still less than 95% accurate, even if we only evaluate the "clean" images with Uncounted=0.

possiblywrong

vor 7 Jahrendiscuss

Author of the article here; I suppose I should confess that I did consider automating the counting, which did seem like an interesting problem... but I rejected the idea, for what I think is good reason: the sorting was the time-consuming part. If we skip the sorting, and depend on the code to get the counting right, and we assume that we are at worst off by one-- or more realistically, off by two, to account for the questionably-identifiable chunks of paste and such-- then how often do we need to go back for manual verification?

With hindsight (although up-front simulation bore this out as well), we see that we would have to go back and manually verify anywhere from 8% (off-by-one) to 25% (off-by-two); that's every fourth pack. Now consider how much more unpleasant that manual counting is, since the Skittles are haphazardly un-arranged in the image. In short, I'm unconvinced that an automated-- while similarly accurate-- accounting would be that much more efficient.

possiblywrong

vor 7 Jahrendiscuss

Author of the article here; you have a point that there is no explicit discussion of validating this assumption, beyond the variability shown in the colored curves in the "count per pack" plot.

Having said that, this small sample is indeed reasonably consistent (or at least not inconsistent) with that iid assumption for the color of each individual Skittle. We would not expect to see any 80+% red packs even assuming that color was perfectly uniformly iid, because the probability of observing such a pack is so small (less than 10^(-19)).

However, still assuming this model, we should expect to see packs with very small proportion of reds... and we do, with one pack having just 3 red Skittles, for example. The entire distribution of proportion of red follows the assumed binomial distribution very closely.

possiblywrong

vor 7 Jahrendiscuss

Author of the article here-- right! This was the key "real world" motivation for this experiment as an attempt at a pedagogical tool; from the article:

> As an aside, I think the fact that this particular concrete application happens to be recreational, or even downright frivolous, is beside the point. For one thing, recreational mathematics is fun. But perhaps more importantly, there are useful, non-recreational, “real-world” applications of the same underlying mathematics. Cryptography is one such example application; this experiment is really just a birthday attack in slightly more complicated form.

possiblywrong

vor 7 Jahrendiscuss

Author of the article here; this is a great point. This experiment initially stemmed from a nice analytical solution to the problem of computing the expected value (via generating functions as described in the post). Computing other moments, let alone the entire distribution, required some Monte Carlo simulation, as shown at the end of the first article (https://possiblywrong.wordpress.com/2019/01/09/identical-pac...) before I started the experiment.

And even this histogram assumes a distribution of total number of Skittles per pack (that varies) that I had to guess at beforehand. In hindsight, the final sample distribution suggests that I probably initially overestimated the true variance, and thus also overestimated the expected number of packs I would need to inspect. In other words, this experiment arguably took longer than "average."

So you're right-- this experiment could have extended into 700 packs, 800 packs... and still have been consistent with the assumed model, but I would have simply been in an unfortunate 90-th percentile possible universe where it took much longer than "average."

possiblywrong

vor 12 Jahrendiscuss

> "For these reasons, I'm actually a bit surprised that the author's data matches the theory so closely... The fit is so perfect I actually suspect he... ah... played with his data slightly after the fact. A "fortuitous" choice for alpha is obviously helpful too."

Author of the linked blog post here. I made the comment that "if I had instead chosen 12, or 13 (for alpha), the resulting predictions would not agree nearly as well." This is perhaps overstating the "luck" of my initial midpoint choice. Here is a quick plot showing the same data with predictions using 12, 12.5, and 13: http://imgur.com/lP5sjwB

(Note also that a better least-squares estimate of alpha is actually about 12.7.) Even these "endpoints" still look to be in reasonable agreement with measurements. That is, if 12 to 13 calories per pound really represents most of the range of variability among the (male) population, then one can likely make useful predictions without needing to be spot-on with their choice of alpha.

Of course, it's a valid question whether 12 to 13 really covers a large chunk of the distribution. Are there men out there with alpha<10, or >15, for example?

possiblywrong

Submissions

Beware the "Natural" Quaternion

The Fisher-Yates shuffle is backward

Hierarchical field sort with string interning

There Is No Equilux

comments