This sounds like a problem for Jim Propp's de-randomization tricks -- converting a random method that has the right asymptotic distribution to a deterministic method that approximates its behavior. But I don't know what the random method with Zipfian distribution would be. --Michael On Sat, Mar 17, 2018 at 11:07 AM, Henry Baker <hbaker1@pipeline.com> wrote:

Suppose that I'm a Fedex driver and I have N houses to visit, but only exactly 1 house every day (i.e., this is NOT a route planning problem). Since I'm an unimaginative Fedex driver, it's simply easier to go to the houses in the same order every cycle of days, whether or not I have something to deliver.

I'd like to come up with a *simple* house visit scheduling algorithm with the following properties:

* For each N, the output is a *fixed* *cyclic* schedule; i.e., after some # of days the entire schedule repeats; we'd like the cycle length to be relatively short and will accept some amount of deviation from Zipf's Law in return

* The % of visits to house #i in each cycle is very roughly proportional to 1/i

* Ideally, the deliveries to house #i should be spread out as much as possible -- i.e., not all bunched together on successive days

* The schedule for N+1 houses is simply computed from the schedule for N houses (alternatively, the schedule for N is computed from an a priori fixed number of schedules from smaller N's)

Here's an example of what NOT to do for Zipf's Law:

Suppose we have 4 houses, with visits scheduled like so:

1 1 2 1 2 3 1 2 3 4

Thus, we have 10 total visits each cycle, but the ratios are 40%, 30%, 20%, 10% -- i.e., this is a linear "tail", rather than a Zipf's Law tail.

Is there such an algorithm which approximates a Zipf's Law distribution?

What about other power laws/long-tail distributions -- e.g., i^(-2) ? Other common distributions?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Forewarned is worth an octopus in the bush.

Additional thoughts after some of Warren's comments: * Obviously, Fedex should visit each house at least once during each cycle, so for Zipf's law we have a lower bound on the cycle length of ~ N*H_N ~ N*log(N) Similarly, for i^(-2) power law, the minimum cycle length ~ N*(N-1) ~ N^2 Adam Goucher has an elegant solution for this one. Similarly, for i^(-3/2) power law, the minimum cycle length ~ 2*N^(3/2). Similarly, for the exponential 2^-i distribution, the minimum cycle length ~ 2^N (think of binary ruler markings). So for 8 houses, Fedex would go to the least popular exponential distribution house only ~once per year! Another deterministic route schedule might instead go to a non-empty subset of the houses on every day, with a visit to the most popular house *every day*, and only occasionally include the less popular houses. So now the question might be how to optimally space the visits to the less popular houses so that they don't "bunch". But this task is somehow simpler, as we can space out round(N*prob(i)) visits to house #i during each cycle of N days. So, getting back to Zipf, is there a clever *algorithmic* way to space out ~round(N/i) visits over N days ? By algorithmic, I mean we don't want to have to spend O(N) time or O(N) space deciding which houses to visit on day #i out of N. At 08:07 AM 3/17/2018, Henry Baker wrote:

Suppose that I'm a Fedex driver and I have N houses to visit, but only exactly 1 house every day (i.e., this is NOT a route planning problem). Since I'm an unimaginative Fedex driver, it's simply easier to go to the houses in the same order every cycle of days, whether or not I have something to deliver.

I'd like to come up with a *simple* house visit scheduling algorithm with the following properties:

* For each N, the output is a *fixed* *cyclic* schedule; i.e., after some # of days the entire schedule repeats; we'd like the cycle length to be relatively short and will accept some amount of deviation from Zipf's Law in return

* The % of visits to house #i in each cycle is very roughly proportional to 1/i

* Ideally, the deliveries to house #i should be spread out as much as possible -- i.e., not all bunched together on successive days

* The schedule for N+1 houses is simply computed from the schedule for N houses (alternatively, the schedule for N is computed from an a priori fixed number of schedules from smaller N's)

Here's an example of what NOT to do for Zipf's Law:

Suppose we have 4 houses, with visits scheduled like so:

1 1 2 1 2 3 1 2 3 4

Thus, we have 10 total visits each cycle, but the ratios are 40%, 30%, 20%, 10% -- i.e., this is a linear "tail", rather than a Zipf's Law tail.

Is there such an algorithm which approximates a Zipf's Law distribution?

What about other power laws/long-tail distributions -- e.g., i^(-2) ? Other common distributions?