# Next step: solve in three dimensionsAugust 30, 2011 7:48 AM   Subscribe

Calculusfilter. A man is led to the center of a valuable field which he does not own. He coats his feet in blue paint so that his path can be traced. At dawn he begins walking. At a randomly selected time he will be told to stop walking, whereupon he will walk in a perfectly straight line back to the starting point. Then he will be given all the land that has been circumscribed by his blue path.

What path should the man walk to maximize his expected receipt of land?

Not for any kind of homework; just idle curiosity. More interested in the soluton, the shape and characteristics of the curve that results, than in the math by which you get there (though I'm somewhat interested in that, too). I'm envisioning a spiral with exponentially-increasing 'diameter' -- any chance it's the golden ratio spiral? How will he deal with the problem of overlap -- the fact that once his spiraling path gets large enough, his labors will begin 'adding' land he had already got on an earlier lap? Will he simply widen his diameter exponentially from the start, so that that he never begins overlapping at all? or will he accept some overlap?

(In case it turns out to be unsolvable if the time period is completely random, we could say that there's a maximum possible time period -- say, he knows he'll be walking for a random duration between 0 and 10 hours, and he knows his speed is exactly 1 mile per hour. Dunno if that helps nail down a solution?)

posted by foursentences to Grab Bag (89 answers total) 34 users marked this as a favorite

Assuming there is no requirement that he wind up with *any* land, could he maximize his expected value by walking one leg of a triangle till the halfway spot (getting him no land if he's cut off early) and then walking the second leg for the rest of the day?

Overlap might lose him more land than being cut off, on average.
posted by musofire at 8:01 AM on August 30, 2011

The figure of maximum area for any given perimeter is a circle. So if the question were, to walk the perimeter of the largest possible shape in a given period of time, ending at your starting point at the end of that time, then the answer would be to walk in a circle, ending at the starting point.

However, your given conditions allow walking straight back to the starting point at the end of the time period. In that case, the largest possible area is to walk in a circular path, ending at the opposite point in the circle at the end of your time period. You then walk straight back to the starting point and end up with exactly a half circle.

All this assumes that the field is so big that you won't run into the boundary.

If you will run into the boundary, the exact solution depends on the shape of the boundary. However the most likely solution there would be to walk to the nearest boundary point (possibly in a straight line or possibly so that the path from the starting point to the point you reach the boundary of the field makes a half circle--that will depend on the exact shape of your field boundary) and then walk along the boundary until time runs out, then walk straight back to the starting point. Which direction to walk and which point on the boundary to walk to will depend quite strongly on the exact shape of the field boundary.

Another possible confounding factor is changes in elevation of the land. If it includes a mountain or valley, say, and increasing the surface area by walking around those features is beneficial, then this could affect the optimal perimeter by quite a lot. (Just for example, walking a circle around an area that includes a tall hill or mountain will include quite a lot more surface area than walking the same circle around a perfectly flat area.)
posted by flug at 8:10 AM on August 30, 2011

At a randomly selected time between the start and when? If the when is now+infinity, then yes I think it might be the golden spiral (though that's based on gut feeling, not rigorous analysis). If the when is now+ 24 hours, then it is going to be a rather different shape.
posted by 256 at 8:14 AM on August 30, 2011

Don't people generally walk in a circle, given no further reference?
posted by Gilbert at 8:23 AM on August 30, 2011

256, yeah, I had in mind that the game would stop at a randomly selected time between the start and infinity (assuming that that problem is solvable).

(Flug, that randomness is the crucial part -- if he knows in advance when his time will be up, then certainly he can calculate the biggest possible semicircular path that he can walk in that predetermined time period, but my question is what he should do if he *doesn't* know.)

To clarify a point that flug raised -- let's say the field is infinitely large, so he doesn't have to worry about running into its extant boundaries. And let's say it's perfectly flat, and homogenously valuable. The "farmland" stuff is just a metaphor to make a math problem more tangible.
posted by foursentences at 8:31 AM on August 30, 2011

Haven't worked this out yet, it's very tricky. However, if the stop time is genuinely a random time t = T in the future, then obviously he can't start by walking in a straight line (since any curving path would gain more land if T is very small).

I suggest using polar coordinates. The problem definition is (I think):

Maximize integral{[R(theta)]^2} - This is proportional to the area he circumscribes.
Constraints: L = v*T = integral{sqrt[(R(theta))^2 + (R'(theta))^2]} - This is the length of the curve he walks.

v is his walking velocity, basically just a constant. For simplicity we can say v=1.
T is also a constant - this is the random variable.

You want to find a function R(theta) such that when you fix T to be any value, the value of theta that solves L(theta) = v*T also maximizes the area.

This is extremely tricky business. I think you're much more likely to be able to use this formulation to find counter-examples. I.E. it might be easy to find a function that beats the golden spiral, but difficult to prove that that function is optimal.
posted by RobotNinja at 8:39 AM on August 30, 2011 [2 favorites]

If you've got some unknown upper limit on the time you expect to be stopped by then it's not immediately clear to me what your strategy might be. However, if you set it to the ten hour limit it certainly can't be some kind of growing spiral. At the last moment before the ten hours is up you should be taking a tangential path - following a circle of your current radius, so the path as a whole can't be a logarithmic spiral, although it might approximate it earlier on (if there's some continuous solution to the problem).
posted by edd at 8:44 AM on August 30, 2011 [1 favorite]

RobotNinja - I think you have to be careful how you count things if you go round more than 360 degrees and start 'covering' area you've already looped.
posted by edd at 8:46 AM on August 30, 2011

Clearly, the direction of his first step is irrelevant--that is, any direction is as good as any other. Once he's any distance from the starting point, the optimal (from the stand point of what will happen if he's stopped "immediately") thing to do is to trace a circle at that distance. But in the long run (if there is one) that strategy sucks. It's like saying, if the market can crash at any moment, how do you invest? Well, you decide on what level of loss is acceptable. So in this case, the level of acceptable loss will determine your spiral at any moment. If that level is a percent of what is already traced (or an arbitrary function of what is already traced) it will generate a particular curve. With no risk allowed, no reward is allowed.
posted by Obscure Reference at 8:46 AM on August 30, 2011

In other words, to maximize your instantaneous rate of increase (i.e. infinite slope) will give you a return of zero.
posted by Obscure Reference at 8:52 AM on August 30, 2011

I had in mind that the game would stop at a randomly selected time between the start and infinity

You're probably going to have to be more specific than that to get a well-defined answer. The problem of selecting a random variable over an infinite range of possible values is notoriously ill-defined; in particular, there's no mathematically well-defined way to choose a number between 0 and ∞ such that all values are "equally probable".
posted by Johnny Assay at 8:52 AM on August 30, 2011 [4 favorites]

Yes, I totally missed the 'randomly selected time that person won't know until it's called' condition.

However, the half-circle example still leads us in the right direction.

At no moment will it be optimal to walk directly away from the starting point (because if time is called then you just waste those outward steps, retracing them exactly).

At no moment will it be optimal to to walk towards the starting point or even in a direction tangent to it (ie, along the perimeter of a circle with center the starting point).

So basically you are going to be walking a circle with radius ever-increasing as time goes along. So yes, some kind of spiral.

However, don't think that you're going to be spiralling around and around the starting point. It will be more like 1/2 (or 1/4 or 2/3 or whatever, depending on exactly when time is called) of a spiral.

Working out the exact spiral shape really is a calculus problem (and one that depends on the exact parameters of the random process that will end the walk) and unfortunately I don't have time to work on that this morning.
posted by flug at 8:53 AM on August 30, 2011 [1 favorite]

I also think there are problems with the question as formulated, but I think there's a very similar question that can be answered. Instead of limiting it to a random time, I think what you're going for is an algorithm that maximizes the area at all points in time. Or, put differently, what shape or curve (when closed by a straight line back to origin) maximizes the ratio of area/circumference.

As mentioned above, the theoretical absolute upper limit is the triangle. Doing this actually requires knowledge unavailable to the man, but he can't do better.

It seems clear that walking in a straight line is not the answer. So the best answer must be a spiral... and that's where my math skills aren't up to the task. However, that does mean that you can reformulate the question as:
"what equation describes the spiral that, when a line is drawn from any point on the spiral to the center, encloses the greatest amount of area".

It seems likely to me that this is the golden ratio, but I can't prove it.
posted by contrarian at 9:27 AM on August 30, 2011

The answer is a spiral. Because the stop time is unknown, you can't have a change in strategy part-way through as an ideal agent. I think we have to assume that his linear speed is constant, which means his angular speed is decreasing. (It would be a neat trick to make his angular speed constant.) The optimization factor is how quickly he walks outwards, radially from his starting point. A golden spiral has an "accelerating" outward direction, which means that the time it takes him to complete a revolution increases much faster than a normal spiral. My calc skills are too rusty to work out whether that's a better strategy than a spiral where each path is a set distance further from the origin.
posted by supercres at 9:31 AM on August 30, 2011

This seems to me to be a lot simpler than you're making it out to be.

To a very half-assed first approximation, if you want to maximize the expected area taken, take the walk that maximizes the area taken at the expected deadline.

Half-assed because the expected area of the deadline, for some fixed walk, may not equal the area of the expected deadline.
posted by ROU_Xenophobe at 9:52 AM on August 30, 2011

Thanks for all answers, and by all means keep them coming. I'm 95% sure the correct path must be SOME kind of spiral; the question is 1) which spiral, and 2) whether the spiral winds up (a) overlapping itself or (b) approaching, as a limit, that ray where overlap would begin, but never quite reaching it. (If in fact the optimal answer is not a spiral, that would be fascinating, but I'm struggling to see it without importing some kind of strange utility function.)

ROU, there's no expected deadline if the deadline could be anytime between 0 and ∞, right? Or rather, the expected deadline is ∞, so the man should just walk in a straight line? Struggling to conceptualize that.

Supercres, the assertion that the golden ratio's outward direction ~accelerates is a good way to express it, and I think that's the source of its intuitive appeal as a solution here -- encompass more and more area with each marginal step, while still shying increasingly away from unnecessary overlap.

Robotninja, thanks for a much more rigorous formulation of the problem than I could have come up with. Does that formulation take into account the area lost due to overlap?
posted by foursentences at 10:10 AM on August 30, 2011

Since you don't know what time you're going to have to stop walking, the solution must be identical for all times T, which means that it's self-similar. In other words, the paths you would see at T1 and T2 are identical except for scale. They would look the same viewed from different heights.

Think about it this way: each step must maximize the additional area added by taking the step.
posted by unSane at 10:12 AM on August 30, 2011 [1 favorite]

(the answer is not a true spiral, since you never want to have travelled more than 360° around your starting point, no matter how far you walk)
posted by unSane at 10:13 AM on August 30, 2011 [1 favorite]

"A randomly selected time between the start and infinity" - assuming you mean a uniform random distribution - not only makes the problem insoluble, the very concept is meaningless. There is no uniform random distribution covering an infinite number of possibilities, as any attempt to analyze such a distribution leads to contradictions.

Consider: if such a distribution did exist,
- The probability that he would be stopped in less than 1 minute would be zero, and the probability that he would be stopped at some time after 1 minute would be one.
- The probability that he would be stopped in less than 1 year would be zero, and the probability that he would be stopped at some time after 1 year would be one.
- The probability that he would be stopped in less than 5,948,136,000,000,000,000,000 millennia would be zero, and the the probability that he would be stopped at some time after 5,948,136,000,000,000,000,000 millennia would be one.

(Note, however, that some non-uniform probability distributions over an infinite range are possible, such as an exponentially decreasing distribution.)

So for the problem to even be meaningful, we have to either specify a non-uniform probability distribution, or a uniform distribution within a finite time.
posted by DevilsAdvocate at 10:16 AM on August 30, 2011 [4 favorites]

Think about it this way: each step must maximize the additional area added by taking the step.

I don't believe this is correct. This would lead him to simply walk perpendicularly to the line connecting his current position to the origin, once he was a non-zero distance from the origin, which would result in him walking in a very small circle around the origin, which is clearly incorrect.

Rather, each step must maximize the area added by taking the step plus the expected area-based on the probability distribution of remaining time-gained by future steps. If one considers only the area added by the current step, walking away from the origin is pointless. If one considers that many more steps might yet be taken, it likely becomes beneficial to walk at some angle away from the origin, rather than perpendicular to it. If he knows his step is certain to be his last step - if, say, the probability distribution is known to be uniform to a maximum time of 10 hours, and it's now 9:59:59 since he started, that step should maximize the area added.

Since you don't know what time you're going to have to stop walking, the solution must be identical for all times T

Not for a uniform distribution with a finite upper time, since the strategy will vary depending on how close you are to the maximum time.
posted by DevilsAdvocate at 10:30 AM on August 30, 2011 [1 favorite]

unSane, whether you're right or not about the 360 degree limitation depends on the mechanics of the question. Your interpretation is right if you lose any ground that you "slice" off on your way back at the end of the time period, but, if instead you get to keep all the ground within ANY line of blue paint, you can still be optimal circling beyond 360 degrees any number of times.
posted by Aizkolari at 10:44 AM on August 30, 2011

The probability distribution is key idea that lets you maximize the expected value (which is the answer to your problem). However, if there is a non-zero chance of being stopped at an arbitrarily small time after the walk begins, then regardless of the initial direction, the farmer needs to find a curve that moves away, as quickly as possible, from the straight line created by his initial direction (because walking in a straight line will give you zero area, and the clock could stop at any time). But there is no trajectory that deviates "the most quickly" from the straight line (i.e. the rate of change is unbounded). This makes me think the problem has no solution, but there might be something about the explicit calculation of expectation value that takes care of these infinities, or a particular probability distribution that somehow normalizes the result.

In other words, to maximize your instantaneous rate of increase (i.e. infinite slope) will give you a return of zero.

On preview, that is exactly what I was trying to say.

It's like saying, if the market can crash at any moment, how do you invest?

That is also a great analogy. I think Obscure Reference has it.
posted by grog at 10:47 AM on August 30, 2011

There is no uniform random distribution covering an infinite number of possibilities, as any attempt to analyze such a distribution leads to contradictions.

This is not necessarily true. If you're playing Blackjack for an unknown possibly infinite amount of time trying to have the highest expected value at the end, the perfect Blackjack strategy still applies whether you're playing for 5 minutes or 500 quadrillion years. I'm not saying that there is such a perfect solution independent of time in this case, but making the time uniformly random across an infinite amount of time does not inherently make the question meaningless.
posted by burnmp3s at 10:51 AM on August 30, 2011

The answer has to be a spiral. Even if you travel more than 360 degrees, that's still the most ideal path for ALL times. If you don't know when you're going to stop, you can't trace a shape that doesn't overlap itself without going in a straight line.

It's silly to get caught up with how the question was phrased. The problem is to pick a function that maximizes the area for all times. Call the maximum time unknown. If you know the maximum time, isn't it trivial to optimize in that range?

The simplest path to evaluate the Archimedean spiral r = theta (so, radius increasing constantly with respect to angle; looks like this for 5 revolutions). Over increasing values of theta, we'll need to find the integral and the arc length. (Arc length will be the stand-in for time, because we assume constant linear speed.)

The arc length, s, of the curve r=theta from zero to theta1, is given by:

s = int[0 theta1](sqrt(r^2 + (dr/dtheta)^2)*dtheta)
s = int[0 theta1](sqrt(theta^2 + 1)*dtheta) (derivative WRT theta is 1)

s = 1/2 (theta1*sqrt(theta1^2+1)+asinh(theta1))

(please forgive the abuse of notation)

The area inscribed is the integral in polar coordinates:

A = 1/2 * int[0 theta1](r(theta)^2*dtheta)
A = 1/2 * int[0 theta1](theta^2*dtheta)
A = 1/6 * theta1^3

So now we just plot area against arc length (time). I did it in Matlab, so:

>> theta1 = 0:.01:10*pi;
>> s = .5*(theta1.*sqrt(theta1.^2+1)+asinh(theta1));
>> A = 1/6 .* theta1.^3;

Which gives a plot like this.

I think your ideal solution will have a linearly increasing area WRT to time, given the unknown duration. This isn't it. Trying a golden spiral, or squaring/cubing/etc the theta term in the equation, will be more complicated. No time to do the math now.
posted by supercres at 10:52 AM on August 30, 2011 [2 favorites]

I don't know how I missed RobotNinja's answer that was basically my idea said concisely.

Though I do think the key part is that A will increase linearly WRT path length in the ideal situation. When I get a chance, I'll see if the golden spiral (or any log spiral) does that.
posted by supercres at 11:03 AM on August 30, 2011

As others have noted, a growing spiral feels right (too busy to do the math to prove it).
However, to skirt around the infinity thing, here are some other ways of thinking about the problem. First, land size is really not that important, what's important is how much land can you cover based on your velocity. To see what I'm getting at, change the problem to be somewhat trivial ... the guy gets the amount of land that is a circle with the distance he's walked as the radius. Clearly the solution to this problem is to keep walking directly away from the starting point. However, the size/shape of the land (assuming the shape is unknown to the walker) doesn't change the solution. In other words, the solution for all land shapes is the same up until a boundary is actually reached (again assuming no prior knowledge of the shape of the land). So, given that we can ignore how big the land is until we actually reach a boundary.
So that raises the question of how to describe the spiral one should walk. This is a function of the probability function of when time will be called. Like others have said, using from now until infinity is really not a good way of describing the problem since the probability of time being called in any fixed time length (whether a second, month, year, or century) is always zero. So to really get to the meat of the problem a fixed time interval would work better. Say from now and 10 years (so he will have ample time to use the land in his lifetime, yet still be a large number). An alternative (but equivalent) approach is to determine a time when the guy will give up.

Regardless, given whatever that time is, and assuming the probability of a time out happening is randomly chosen between when he starts walking and the time ends, the path seems to be a normal spiral with the end point on the perimeter exactly 360 degrees away from where he started, at velocity*(maximum time) away from the center.

However, change the probability distribution, and the path will also change. For example if it's more likely time to be called earlier than later, than the spiral would be tighter for the first 180 degrees, and much broader the final 180 degrees.
posted by forforf at 11:04 AM on August 30, 2011 [1 favorite]

You asked for the greatest expected value. Most of the responses assume that the question is, "what is the path such that, if I am stopped at any time, I have maximized area."

However expected value is the average of all values. So theoretically if you have one path that gives you areas of 1, 2 and 3, and another that gives you values of 0, 0 and 7, then the second one has the greater expected value.

OP should clarify whether he wants the greatest expected value, or a strategy for maximizing area at each possible cutoff point.
posted by musofire at 11:05 AM on August 30, 2011 [3 favorites]

Musofire: I was assuming that this is a once-in-a-lifetime opportunity, so that the risk/reward strategy would minimize the odd (or frequent) low values. The expected value of a die roll is 3.5, but you have to be able to roll more than once :)
posted by supercres at 11:17 AM on August 30, 2011

The probability distribution of ending time T is uniform. Therefore the solution must be optimal for all values of T. Therefore it must be self-similar.

OP should clarify whether he wants the greatest expected value, or a strategy for maximizing area at each possible cutoff point.

These are the same solution, I'm sure.

The reason I'm against a spiral is that if you complete more than 360°, each extra degree fails to add the amount of area that was added on the revolution before. Whereas if you asymptotically approach 360 degrees, you keep adding bigger and bigger slices. (Although it's not clear at all how the series of areas added would converge - maybe it would all come out in the wash and you just keep adding the same amount on each step regardless?)
posted by unSane at 11:17 AM on August 30, 2011

The expected value of the circumscribed area is infinite, unless we stipulate an upper bound for the time the man is allowed.
posted by unSane at 11:24 AM on August 30, 2011

unSane, I like the idea of asymptotically approaching 360 degrees. I think that would be a logarithmic spiral with a growth factor set so that radius approaches infinity as theta approaches 2*pi. The path would become a straight line parallel to the initial instantaneous direction.
posted by supercres at 11:38 AM on August 30, 2011

The area included by inscribing laterally along one unit of circumference (which takes one unit of time) is rπ/2. If you've already covered that circumference before, you gotta subtract out the area you already covered, which gets gnarly math-wise. Still, the farther from the centre you are, the more area you include per unit time.

So, you got to walk in a spiral that optimizes increasing distance from the centre with increasing angular inclusion. I'm not smart enough to figure out exactly which ratio is best but it is probably the golden spiral because that would be elegant, and pretty.
posted by seanmpuckett at 11:43 AM on August 30, 2011

It seems to me that the fundamental issue is the probability distribution of the time-out. If the distribution function is flat (i.e., the time-out occurring at 3 seconds is just as likely as one occurring at 10 billion years), then the optimal solution is to walk straight out from the center. Of course, this doesn't make intuitive sense, since this means he'd never get any land. But that's because the probability of the ever being a time-out is zero. In other words, it's makes this problem identical to one where there is no time limit at all.

So in order for the problem to make any sense at all, something has to change. The most obvious way is to fix the time limit to some specific value, which makes the problem fairly straight-forward. Another way would be to change the probability distribution function so that as time approaches infinity, the probability of a time out occurring is also zero. For example, the probability of a time out occurring is equal to 0 t < 1minute and 0.5*(time/time^2) for t > 1 s. So there is a 50% chance of a time out occurring after 1 minute, 25% at two minutes, etc.

The point is that unless the probability of the time-out occurring at infinity is zero, the problem becomes one where time is unlimited.
posted by forforf at 11:50 AM on August 30, 2011 [1 favorite]

unit error, that should have been ... probability = 0 at t < 1 minute and 0.5(time/time^2) for t > 1 *minute*.
posted by forforf at 11:52 AM on August 30, 2011

I agree there needs to be an upper bound on the time or the problem is meaningless.
posted by unSane at 11:53 AM on August 30, 2011 [1 favorite]

Solving the problem for a single time T (or equivalently number of steps N) would be a start.
posted by unSane at 11:53 AM on August 30, 2011

There doesn't *have* to be an upper bound on time, only that the probability decreases to 0 as time approaches infinity.
posted by forforf at 12:02 PM on August 30, 2011

Better minds than mine have already tackled the math, but the problem reminds me of The Walking Purchase:
William Penn's heirs, John Penn and Thomas Penn, claimed a deed from the 1680s by which the Lenape promised to sell a tract beginning at the junction of the Delaware River and Lehigh River (near modern Wrightstown) and extending as far west as a man could walk in a day and a half.... According to the popular account, Lenape leaders assumed that about 40 miles (60 km) was the longest distance that could be covered under these conditions. Provincial Secretary James Logan, the legend continues, hired the three fastest runners in the colony, Edward Marshall, Solomon Jennings and James Yeates, to run on a prepared trail. This occurred on September 19, 1737; only Marshall finished, reaching the modern vicinity of present-day Jim Thorpe, Pennsylvania, 70 miles (113 km) away.
posted by AsYouKnow Bob at 12:04 PM on August 30, 2011 [1 favorite]

The solution for a single fixed time T (assuming even probability for any t in T) is a one revolution spiral. To visualize it in Cartesian coordinates, rather than starting at a point in a plane, have the guy start in the corner of an infinitely large square, and the amount of land he gets is the right triangle described by the start point, the ending point when time-out is called, and the the straight line to the closest side.

If T is infinite the solution for the Cartesian coordinates is obvious, what obfuscates the polar solution is that you want to end up 360 degrees from where you started. However, if you visualize a single revolution spiral for circles of increasing radius, you can imagine the spiral getting more and more stretched out, until at infinity, it's a straight line.

Again, this is only for the case where the probability is evenly distributed across the entire time interval.
posted by forforf at 12:08 PM on August 30, 2011

What about a solution something like this:

At time Tn, call the position P of our guy in polar coords be (r, theta).

The next step Sn he takes will be a vector (r', theta') which has a scalar step size S.

We want the direction of the new vector to vary asymptotically from being at right angles (π/2) to the current position vector at t=0, to being along the position vector (π) at time infinity, or equivalently when theta = 2π.

So the angle between the vector Sn and the position vector should look something like

(π/2 + π(1-theta/2π)
posted by unSane at 12:45 PM on August 30, 2011

I think the best we can hope for is a slope of the area vs path-length plot that becomes linear as path-length approaches infinity; that's what it did in my example. It will never have an increasing derivative. (At least, not with respect to time. It might to angle, but angular speed necessarily decreases as radius increases.) I think by changing parameters (power of theta? logarithmic spiral?) the final asymptotic slope could be increased, but it will always approach linear.

unSane, are you sure that the slope of your area vs path-length plot wouldn't decrease in that case? I don't quite follow your most recent post, but it would with a path that approaches linear, which I think falls out of a path where the angle approaches 2pi.
posted by supercres at 1:02 PM on August 30, 2011

Assuming a uniform distribution over a fixed time range, you can visualize this as a three dimensional problem, where the third dimension represents the probability that time will not have been called, and goes from 1 to 0 as T goes from T0 to Tend. So area gained at the beginning of the path counts for more than area gained at the end, as it is more likely that the farmer will actually gain it.
posted by novalis_dt at 1:03 PM on August 30, 2011

musofire and forforf have it. The problem is unanswerable without a fixed upper time limit. Or, rather, the answer is forforf's unintuitive sol'n.

musofire: "You asked for the greatest expected value. Most of the responses assume that the question is, 'what is the path such that, if I am stopped at any time, I have maximized area.'"

These are very different questions. The expected value of something is the sum of all possible outcomes times their probability. Hence, you could be willing to trade-off some possible land at the beginning (for a length of time that it's improbable that the game will end) if it means greater gains later on (when the game is more likely to end).

forforf: the optimal solution is to walk straight out from the center.

Yes, if there's no upper time limit, this is the answer. Think about it: by beginning your spiral early, you decrease the size of the circle you could later circumscribe. If you know the game could go on for a trillion years, the chance that it ends in the first thousand years is relatively minute, so you shouldn't base your actions on the small chance that it ends so soon. Instead, you maximize your later gains by walking straight away from the center, to make the circle as big as possible. Later on, you can start veering away in a spiral.

Of course, if the end time is truly infinite, then "later on" never comes and you just walk straight away from the center. If the game could last 10^20 years, what are the odds it'll end after a trillion? How foolish you'd be walking around in circles for a trillion years when you could have been trekking off straight away from the center. Think how big *that* circle would be.
posted by losvedir at 1:14 PM on August 30, 2011

If you're playing Blackjack for an unknown possibly infinite amount of time trying to have the highest expected value at the end, the perfect Blackjack strategy still applies whether you're playing for 5 minutes or 500 quadrillion years.

I don't agree.

Suppose the optimal strategy, A, nets you \$5/hand, on average. Let's also say that there's a suboptimal strategy, B, which is still profitable but nets only \$2/hand.

The expected value of playing strategy A, when you are stopped after playing a number of hands according to this alleged uniform infinite probability distribution, is infinite. The expected value of strategy B, when you are stopped after playing a number of hands according to this distribution is also infinite.

A is a better strategy than B only when the expected number of hands is finite. (And, as noted before, it's possible to have a finite expected number of hands even if the maximum possible is infinite for some non-uniform probability distributions, but not for a uniform one.) When the expected number of hands is infinite, strategies A and B are equally good.

"Whether you're playing for 5 minutes or 500 quadrillion years" only further illustrates the conceptual error you are making, because 500 quadrillion years is no closer to infinity than 5 minutes is. If one was stopped according to this alleged uniform infinite probability distribution, the probability of being stopped within the first 500 quadrillion years would be zero. Not "a very very very small number very close to zero," but ZERO.

If you don't trust me, see this entry from Ask A Mathematician. In particular:
Fine, but can we define a probability distribution on the set of integers (rather than the real numbers between 0 and 1) such that they each occur with equal probability (i.e. does a uniform distribution on the integers exist)? The answer, sadly, is no.... Attempting to define a uniform distribution on the full set of real numbers also fails, for a very similar reason that it doesn’t work on the integers (it can not be the case that each real number (or equally sized interval of real numbers) has the same probability and the probability density function integrates to 1).
posted by DevilsAdvocate at 1:15 PM on August 30, 2011 [1 favorite]

Clearly there's a trade off between moving radially, which maximizes distance from the origin and therefore makes it easier to gain area later, and moving tangentially, which gains area now at the cost of doing so later. There's really only one degree of freedom at any time T, which is the angle at which you should take the step relative to the current radius.

Since the most area gains are made at the greatest distance from the origin, for a particular number of steps N it makes sense that early steps should be more radial, changing to a more tangential direction as you approach N steps.

For N=1, it's trivial - you have to step away from the origin, and the area is 0.

For N>1, I strongly suspect that you want to describe a circular arc of 2π, with the final walk home completing a semi circle.
posted by unSane at 1:16 PM on August 30, 2011

I mean an arc of π, sorry.
posted by unSane at 1:16 PM on August 30, 2011

Whereas if you asymptotically approach 360 degrees, you keep adding bigger and bigger slices.

You keep adding slices with larger and larger radii, but you're adding narrower and narrower slices, and it's not clear to me that the area you gain is greater than what you would by going past 360 degrees. While it's true that going past 360 degrees seems inefficient because you don't get to "double-count" the area you already covered the first time around, it may be the case that even taking that into account, it may still give you a greater increase in area than a very narrow slice which slightly increases the radius beyond what you already had.
posted by DevilsAdvocate at 1:28 PM on August 30, 2011

The expected value of playing strategy A, when you are stopped after playing a number of hands according to this alleged uniform infinite probability distribution, is infinite. The expected value of strategy B, when you are stopped after playing a number of hands according to this distribution is also infinite.

To me this is semantics and doesn't really affect the actual question. You can prove via induction that A always results in a higher expected value at any given time than B, so that the inequality holds true for the infinitely many finite values time could have, even if the expect values at time infinity are meaningless. So the question may be worded incorrectly and should be phrased as maximizing the value for any arbitrary finite time t, but my point was that you don't need to set an actual time limit for this question or use a non-uniform distribution of possible times in order to solve it any more than you need to set a time limit for playing Blackjack when you talk about optimal strategies.
posted by burnmp3s at 1:38 PM on August 30, 2011

For N=1, it's trivial - you have to step away from the origin, and the area is 0.

For discrete steps, N=2 is also trivial: you have to step away from the origin on the first step; if you're not stopped then, you maximize the area by turning 90° for the second step. The area is 0 if you are stopped after 1 step, and 1/2 if stopped after the second step, so the expected value is 1/4.

In fact, if you know the maximum number of possible steps, your last step, should you reach that maximum number, should necessarily be perpendicular to the line between your current position and the origin. (This suggests to me that in the continuous case, if you know a maximum finite time, you should be moving perpendicular to the origin at that maximum time.)

The smallest non-trivial case is N=3. The first step must be away from the origin, and the third step, if you get to take it, must be perpendicular to the line connecting the end of your second step to the origin. The only uncertain part is the optimal angle between the first and second step - call this θ. Clearly, θ should be at least 90°. (If it's less than 90° you're moving back towards the origin, which is counterproductive.)

Now, if you're stopped after the first step, the area is 0.

If stopped after the second step, the area is 1/2 sinθ

If allowed to take all three steps, the total area is [1/2 sinθ + 1/2 sqrt(2-2cosθ)].

(note cosθ will be negative.)

So the expected area covered is [1/3 sinθ + 1/6 sqrt(2-2cosθ)]

Turns out this value is maximized at approximately θ=107.25°, with an expected value of 0.58672

For the continuous case with a finite maximum time T, I expect the solution is to start moving away from the origin at 180° and gradually decrease the angle between your position relative to the origin, and your motion, until it reaches 90° at T.
posted by DevilsAdvocate at 2:00 PM on August 30, 2011

I agree there needs to be an upper bound on the time or the problem is meaningless.

I disagree. Let's assume that we solve the problem for an upper bound of t. Then we can ask what the solution looks like in the limit as t approaches infinity. It's possible that you get a singularity or some other oddity that makes a solution impossible, but it's not clear to me that you must.
posted by It's Never Lurgi at 2:08 PM on August 30, 2011

DevilsAdvocate is pointing out that there is a qualitative difference between 500 quadrillion years and infinity, not just a quantitative one. Any fraction of infinity is also infinite, and the likelihood of any instant being the randomly selected time is zero (i.e., 1/infinity). The problem is that it destroys the question -- it wouldn't make any difference what direction you walked because the random time bell would never be rung.

But I think that is the right answer. I am not a probability expert by any means, but I think it is the kind of question that does not have an answer once you bring infinity into it. Another example of this kind of question -- Lets say you are given a dollar and paid 2/1 on a series of coin flips (1st win nets 3 (1+2) 2nd nets 9 (3+6), etc.). You must bet everything you have on each consecutive flip, but can quit anytime. What is the optimal strategy? On a finite number of flips, the optimal strategy is to flip at every opportunity because the payout -- 2/1 -- is better than the odds of losing -- 1/1. However, if there is an infinite number of possible flips this falls apart because if you bet an infinite number of times the probability that you will lose at least once is certain.
posted by rtimmel at 2:14 PM on August 30, 2011

Another way of visualizing this, in the 0-360° case anyway, is to think of the path as a curve of the form

r = f (theta)

in which case the area is proportional to the integral of f(theta)^2

f is constrained as follows:

f(0) = 0
the length of the curve = N (taking one step as the unit)

So we can think of trying to enclose the maximum area with a curve of length N, which has one end tethered to the origin.

It is pretty clear to me that this means the the solution in the case of a particular N is to get as close to a semi circle as possible. This satisfies the conditions outline above that the man begins walking radially and ends walking tangentially.
posted by unSane at 2:46 PM on August 30, 2011

If so, then the maximum area for N steps of unit length is

A(N) = 1/2 π r^2 (half the area of a circle radius r)

The circumference is 2N (since N steps takes us halfway round), so the diameter is 2N/π which makes the radius N/π

slotting this in then:

A(N) = 1/2 π (N/π)^2 = 1/2π N^2
posted by unSane at 2:54 PM on August 30, 2011

Let's assume that we solve the problem for an upper bound of t. Then we can ask what the solution looks like in the limit as t approaches infinity. It's possible that you get a singularity or some other oddity that makes a solution impossible, but it's not clear to me that you must.

This is a fair point. I strongly suspect, however, the limit of the finite problem as the maximum time T goes to infinity will be a straight line away from the origin. I suspect that the solution for a finite T will be a curve that starts moving away from the origin and gradually increases the angle until at T it is moving perpendicular to the origin. But this would mean that as T approaches infinity, the motion in any finite time would remain directly away from the origin.

(On preview: if unSane's semicircle solution turns out to be correct - in fact the semicircle is known to be the correct answer if you drop the probabilistic time and just give a fixed, known time in which to walk - then the solution as T approaches infinity is an infinitely large semicircle, i.e., within any finite time one is still walking directly away from the origin.)
posted by DevilsAdvocate at 2:54 PM on August 30, 2011

Considering the continuous case with maximum time T:

unSane is right that there's only one parameter to be chosen at each time, the angle between your position vector (from the origin) and your motion vector; call this θ. (Note I've redefined this from my prior comment analyzing the discrete case for N=3; now, θ=0°, rather than 180°, represents motion directly away from the origin, which will simplify the math somewhat.)

Assuming a velocity of 1 space unit per time unit, your distance from the origin at time x will be:

r=∫0x cosθ dt.

The total area covered, at time y (if you haven't been stopped before then) is:

A=∫0y 1/2 r sinθ dt. (Remebering that r itself is a function of t.)

The probability that you will actually "get" to a certain time drops linearly from 1 at t=0 to 0 at t=T, so add in that factor to calculate the expected area covered:

E=∫0T ((T-t)/T) 1/2 r sinθ dt

Find the function θ=f(t) that maximizes E.
posted by DevilsAdvocate at 2:59 PM on August 30, 2011

Well, here's a totally seat of the pants way of looking at f(t).

Let's say the maximum number of steps is Nmax and the actual number of steps we get is N

Let's also say that we have already taken M steps.

What if at every step we simply tried to steer ourselves in the right direction to maximize the area for the expected number of steps remaining, given that we have already gone M steps?

We already know how to do this, sort of. We can't do anything about the steps we've already taken, but we can take the step that would be required to create a semicircle of the appropriate size as described above.

At step M, we expect to go a further (Nmax-M)/2 steps. So at step M we take the step that would be required to create a semicircle of semicircumference M+(Nmax-M)/2 = (Nmax+M)/2.
posted by unSane at 3:37 PM on August 30, 2011

So thinking this through a bit more, for a concrete example. Suppose we are allowed a maximum of 1000 steps, but the actual number is chosen randomly between 1 and 1000. So the expected number of steps is 500.

Accordingly, we take our first step as if making a semicircle of semicircumference 500, the expected length of our path.

Then we slowly increase the circumference of the semicircle we are making as we take step after step, until we finally, on the 1000th step, are walking as if we were making a semicircle of semicircumference 1000.

This family of solutions is fairly self similar, just getting smoother as the maximum number of steps increases.
posted by unSane at 3:46 PM on August 30, 2011

Another way of thinking about it is that at step M you walk along a curve of radius (Nmax+M)/2π.
posted by unSane at 3:50 PM on August 30, 2011

I like that--it jibes with my intuition that the angle between position and motion should approach 90° faster than it does in the case of a fixed, known-in-advance number of steps. It would look something like half of an egg with the narrow end at the origin.
posted by DevilsAdvocate at 4:03 PM on August 30, 2011

I'm afraid to say I'm finding unSane unconvincing.
posted by edd at 4:09 PM on August 30, 2011

Again let's take the case where we know we are going to take N steps and want to maximize the area.

We are going to make a semicircle, divided into N triangular segments, each subtending an angle of π/N.

Each step Si will be the vector

(sin(iπ/N), cos(iπ/N)), for i in 0...N

Now consider the case where we are trying to make the expected semicircle at each step, as described above, with a maximum Nmax steps.

At step Si the expected total number of steps is (Nmax+i)/2.

So each step Si will be the vector.

It should not be too hard to work out the area now.

( sin( 2iπ/(Nmax+i) ), cos( 2iπ/(Nmax+i) )

Sanity check -- our zeroth step is (1,0). Our Nmaxth step is (0,-1)
posted by unSane at 4:09 PM on August 30, 2011

sorry screwed that up - the sentence about the area should come last!
posted by unSane at 4:12 PM on August 30, 2011

Like I say that is just seat of the pants but it makes sense to me that if the solution for a known N is a semicircle, then the solution for an unknown but finite N should be something that looks vaguely similar but changes step to step as more information about the total number of steps becomes available.

What don't you like about it, edd?
posted by unSane at 4:23 PM on August 30, 2011

I did a spreadsheet to do the case where Nmax=100. This is what the curve looks like.
posted by unSane at 4:39 PM on August 30, 2011

Looking at that you can see it's not right, as the last step is not at right angles to the radius vector. Hm.
posted by unSane at 4:45 PM on August 30, 2011

With Nmax=400 it's even clearer that it's wrong. I think the approach is right though.
posted by unSane at 4:47 PM on August 30, 2011

"(the answer is not a true spiral, since you never want to have travelled more than 360° around your starting point, no matter how far you walk)"
is the earliest thing that makes me feel uncertain.
posted by edd at 4:51 PM on August 30, 2011

I think you've got the right general idea...try defining the angle between the step and the radius vector directly, rather than the direction of the step. I.e., let the step be Πi/(Nmax+i) to the radius vector.
posted by DevilsAdvocate at 4:51 PM on August 30, 2011

I don't want to butt in too much because I don't have a good idea of a real solution, but I too have a vague feeling that this thing can't be asymptotic - if it is, it can't be self-similar, right?
posted by ftm at 4:53 PM on August 30, 2011

More work on the continuous case with finite maximum time. I'm going to arbitrarily set the maximum time T=1; a larger or smaller value would just give the same solution, scaled larger or smaller. (Doubling the length of time would result in the same shape but twice the length, giving four times the area.)

If θ as a function of time is represented by θ(t), then the expected value is given by:

E = ∫010x (1/2)(1-t)(sin θ(x))(cos θ(y)) dy dx

For the semicircle, θ=(2/Π)*t

The expected value for the semicircle is (Π2-4)/4Π30.0473259

unSane's "curvature based on expected steps" (with suggested modification by me) is, in the continuous case, θ=(2/Π)*(2t/t+1). The expected value is ~0.05044, better than the semicircle.
posted by DevilsAdvocate at 4:55 PM on August 30, 2011

θ=(2/Π)*t
θ=(2/Π)*(2t/t+1)

Correction: in both of these, (2/Π) should be (Π/2). I did it right for the calculations in Wolfram Alpha, just wrong here.
posted by DevilsAdvocate at 4:58 PM on August 30, 2011

I tried solutions of the form θ=(Π/2)*tn. The best I was able to come up was at n=0.647, with an expected value of ~0.0503847, just a hair below unSane's curvature approach.
posted by DevilsAdvocate at 5:10 PM on August 30, 2011

θ=(Π/2)*(2t/t+1)

I tried generalizing this as θ=(Π/2)*(nt/t+n-1), but it appears n=2 gives the maximal result (at least varying n by as little as 0.01) among solutions of that form, which suggests to me that unSane's reasoning is correct.
posted by DevilsAdvocate at 5:24 PM on August 30, 2011

Here's a graph (1000 steps, step length=0.001 so it should be pretty close to the continuous case). Interesting that it goes past 90° to about 132°.

Note that if you increased the maximum length/number of steps, the solution would grow bigger as a whole but keep the same overall shape; that is, it wouldn't wind around farther, it would just be bigger, still ending after covering about 132°.
posted by DevilsAdvocate at 6:11 PM on August 30, 2011 [2 favorites]

Tried some variations of the form θ=(Π/2)*(2t/t+1)n, but n=1 seems optimal.
posted by DevilsAdvocate at 6:15 PM on August 30, 2011

132° is 2π/e near as dammit. That's awesome.
posted by unSane at 7:11 PM on August 30, 2011

Also, this suggests that the infinite case is simply an infinitely big version of this curve, which looks like a straight line away from the origin to any finite person.
posted by unSane at 7:21 PM on August 30, 2011 [1 favorite]

I think if this isn't the solution it's very close.

To be clear if you haven't been playing along, the curve DevilsAdvocate posted shows the path you should take. The scale depends on

a) the length of your stride
b) the maximum time allowed

The length of the curve is (a) times (b). So if you know the maximum time is 24 hrs and you walk at 4 mph, you know that curve is 96 miles long and set the scale accordingly.

Basically you follow this path at the scale given by (a) and (b) until your time is up. You only reach the end of it if you get the maximum time. If you know in advance how long you have, a semicircle is you best bet, but if you're going to be stopped randomly at some time between the start and the maximum time, you walk along this curve.
posted by unSane at 8:26 PM on August 30, 2011 [1 favorite]

errata: (a) should be your ground speed, but you get the idea
posted by unSane at 8:28 PM on August 30, 2011

Further confirmation. Ran the numbers for an Archimedean spiral with polar equation r=aθ, with θ going from 0 to θmax, and a chosen to make the arc length equal to 1. The best I found in that method was θmax≈139.5°, a≈0.249, and an expected area of ~0.04973.
posted by DevilsAdvocate at 9:24 PM on August 30, 2011

unSane: To be clear, then, if that curve is the proper one for a known "maximum time allowed", what if the maximum time allowed is infinite? My intuition, which I think is backed up by your work, is that since the scale of that spiral is based on the maximum time allowed, if that's infinite, then the spiral is infinitely big and you only get to the first part of it, i.e., radially outward. Correct?
posted by losvedir at 5:24 AM on August 31, 2011

losvedir, that's what it looks like.

This curve is interesting because it satisfies all the conditions we stipulated, but it doesn't look like the spiral folk were intuiting at the beginning. It's a sort of cross between a semicircle and a spiral. I wonder if it has a name?
posted by unSane at 6:26 AM on August 31, 2011

It's particularly cool (if true) that for a line of unit length, the optimal angle is 2π/e.
posted by unSane at 6:28 AM on August 31, 2011

Intuitively it seems that r = sqrt(theta) would be good... I don't have the time to calculate it, but how does that one work out?
posted by Earl the Polliwog at 8:26 AM on August 31, 2011

Or even sqrt(theta_max^2 - theta^2).
posted by Earl the Polliwog at 8:28 AM on August 31, 2011

It's particularly cool (if true) that for a line of unit length, the optimal angle is 2π/e.

Alas, I think that may just be coincidence. I did a 10000-step simulation, and it covered ~2.3033 radians, about 4% less than 2Π/e≈2.3115 radians. I can't say for sure, but I'm guessing that's more of a discrepancy than can be accounted for by the fact that it's discrete rather than the continuous case.

The formula for the final angle in the continuous case is (for a generalized θ as a function of t):

θmax = ∫01 sin θ/r dt

The problem here is that r itself is a function of t, and an integral to boot. When we were deriving the formula for expected area, we were multiplying by r, so we could turn that into a double integral, but dividing by r is a whole different beast altogether.

We might be able to do it in the specific case θ=Πt/(t+1), where Wolfram Alpha does give a solution for r as a function of t, but it's kind of ugly.
posted by DevilsAdvocate at 9:24 AM on August 31, 2011

And I shouldn't try to do simple math in my head, because that's a 0.4% difference, not a 4% difference.

However, Wolfram Alpha gives ~2.30359 as the final angle.
posted by DevilsAdvocate at 9:46 AM on August 31, 2011

Some kind of monte carlo / genetic optimization on this would be interesting...
posted by unSane at 9:48 AM on August 31, 2011

Fantastic -- my favorite metafilter response yet. Thanks to all who contributed, especially unSane and DevilsAdvocate.

The solution is really satisfying -- its quasi-self-similarity, its gradually drifting towards perpendicularity, and especially the counterintuitive spot at which it terminates. (I will hold out hope that e really is somehow involved.)

I'm not sure whether or not I have the chops to model and genetically-optimize this in R, but now that the answer's form has been sketched so well, I'll give it a shot the next time I'm playing in R (and I'll post here if I turn up anything interesting). Thanks again -- very glad I asked this one.
posted by foursentences at 9:14 AM on September 1, 2011

« Older I need chocolate!   |   Soaked HDD Newer »