great explanation and visuals.
but I do not quite get the way the arrangements of sheep are treated. They seem to be counted in the standard "Unordered Sampling with Replacement" fashion.
>Just as the sheep wander about the plots of land in the farm, these packets of energy randomly shuffle among the atoms in the solid.
this would mean that any "packet" of energy is equally likely to be in any of the buckets and the "packets" are independent of each other. so we have an equal distribution on the product space with 6^6 elements.
but then later
> Now, let’s assume the sheep are equally likely to be in any of these 462 arrangements. (Since they move randomly, there's no reason to prefer one arrangement over another.)
under the prior assumptions these arrangements would not be equally likely. e.g. "all sheeps in plot 1" would be far less likely than "each sheep in a different plot"
am I missing something here?
in any case the same conclusions can be drawn in both cases, only that the concentration around 3 is already more pronounced in the "6 sheep, 6 plots" case using the product space model.
I think the confusion is in the way that sheep as a word can be both plural and singular. Specifically, one sheep is as likely to be in any single spot compared to any other single spot. It’s when you get to more than one sheep that you see the distributions
"[the paper] gives a refined version of the sieve that takes less time and less space."
It is not about the time-complexity which is "almost" linear in any case (and even slightly worse than the classical version O(nlog(log(n)) vs O(nlog(n)), but about the space complexity, which is "almost" O(n^(1/3)) vs O(n^(1/2) ( or the classical "naive" O(n))
>Just as the sheep wander about the plots of land in the farm, these packets of energy randomly shuffle among the atoms in the solid.
this would mean that any "packet" of energy is equally likely to be in any of the buckets and the "packets" are independent of each other. so we have an equal distribution on the product space with 6^6 elements.
but then later
> Now, let’s assume the sheep are equally likely to be in any of these 462 arrangements. (Since they move randomly, there's no reason to prefer one arrangement over another.)
under the prior assumptions these arrangements would not be equally likely. e.g. "all sheeps in plot 1" would be far less likely than "each sheep in a different plot" am I missing something here?
in any case the same conclusions can be drawn in both cases, only that the concentration around 3 is already more pronounced in the "6 sheep, 6 plots" case using the product space model.