A slight discrepancy | Hacker News Reader

A slight discrepancy

bit-player.org

77 pointswglb13 comments

Say what you want about human perception of randomness, but I definitely find the raindrops to be more visually appealing than pseudo or quasi random.

As was said in the other comments, it seems to me that the distinguishing feature is the average spacing around each point, most likely caused by droplets aggregating when too close.

This is one of those things that always drives me crazy with iTunes shuffle feature with the dj thing, repeat frequency. Yes, I want random, no, I don't want songs to repeat immediately. If someone could fix this with a pseudo-quasi "random" algorithm I'd be eternally grateful.

iTunes used to have a slider in the settings that would make it "more random" (would try to play songs from different artists and albums). Apparently, it got removed around iTunes 8: http://hintsforums.macworld.com/archive/index.php/t-93993.ht...

1) The rain is not really random, since only when droplets get large enough do they drop to the earth. To get large they will accumulate whatever is closest around them, meaning a sheet of evenly-spaced vapor (due to the diffusive properties of gas) quickly becomes a sheet of larger droplets evenly spaced. And this even spacing falls to the ground - granted with some intervention by the wind etc but the point is the rain is not all that random.

2) The same thing happens on the surface of the table, right? Smaller droplets converge into larger ones as more rain falls and pushes them together. And there is a maximum size of dot before it turns into a lake and runs off the table. So eventually you get what tends to be a fairly even distribution of dots of a certain size.

Anyway I could be totally off-base with all of this, but let me just say this is a fascinating problem and what a curious mind to have come up with it!

Thanks! I now have the language to describe the highly annoying fact that the ipod shuffle algorithm seems to be pseudorandom when I wish it was quasirandom!

You mean: Shuffle should shuffle, like a deck of cards, and not draw with replacement?

Does it really? I can't really test this because I don't have an iPod shuffle, but in iTunes shuffle+repeat will

  1. generate a random permutation of the playlist
  2. play all the way through it
  3. goto 1

This does mean that for a playlist of N songs, you'll hear the same song consecutively about once every N^2 songs.

The problem comes about I think when you are constantly opening the iPod app on your iPhone and starting again each time in shuffle mode rather than resume. So the playlist gets regenerated each time. I feel like there are songs I've heard 50 times and plenty of songs I've never heard come up. Would be much better if it aimed for an even distribution.

My algorithm for playing songs indefinitely in a random order:

1. let S = set of songs to be played

2. let N = number of songs

3. repeat until bored:

3.1. let R = set of last [N / 2] songs we played

3.2. pick a song at random from S \ R; play it

You may want to tweak step 3.2 to give higher probabilities of picking songs that haven't been played for longer.

A few points:

* you might expect raindrops themselves to be quasi-random since they are formed by accumulation of humidity in small areas

* the surface tension of the drops would certainly help in accumulating nearby drops in the table mesh, but not enough by itself to combine nearby cells (which you can see with several examples in the picture)

* I suspect the filled-cells are formed by condensation along the wire mesh instead of drops falling directly into each hole, and since the condensation would be evenly distributed (the air around the table will have uniform humidity), you would expect the filled cells to be regularly distributed like this since a drop forming in a cell would use condensation required by neighbors to form drops

>I realized there are only finitely many candidate rectangles that might possibly maximize the discrepancy. They are the rectangles in which each of the four sides passes through at least one dot.

That's really a non-trivial insight. It makes perfect sense once you hear it, but I'm not sure any amount of thought would have lead me to it were I in the author's position.

For what it's worth, it occurred to me right away. If you spend any time learning about and solving continuous optimization problems, one of the first patterns you notice is the existence of criteria that narrow possible optima to a finite number of possible points. For example, using basic calculus on differentiable optimization functions these are the "critical points". In linear programming, we can consider only the vertices of the polytope defined by the constraints.

If such reasoning doesn't occur to you right away, you might also discover this fact by considering a candidate rectangle and considering how changing it slightly changes the discrepancy. A very simple kind of change would be one in which no points enter or leave the rectangle, which leads to this observation.

At first glance, how I'd find the maximum:

1. Reorient the cells from paralellograms to squares, with integer coordinates.

2. Create lookup tables, with dots from the origin to a given (x, y).

3. Any given rectangle:

  A  B

  C  D

has a count given by the lookup tables for B and C, minus A and D.

4. Then, iterate over all the rectangles.

I guess with a set this sparse, you could numerate all the useful x and y to check, and skip step 1.

Edit: I chose the bottom left as the origin, incidentally.

>>The pseudorandom pattern has both tight clusters and large voids.

This is similar to the distribution of galaxies due to gravity within the observable universe: http://astronomia.net/cosmologia/cfAsurvey.gif

Reply on news.ycombinator.com