The continuous elevator

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

The continuous elevator

Postby imatrendytotebag » Thu Jan 29, 2009 6:33 am UTC

Here's a problem I came up with related elevator dynamics. (also data reading, and other things)

We have an "elevator" X on a line segment of length 1. X moves at a constant speed v throughout the problem (0 < v < 1), where v is is units distance per second. Each second, a dot is placed on the line segment with equal probability of being placed anywhere. Whenever the elevator X "collides" with a dot, that dot is immediately deleted.

The object of the elevator is to minimize the expected time a dot waits before it is deleted. It seems clear to me that the elevator should be constantly moving toward the dot which has been in existence the longest. If it follows this algorithm, what is the expected waiting time of a dot?
Hey baby, I'm proving love at nth sight by induction and you're my base case.

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: The continuous elevator

Postby ++$_ » Thu Jan 29, 2009 7:08 am UTC

imatrendytotebag wrote:It seems clear to me that the elevator should be constantly moving toward the dot which has been in existence the longest.
Is this always the case? Suppose the first dot is placed at 0.99, the second dot at 0.01, and the elevator starts at 0.5, moving at 0.01 units per second. The third through 40th dots are all placed above 0.99. Shouldn't the elevator collect those first before going south towards the 0.01 dot?

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: The continuous elevator

Postby Xanthir » Thu Jan 29, 2009 1:44 pm UTC

Hah, didn't read your first line until afterwards. This sounds *exactly* like a problem statement of an optimal seektime algorithm for hard drives. I'd look into any literature on that subject.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

gnuoym
Posts: 30
Joined: Wed Jan 07, 2009 7:38 pm UTC

Re: The continuous elevator

Postby gnuoym » Thu Jan 29, 2009 2:51 pm UTC

Since the points are truly random, I think the best method is to just travel back and forth from 0,1 over and over. The worst case scenario is a wait time of 2/v, but the average should be no worse than 1/v and I'd wager most wait times are less. I just don't have the time to try and nail down an actual value. Someone with a better grasp will certainly correct me for you though. :D

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The continuous elevator

Postby Yakk » Thu Jan 29, 2009 3:21 pm UTC

Did you mean average? Because average ... well, it don't work like that.

One dot is added at 0. Then dots are added, two at a time, at 0.9 and 1.0, every 0.1 seconds. This just happens, randomly...

It is never in the interests of the elevator to head down to the 0, if the goal is to reduce the average wait time of dots after they are spawned.

Unless your goal is to have the least wait time of dots that are in existence at any one time?

