“Repeat at most once every 16 days” means they can repeat twice in 17 days (once on day 1, no more for the rest of the 16 days, and again on day 17), but don’t have to. And in this case, they mostly shouldn’t be repeating every 17 days. I’m not sure if we’re seeing a bug in the horoscope-choosing code or it’s just that the unused ones aren’t being given enough of the probability mass, but if it’s been three days in a row I suspect the former. I’ll look into it.
ETA: There’s at least a bug, since horoscope 8 came up twice with about a week between instances. Hopefully Peer will have time to take a look at it tomorrow, and while we’re poking at the code anyway I’ll have him change the default functional score of the unused ones to 3 rather than 1. There may still be another couple days of repeats while we iron things out, though.
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.
(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.
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):
For the past 2 days the horoscopes have been repeating. With only 33 choices it’s bound to happen, but it does seem a bit often.
Also, my english is letting me down. Does “repeat once every 16 days” mean “no more than one instance in any 16 day period” or “no more than 2”?
“Repeat at most once every 16 days” means they can repeat twice in 17 days (once on day 1, no more for the rest of the 16 days, and again on day 17), but don’t have to. And in this case, they mostly shouldn’t be repeating every 17 days. I’m not sure if we’re seeing a bug in the horoscope-choosing code or it’s just that the unused ones aren’t being given enough of the probability mass, but if it’s been three days in a row I suspect the former. I’ll look into it.
ETA: There’s at least a bug, since horoscope 8 came up twice with about a week between instances. Hopefully Peer will have time to take a look at it tomorrow, and while we’re poking at the code anyway I’ll have him change the default functional score of the unused ones to 3 rather than 1. There may still be another couple days of repeats while we iron things out, though.
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:
No object is drawn more than once in any consecutive P drawings, for a given P ⇐ N.
Every object is drawn at least once in every consecutive Q drawings, for a given Q >= N.
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.
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.
(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.
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):
I second the claim that it works.