RichardKennaway comments on Rationalist horoscopes: A low-hanging utility generator. - Less Wrong

62 Post author: AdeleneDawner 22 May 2011 09:37AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (77)

Comments (77)

You are viewing a single comment's thread. Show more comments above.

Comment author: RichardKennaway 15 June 2011 09:55:29AM 1 point [-]

This suggests an exercise in mathematics and programming:

Given a set of N objects, generate an indefinitely long sequence of random members of the set, such that:

  1. No object is drawn more than once in any consecutive P drawings, for a given P <= N.
  2. Every object is drawn at least once in every consecutive Q drawings, for a given Q >= N.
  3. The probability distribution of the next drawing, given only knowledge of the last P-1 drawings, is uniform over the remaining N-P+1 objects.
Comment author: AdeleneDawner 15 June 2011 10:09:10AM 0 points [-]

I think 2 and 3 are mutually exclusive - 3 is a pretty strict specification of how an item is chosen, and doesn't lend itself to making 2 guaranteed to happen at all.

Comment author: RichardKennaway 15 June 2011 10:14:47AM *  1 point [-]

(3) only says what you know about the next one, given the last P-1. The actual algorithm can know the entire previous history. So if object X has just been passed over Q-1 times, it must be chosen next by (2), but that doesn't violate (3), because that information isn't available from the last P-1 drawings.

ETA: A simple algorithm that I think works is this:

1. Generate the first P-1 items at random, all distinct.
At each subsequent step:
2. If there is an item that has not appeared in the last Q-1 drawings, choose it.
3. Otherwise, choose uniformly from among those that have not appeared in the last P-1 drawings.

This isn't the only possible algorithm. Instead of a uniform distribution in part (3), one might weight it towards those that were last chosen longer ago, with (2) being a special case of that.

Comment author: RichardKennaway 16 June 2011 03:04:26PM 2 points [-]

I couldn't resist programming it. I have a MATLAB function randchoiceseq(N,P,Q,K), where N, P, and Q are as above and K is the length of sequence to generate. If it would be useful for the horoscope site, I can send a copy. Result of randchoiceseq(33,16,40,100):

 8 16 19 18 5 2 15 33 28 1 25 24 26 31 32 10 4 27 20 7
3 16 23 6 33 17 22 13 21 12 14 30 9 19 29 8 11 2 5 18
15 28 25 4 24 26 1 10 32 31 27 3 20 7 16 33 23 19 17 6
13 8 22 21 12 14 30 29 9 25 15 5 2 11 18 28 26 24 32 4
27 1 20 10 3 31 33 23 7 16 17 19 13 29 6 8 14 24 22 21
Comment author: Will_Sawin 16 June 2011 03:15:25PM 0 points [-]

I second the claim that it works.

Powered by Reddit Powered by Reddit