The idea is that each DoT contributes (1/# of total dots) units to the average every second. Regardless of how old it is already.

...

A naive solution would be to head in the direction that generates a path that eats all of the visible dots in the way that keeps the average the lowest (note that this might be computationally difficult ... but probably not. It is, however, easy to solve by just looking at the entire decision tree...). A more complex solution would have to take into account new dots coming into existence -- two equal paths in time and average that end at the middle, and at the edge, have the property that the middle is likely to do better in eating a randomly produced dot.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

gnuoym
Posts: 30
Joined: Wed Jan 07, 2009 7:38 pm UTC

Re: The continuous elevator

Postby gnuoym » Thu Jan 29, 2009 3:52 pm UTC

Yakk wrote:One dot is added at 0. Then dots are added, two at a time, at 0.9 and 1.0, every 0.1 seconds. This just happens, randomly...

It is never in the interests of the elevator to head down to the 0, if the goal is to reduce the average wait time of dots after they are spawned.


Yeah, but the P(X>.9) is only .1 per dot. So what is the likelyhood that the dots 'randomly' only show up at .9 and 1.0, 10^-t? I certainly wouldn't build a model around that exceptional case. And in that example you have 10 dots after 10 secs, 9 w/ a wait time of 1, 1 with a wait time of 10 = 19sec / 10 dots = 1.9 sec average...

Again, I'm assuming I'm wrong, but I love learning why.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The continuous elevator

Postby Yakk » Thu Jan 29, 2009 4:01 pm UTC

The speed dots are spawned, and the velocity v, are two variables that are effective inverses of each other. Make the velocity 0.05 instead of having 2 dots dropped every 0.1 seconds -- same difference. (Ie, that isn't important)

The important point is that "older" dots are no more important to pick up than "newer" dots. If there is an old dot on the far side of the range, and a new dot drops 'just behind you', you turn around and grab that new dot.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

gnuoym
Posts: 30
Joined: Wed Jan 07, 2009 7:38 pm UTC

Re: The continuous elevator

Postby gnuoym » Thu Jan 29, 2009 5:05 pm UTC

We are told the speed the dots are spawned is a constant 1/sec. This is independent of the speed of our elevator.

If you'll allow me a discrete example to illustrate why I'm having trouble with this idea...

Imagine n cash registers that begin empty. Every minute a customer arrives at an empty register. If you are at the register you can process them immediately, but if you aren't it takes some amount of time to move from one register to the next, say 30 seconds. Wouldn't the most effiecient algorithm be to walk up and down the bank of registers and process whomever is there?

Alternately, you wouldn't design a windshield wiper that only swept through 1/2 its arc twice and claim the glass was equally as dry as if it did full sweeps.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The continuous elevator

Postby Yakk » Thu Jan 29, 2009 6:03 pm UTC

*sigh*. Varying the rate of delivery of dots, and varying the speed of the elevator, does the same thing.

In any case, "Wouldn't the most effiecient algorithm be to walk up and down the bank of registers and process whomever is there?" -- no, that is not the most efficient algorithm. If there was only 1 person in line, moving to that person is probably the right option, even if you where moving the other way before hand.

If you had no information about the state of the customer lines, then yes, that might be the right algorithm.

Finally, note that my real complaint is that "average wait time" is not that good of a metric. Average square wait time, for example, is probably better, and would almost certainly prevent starvation (where the dots arrive in such a pattern that it is never optimal to pick up an earlier dot).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

gnuoym
Posts: 30
Joined: Wed Jan 07, 2009 7:38 pm UTC

Re: The continuous elevator

Postby gnuoym » Thu Jan 29, 2009 6:29 pm UTC

I clearly see now that fixing either the spawn time or the speed and varying the other has the same effect on the problem. I didn't get quite that meaning when I read your earlier post.

bray
Posts: 67
Joined: Wed Aug 15, 2007 4:17 pm UTC

Re: The continuous elevator

Postby bray » Fri Jan 30, 2009 3:08 pm UTC

Yakk, are you claiming that minimizing average wait time can lead to a situation where one of the dots never gets picked up? Because if you never pick up one of the dots, then you almost surely will never pick up a constant fraction of the dots, which is going to give you an infinite average wait time. And since there is a strategy that does have a finite average wait time, any strategy minimizing expected average wait time will need to have that situation occur with probability 0.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: The continuous elevator

Postby Buttons » Fri Jan 30, 2009 4:06 pm UTC

To say that some dots might never get picked up but that this happens with probability 0 is not a contradiction. In fact it's true, for appropriate elevator speed.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The continuous elevator

Postby Yakk » Fri Jan 30, 2009 4:11 pm UTC

No, I didn't say you should ignore a constant, or bounded above zero, fraction of the dots. Yes, that leads to an unbounded growth in the average lifetime of dots.

I'm saying that there is no incentive to "get the oldest", because each dot contributes the same amount every second to the "average lifetime of dots before they are picked up".

And I'm saying that the measure "average lifetime of dots before they are picked up" isn't a good measure for things like drive scheduling or picking up people who are waiting at an elevator.

The L2 (or even Linfinity) norms are probably a better measurement of the performance of such an algorithm for a given test case.

Average is often a bad measurement of performance.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: The continuous elevator

Postby quintopia » Fri Jan 30, 2009 6:23 pm UTC

What if you wanted to minimize the average using an algorithm which guarantees the impossibility of starvation? (i.e. there is some length of time t, for which we we can guarantee no dot will ever have been waiting longer than t.)

User avatar
parallax
Posts: 157
Joined: Wed Jan 31, 2007 5:06 pm UTC
Location: The Emergency Intelligence Incinerator

Re: The continuous elevator

Postby parallax » Fri Jan 30, 2009 6:26 pm UTC

In other words, he's saying a restaurant where two people each wait 30min (302+302=1800) is better than one where one person waits 5min and another waits 45min (52+452=2050).

I think the a good solution would be to create a potential function P(x|y,t) for each dot that depends on where and when the dot was created. Sum all of the potentials and follow the gradient. A good candidate might be P(x|y,t) = 1/(y-x). x is the position of the elevator, y is the position of the dot and t is how long the dot has been there. For the square sum, use P(x|y,t) = t/(y-x)2.
Cake and grief counseling will be available at the conclusion of the test.

User avatar
Cycle
Posts: 146
Joined: Mon Feb 25, 2008 1:55 am UTC

Re: The continuous elevator

Postby Cycle » Sat Jan 31, 2009 6:43 am UTC

Using the L1 norm, starvation occurs. In the example you gave: (1, 0.1, 0, 0.1, 0, 0.1, 0,...) starving the one at the top is clearly optimal. The average time is lim (n+(10n-1)*0.1)/(10n) = 0.2

So, yeah, probably better to use L2 norm. It makes calculation easier anyways.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests