Time to finish route heuristic problem

[slightlydead]

Say you're want to go from point a to point b which is comprised of X steps.

Let's say each step takes one second to complete and every step you have a constant chance (Y%) of being sent back to point a(you do not lose time being sent back). You do have the option of spending Z seconds and changing point a to your current position. You can do this an unlimited amount of times.

This is a general case, but for the sake of making a concrete example, let's say Y=5, z=5, and steps =100. How often then do you think Point A should be moved during the trip and during what intervals? How would you model this problem?


At the extremes, we could move Point A every single step we can take, but that would take ~520 seconds to do. The best case, would be if we never moved Point A and just ran through, that would take 100 second but the chance of that happening is .95^100~=.5%. Not too good odds. How would you set up this risk vs reward heuristic to get the best numbers on average?

Edit: Not hw, actually based on watching a SDA video of "pokemon yellow". Some guy ran through a cave without a single encounter but he did it segmented for the purposes of his sanity.

[Goplat]

Suppose your policy is to move point A once you've moved by L steps. The probability of making it at least S steps in an individual attempt without getting sent back (0 <= S <= L) is (1-Y)^S, so the average number of steps made per attempt is 1 + (1-Y) + (1-Y)² + ... + (1-Y)^L-1, which can be rewritten as (1 - (1-Y)^L)/Y. Since the probability of an attempt being successful is (1-Y)^L, the average number of attempts made for the segment is (1-Y)^-L, and the average time taken for the segment is ((1-Y)^-L - 1)/Y + Z. There are X/L segments to get through, so the total average time taken is X/L * (((1-Y)^-L - 1)/Y + Z).

There is no possible formula for choosing L to minimize this time, unfortunately, so you just have to try different values to see which one is best.

[ConMan]

NINJA'd by Goplat - but he seems to be working solely from a "Save once and once only" standpoint, whereas I'm assuming an arbitrary number of saves. See below:

So in other words, you have a "start point", and "end point" and a "current position" between the two. Let's call the distance from the start point to the end point n, and the distance from the current position to the end point m - this is based solely on where the last "save" was made, and independent of where the original start point was, since we're assuming the probability of a "reset" on any given step is independent of all other factors.

We have a strategy S(m, n), that tells us whether to "save" depending on where we and the save point are relative to the end point, so we can calculate E(m, n | S) - the expected amount of time it will take you to get to the end point, given your strategy. Thankfully, because of the way this is set up, we can write that in a pretty straightforward way:

If S(m, n) = "save", then E(m, n | S) = t_save + E(m, m) <- in other words, the time it takes us to put down a save point, plus the time we would expect to take given that we're now starting from that save point. Let's call this E_1(m, n)

If S(m, n) = "don't save", then E(m, n | S) = t_step + p E(n, n) + (1 - p) E(m - 1, n) <- in other words, the time it takes to make the step, plus the contribution from having to go back to the start point times the probability of having to do so, plus the expected time it will take us from the next step onwards times the probability that we don't get sent back. Let's call this E_0(m, n)

Some things to note are:
* m <= n
* We can simplify by writing everything in terms of a single step time, i.e. t_step = 1 and t_save is calculated in terms of "step times".
* E(0, n) = 0, since once we reach the end point there will always be zero time left to reach the end point, independent of our strategy

So now what can we do? Well, we have a set of boundary conditions, so we can work backwards from them, adding in the assumption that we always want to minimise E(m, n | S) - so we want to choose S such that we place the save points at the best possible locations to minimise our expected time. In other words, S(m, n) = "save" when E_1(m, n) < E_0(m, n) and S(m, n) = "don't save" when E_1(m, n) > E_0(m, n). What happens if they're equal? It doesn't change our expected time, so we could pick a "better safe than sorry" option and always save in those cases, or we could go with "he who hesitates is lost" and never save. Since I am, by nature, a cautious person, I'll go with the former.

The first thing you can notice pretty quickly is that after we've saved, we will always take a step - we know we don't need to save again. So S(n, n) = "don't save" and E(n, n | S) = E_0(n, n) which we can use to show that E(n, n | S) = 1/(1-p) + E(n-1, n | S). And that means that E(1, 1 | S) = 1/(1-p), i.e. if there's only one step you need to take, the expected amount of time it will take you to get to the end point is the inverse of the probability that you successfully make the step without being sent back - which makes sense, so our formulas are working fine so far.

We can also go one step further, which is to say that E_1(1, n) = t_save + 1/(1-p) <- if we save on the last step, then the expected amount of time is just the time it takes to save plus the previously calculated expected time of taking one step.

At this point, it gets a little tricky since we have to essentially do a sort of two-dimensional induction - the values E(m, n | S) depend directly on the other values for E(m', n | S) for 0 >= m' >= n, but also on E(m, n - 1 | S), so you have to do a bunch of manipulations between the various values of m at a given n, then feed those into the "next layer up" of n + 1. And those all depend on t_s and p.

I'll try to post some more on this later.

[ConMan]

Ok, the next piece of the puzzle is to realise that for the strategy S which minimises the expected times at all steps, E(m, n | S) <= E_0(m, n) and also E(m, n | S) <= E_1(m, n), with the equalities happening when we choose that relevant strategy.

For example, let's calculate S(m, 2) and E(m, 2 | S) for m = 0, 1, 2. We know that:
* E(0, 2) = 0
* E(1, 1) = 1/(1-p)

Also, E(n, n | S) = E_0(n, n) (i.e. never save twice) = 1 + pE(n, n | S) + (1 - p)E(n - 1, n | S) so E(n, n | S) = 1/(1 - p) + E(n - 1, n | S) and hence E(2, 2 | S) = 1/(1 - p) + E(1, 2 | S)

E_1(1, 2 | S) = t_save + E(1, 1 | S) = t_save + 1/(1 - p)
E_0(1, 2 | S) = 1 + (1 - p)E(0, 2 | S) + pE(2, 2 | S) = 1 + 0 + p(1/(1 - p) + E(1, 2 | S))

So now, using the first line of this post, we can save that E(1, 2 | S) <= E_0(1, 2 | S) = 1 + p/(1 - p) + pE(1, 2 | S) which implies that E(1, 2 | S) <= 1/(1 - p) + p/(1 - p)^2, with equality when E_0 < E_1, which we can show happens when t_save >= p/(1 - p)^2.

From that, we can then say that:
S(1, 2) = "save" if t_save <= p/(1 - p)^2

And hence that:
E(1, 2 | S) = t_save + 1/(1 - p) if t_save <= p/(1 - p)^2, or 1/(1 - p) + p/(1 - p)^2 otherwise.

And we also have:
E(2, 2 | S) = 1/(1 - p) + E(1, 2 | S)

Past this, it looks like it gets into some nasty induction, which I'm not sure how well it can be simplified/automated. I'll keep on with it, just out of interest sake.

[Goplat]

NINJA'd by Goplat - but he seems to be working solely from a "Save once and once only" standpoint, whereas I'm assuming an arbitrary number of saves. See below:

Actually, I assume saving with a fixed period (every L steps). This may not be quite optimal if L doesn't divide evenly into X (but if X is large it doesn't matter much).

[ConMan]

NINJA'd by Goplat - but he seems to be working solely from a "Save once and once only" standpoint, whereas I'm assuming an arbitrary number of saves. See below:

Actually, I assume saving with a fixed period (every L steps). This may not be quite optimal if L doesn't divide evenly into X (but if X is large it doesn't matter much).

Ah, my mistake. Yes, you did make that assumption.

Anyway, to continue my crazy thoughts:

Under the optimal strategy, for every n there is an m which is the point at which you definitely save. As such, we can calculate a string of E_0's from E_0(n, n) up to the E_0(m, n) where it is greater than E_1(m, n), i.e. t_s + E_0(m, m). And I *think* that means you can, for each n, store a pair of values at a time - the m where the crossover occurs, and E_0(n, n). And, if you want, you can also store E_1(m, n) just to add them all together to get your final value. As such, E(m + 1, n | S) will equal E_0(m + 1, n | S) = 1 + (1 - p)E(m, n | S) + pE(n, n | S) = 1 + (1 - p)E_1(m, n) + pE_0(n, n) = 1 + (1 - p)(t_save + E_0(m, m)) + p E_0(n, n) <- so now we have our sequence of E_0(m', n) for m' between m and n, that relies only on already-known p, t_save and E_0(m, m), and the as-yet-unknown E_0(n, n). Then we can cascade down, and try to solve for E_0(n, n) and m.

EDIT FOR MORE STUFF:

So, for some m, we can set E(m, n) = E_1(m, n) and then for m' > m, E(m, n) = E_0(m, n). Using a bit of induction (or breaking things down into geometric series), you can show that:

E_0(m + k, n) = [1 - (1 - p)^k]/p * [1 + p E_0(n, n)] + (1 - p)^k * [t_save + E_0(m, m)]

And, from that, deduce that:

E_0(n, n) = 1/p * [(1 - p)^(m - n) - 1] + t_save + E_0(m, m)

The hard part is then working out what m is.

[freakish777]

@Goplat, that policy is non-optimal. The closer you are to the destination, the less often you should make your current location the save point.

There should be some type of decaying frequency with which you save, like:

2, 4, 8, 16, 32, 64

Or whatever.

Say you have no save point, and are at position 99 (as per the initial post's numbers). Your chance of being sent back is 5%. You have:

• 0.95 * 1 Second +
• 0.05 *
  • 0.5 * 100 seconds + //go back only once
  • 0.5 *
    • 0.5 * 100 seconds + //go back twice
    • 0.5 *
      • 0.5 * 100 seconds + //go back 3 times
      • 0.5 *
        • etc

Should yield an average time of 5.95 seconds to travel the last step. Compared to creating a save point (5 seconds) and moving (1 second), you're saving at least 0.05 seconds on average (not gonna bother with the percentage chance here).

So, with the initial posts numbers, my assumption is the because Y is so large, it would actually be optimal to create save points at almost all points, except perhaps the last handful.

Basically, you want to compute the average time it will take at each step, and compare with the average time of reaching the goal with creating the save point at the current position.

[Goplat]

@Goplat, that policy is non-optimal. The closer you are to the destination, the less often you should make your current location the save point.

There's no difference between e.g. a 0-to-20 segment and an 80-to-100 segment. A segment of a particular length takes the same expected time to complete successfully no matter where it is, so there is no reason to prefer shorter segments near the beginning or longer segments near the end.

With the original numbers, the optimal segment length (in terms of time per distance covered) is 11. The best way to get to 100 is with eight 11-length segments and one 12-length; it will take 178.3 seconds on average.

Say you have no save point, and are at position 99 (as per the initial post's numbers). Your chance of being sent back is 5%. You have:

• 0.95 * 1 Second +
• 0.05 *
  • 0.5 * 100 seconds + //go back only once

If you get sent back, the probability that you won't go back any more isn't 0.5, it's 0.95¹⁰⁰ ~ 0.006. Most likely you will go back many times.

[freakish777]

There's no difference between e.g. a 0-to-20 segment and an 80-to-100 segment.

Sure there there is. The 80-100 segment is closer to the overall goal, making the expected value of creating a save point on any node in it less than the expected value of creating a save point on any node in the earlier segment.

If you get sent back, the probability that you won't go back any more isn't 0.5, it's 0.95¹⁰⁰ ~ 0.006. Most likely you will go back many times.

My bad, I missed the percent sign in the opening post on the following:

.95^100~=.5%

That shouldn't change the fact that the expected value of a save point changes on each node and that there's optimal nodes to place them on (that don't follow a static frequency).

[Goplat]

There's no difference between e.g. a 0-to-20 segment and an 80-to-100 segment.

Sure there there is. The 80-100 segment is closer to the overall goal, making the expected value of creating a save point on any node in it less than the expected value of creating a save point on any node in the earlier segment.

Talking about the expected value of creating a save point at a particular node is not a useful concept - it depends on both the previous save point you created and the next one you're going to create, so you can't consider nodes independently. If you've only decided you're going to save at 20, adding a save point at 10 is beneficial. If you've decided you're going to save at 9 and 11, adding a save point at 10 is a waste.

If you don't believe me that save points should be spaced about uniformly, write a simulator and see for yourself. Or if you have Python, use mine. Try the different settings for savepts and see how they perform.

Code: Select all

import random

# Problem parameters
Y = 0.05
Z = 5
steps = 100

# Strategy
savepts = set((11, 22, 33, 44, 56, 67, 78, 89)) # Uniform spacing
#savepts = set((5, 10, 15, 20, 30, 40, 60, 80)) # More saves near beginning
#savepts = set((20, 40, 60, 70, 80, 85, 90, 95)) # More saves near end

trials = 1000
time = 0
for _ in xrange(trials):
   pos = 0
   save = 0
   while pos < steps:
      if pos > save and pos in savepts:
         save = pos
         time += Z
      time += 1
      pos += 1
      if random.random() < Y:
         pos = save
print "Average time:", time * 1.0 / trials


[freakish777]

Then there shouldn't be any difference between the following?

savepts = set((12, 23, 34, 45, 56, 67, 78, 89)) # Uniform spacing, first point at 12, last point 11 away
savepts = set((11, 22, 33, 44, 55, 66, 77, 88)) # Uniform spacing, first point at 11, last point 12 away

When I increase the number of trials to 100,000 (really 100,000,000 would be nice for confidence in the results, but I don't have all day to let it run), I get 178.26135 for the second, and 178.3827 for the first.


savepts = set((10, 21, 32, 43, 54, 65, 76, 88)) # More points near beginning

Yielded 178.28684 (in between) and:

savepts = set((10, 20, 32, 45, 58, 72, 86)) # More saves near beginning, one less point

Yielded 179.8081 (about 1.5 seconds behind). All of this leads me to believe that 100 steps, 5% and 5 seconds are more restrictive compared to the general case.

it depends on both the previous save point you created and the next one you're going to create, so you can't consider nodes independently. If you've only decided you're going to save at 20, adding a save point at 10 is beneficial. If you've decided you're going to save at 9 and 11, adding a save point at 10 is a waste.

Correct, it depends on the last time you saved, and how much farther you have to go. Like I said, start at your current position, calculate the average time it takes to get to the end from your current position (which is dependent on where you last saved), and compare it to the average time it takes to get to the goal if you create a save point at your current location.

The higher the number of steps there are until the finish, the higher the expected value of a save point.
The higher percentage chance of being sent back, the higher expected value of a save point.
The higher cost of creating the save point, the lower expected value of creating a save point.

These are all (obviously) true. However, one of these parameters changes while we're in the middle of the task (the steps left until the finish).

[Goplat]

Then there shouldn't be any difference between the following?

savepts = set((12, 23, 34, 45, 56, 67, 78, 89)) # Uniform spacing, first point at 12, last point 11 away
savepts = set((11, 22, 33, 44, 55, 66, 77, 88)) # Uniform spacing, first point at 11, last point 12 away

When I increase the number of trials to 100,000 (really 100,000,000 would be nice for confidence in the results, but I don't have all day to let it run), I get 178.26135 for the second, and 178.3827 for the first.

That's not a statistically significant difference. The standard deviation for individual trials is about 21, so for the average of 100000 trials it's about 21/sqrt(100000) = .066. The results deviate from my prediction (178.30626) by only -0.7 and 1.2 sigmas respectively.

it depends on both the previous save point you created and the next one you're going to create, so you can't consider nodes independently. If you've only decided you're going to save at 20, adding a save point at 10 is beneficial. If you've decided you're going to save at 9 and 11, adding a save point at 10 is a waste.

Correct, it depends on the last time you saved, and how much farther you have to go. Like I said, start at your current position, calculate the average time it takes to get to the end from your current position (which is dependent on where you last saved), and compare it to the average time it takes to get to the goal if you create a save point at your current location.

It depends on how much farther you have until the next save point, not your overall progress towards the goal.

It seems you're thinking in terms of a "greedy algorithm" that neglects to take your own future actions into account. I move to 1, I save because saving at 1 is better than no saves at all. I move to 2, I save again because saving at 1 and 2 is better than saving at just 1. But this is already not optimal - my save at 2 subsumes almost all the benefit I got from saving at 1. If I was at 1 and already knew I was going to save at 2, I would have recognized that saving at 1 was wasteful and not bothered.

[Yakk]

Suppose our next save is going to be at location y, and we are at location x (a save point). We are only allowed one save point between x and y.

If we put a save at location z, we can work out the cost-benefit of this save point relative to others.

Now, costs of a save at a given location are fixed. So other than deciding if we want that intermediate point, we can ignore costs to determine where the ideal point is between two given save points.

The argument from symmetry is pretty decent that it should be at the half-way point. The game of "get to the middle save point" and "get from the middle save point to the end point" are only determined by the length between the points. We'd need to throw in a convexity/concavity argument or something to prove that the average point is ideal. Suppose we have this lemma proven.

So we back up and look at a entire set of save points. Pretend we removed one, and wanted to replace it with a better one. In a non-uniform case, replacing one that isn't on the average location between its adjacent save points with one that is improves the time to win! So if non-uniform save points are ideal, it does have to be locally uniform.

Of course, we could short circuit this entire algorithm, and break our game down into a bunch of sub games. Each sub game is getting from one save point to the next. The time it takes to win, on average, is the sum of the average time in each save game! And with convexity of a certain sort, if any sub game is longer than another by 2, we can grow the short sub game and shrink the long sub game and end up with a shorter overall time. On top of this, the sum of sub games clearly doesn't care about the order the sub games where in on the original path. Between these two, we can construct a pretty robust proof that the ideal solution is with uniformly spaced saves, and a bias for longer/shorter saves at the start/end of the path does nothing, like my goggles...

(Note that the above just contains sketches of proofs, not the proofs themselves. I'm hoping it is convincing, nonetheless).

[freakish777]

Now, costs of a save at a given location are fixed.

I think your view of this as being a fixed cost only, may be skewing things. While the fixed cost is the same, there's an opportunity cost you end up paying later by not hedging your bets early.



Python 3.whatever code:

Code: Select all

import random
import itertools

# Problem parameters
Y = 0.05
Z = 5
steps = 100
i = 0
stepsActual = []

while i < steps:
    i+=1
    stepsActual.append(i)
   
j = 0




allCombinations5 = []

#At 12 save points, we have 160 seconds minimum, so the average can't possibly get better than the 178ish we're looking for
for L in range(0,12):
    for savepts in itertools.combinations(stepsActual, L):
            trials = 1000
            time = 0
            for _ in range(trials):
               pos = 0
               save = 0
               while pos < steps:
                  if pos > save and pos in savepts:
                     save = pos
                     time += Z
                  time += 1
                  pos += 1
                  if random.random() < Y:
                     pos = save
            if ((time * 1.0 / trials) < 179):                     
                print(str(savepts) + '\t' + str(time * 1.0 / trials))
            j += 1
            if (j % 100000 == 0):
                print(str(j) + ' combinations checked' + str(savepts))
   


I've modified the above, looking only in range 8-9 (since I had claimed I thought there was a good change at there being a series with 8 save points that outperformed the evenly spread one Goplat arrived at, and I also changed the number of trials from 1000 to 250 (both of these are to save time, so far my machine has completed 200,000 test combinations). The plan was to take the list of savepts it spits out and subject them to much larger trial sizes to get more accurate times.

Even at just the 100 choose 8, there's about 186,000,000,000 combinations to get through, so I don't think this will be completing any time soon.

It's entirely possible that biasing save points towards the beginning is too greedy in some way, and that evenly spread points are optimal, but I'm unconvinced thus far that evenly spread points are in fact optimal.

Anyone have access to a really fast machine??

[Yakk]

Now, costs of a save at a given location are fixed.

I think your view of this as being a fixed cost only, may be skewing things. While the fixed cost is the same, there's an opportunity cost you end up paying later by not hedging your bets early.

I was doing a cost benefit analysis. The opportunity cost is factored in with the benefits.

Opportunity cost is the "cost" of "benefits forgone by the choice". If I calculate the benefits for each possible decision, and the costs of each possible decision, then find the one with the highest (benefits)-(costs), opportunity costs have been factored in already.

Do you have a valid objection to my reasoning? There are quite possibly flaws, but this doesn't look like one of them.

[freakish777]

I was doing a cost benefit analysis. The opportunity cost is factored in with the benefits.

Opportunity cost is the "cost" of "benefits forgone by the choice". If I calculate the benefits for each possible decision, and the costs of each possible decision, then find the one with the highest (benefits)-(costs), opportunity costs have been factored in already.

Do you have a valid objection to my reasoning? There are quite possibly flaws, but this doesn't look like one of them.

Yes.

The time it takes to win, on average, is the sum of the average time in each save game!

Say you have uniform sub games (not uniform save points, but areas you've broken everything up into). I agree that you are looking to minimize the sum of these sub games to get the best possible time. However, if possible, we want to minimize the first sub game more than the other sub games. This is due to the fact that the first nodes will be the most visited. Obviously, we can't do this at such a high expense to the last nodes that they make us take longer.

The benefit forgone by the choice here is not repeating the first nodes over and over and over and over. Having a stable "each sub section of X nodes takes us the same amount of time" might actually be optimal, but it certainly doesn't seem optimal to me. If the first X nodes are capable of being minimized with 2 save points in them at the expense of the last 2X nodes taking longer, I think there exists the possibility of that being the optimal solution. Granted, it may not be, given the numbers we're using for this experiment (Y = 5%, Z = 5 seconds), and may only become evident when the time it takes to create a save point goes down, or the chance of being sent back goes up.

[Yakk]

No, you still aren't pointing out a flaw in my argument. I'll formalize it if it might help.

First, a simple lemma:
Lemma 1: Suppose you have two save points. When you add an additional save point, the optimal spot to place it (to minimize travel time between the two original save points) is the half way point.

I believe I sketched out why this is true in a previous post. Do you disagree with it?

This lemma builds on the previous one:
Lemma 2: If you have a length of with a save point at each end, and a save point somewhere in the middle, and no other save points, moving that save point to the middle of the interval will not increase the length of time it takes to go from one end of the interval to the other.

It is pretty easy to prove this using lemma 1. We simply remove the middle save point, and note that the most efficient spot to put it is in the middle, so it can't be worse than our original spot!

Lemma 3: The average time it takes to get from the start to the end of the track is the sum of the time it takes to get from the starting location, to save point 1, then save point 1 to save point 2, ..., then save point n to the end location.

Is this the one you are disagreeing with?

Lemma 4: A non-uniformly placed set of points is sup-optimal (to the degree that you can make your points uniform). Or, a uniformly placed set of points is the optimal solution.

This follows pretty easily from 2 and 3. If we are non-uniformly placed, using #2 lets us find a better solution.

So, where do you disagree with my logic, explicitly? I'm aware that "it doesn't feel right" to you. That really isn't material.

I think there exists the possibility of that being the optimal solution.

That possibility only exists if the proof sketched above isn't valid for some reason.

[Snark]

the average number of attempts made for the segment is (1-Y)^-L, and the average time taken for the segment is ((1-Y)^-L - 1)/Y + Z.

First, I'm going to steal this. Average time to go S steps without saving (assuming you start on a save) is ((1-Y)^-S - 1)/Y

For simplicity, let's let X be arbitrarily large.

Then assume that we went S steps from our closest save point.
Expected time to get to S+1 if you save at step S = Z + 1/(1-Y)
Expected time to get to S+1 without saves = (1-Y)*1 + Y*(((1-Y)^-S-1 - 1)/Y) = (1-Y)^-S-1 - Y

For Y = .05 and Z = 5, expected time with saving = Z + 1/(1-Y) = 5 + 1/.95 = 6.0526 seconds
For Y = .05 and Z = 5 and S = 34, expected time without saving = (1-Y)^-S-1 - Y = .95^-35 - .05 = 5.9711 seconds
For Y = .05 and Z = 5 and S = 35, expected time without saving = (1-Y)^-S-1 - Y = .95^-36 - .05 = 6.2880 seconds

So the optimal solution is to save every 35 steps if you're going forever. But the optimal steps when X = 100 seem to be close to 10/11. Can anyone spot an error in my math? Because I sure can't.

[freakish777]

No, you still aren't pointing out a flaw in my argument. I'll formalize it if it might help.

First, a simple lemma:
Lemma 1: Suppose you have two save points. When you add an additional save point, the optimal spot to place it (to minimize travel time between the two original save points) is the half way point.

I believe I sketched out why this is true in a previous post. Do you disagree with it?

Why is this obviously true?

Essentially I'm not seeing how this is so obvious that we can assume it to be true and base the rest of an argument off of that.

[freakish777]

the average number of attempts made for the segment is (1-Y)^-L, and the average time taken for the segment is ((1-Y)^-L - 1)/Y + Z.

First, I'm going to steal this. Average time to go S steps without saving (assuming you start on a save) is ((1-Y)^-S - 1)/Y

For simplicity, let's let X be arbitrarily large.

Then assume that we went S steps from our closest save point.
Expected time to get to S+1 if you save at step S = Z + 1/(1-Y)
Expected time to get to S+1 without saves = (1-Y)*1 + Y*(((1-Y)^-S-1 - 1)/Y) = (1-Y)^-S-1 - Y

For Y = .05 and Z = 5, expected time with saving = Z + 1/(1-Y) = 5 + 1/.95 = 6.0526 seconds
For Y = .05 and Z = 5 and S = 34, expected time without saving = (1-Y)^-S-1 - Y = .95^-35 - .05 = 5.9711 seconds
For Y = .05 and Z = 5 and S = 35, expected time without saving = (1-Y)^-S-1 - Y = .95^-36 - .05 = 6.2880 seconds

So the optimal solution is to save every 35 steps if you're going forever. But the optimal steps when X = 100 seem to be close to 10/11. Can anyone spot an error in my math? Because I sure can't.

Assuming equal spacing is in fact optimal, it doesn't make sense that there should be a difference for how many nodes to travel between "going for set distance X" and "going forever." Going forever can logically be broken up into optimizing "going for set distance X" over and over again (if 11 is the optimal number, then X should be a multiple of 11, to avoid small inaccuracies of accidentally stretching (to 12)/compressing (to 10) a section in between 2 save points).

[Snark]

the average number of attempts made for the segment is (1-Y)^-L, and the average time taken for the segment is ((1-Y)^-L - 1)/Y + Z.

First, I'm going to steal this. Average time to go S steps without saving (assuming you start on a save) is ((1-Y)^-S - 1)/Y

For simplicity, let's let X be arbitrarily large.

Then assume that we went S steps from our closest save point.
Expected time to get to S+1 if you save at step S = Z + 1/(1-Y)
Expected time to get to S+1 without saves = (1-Y)*1 + Y*(((1-Y)^-S-1 - 1)/Y) = (1-Y)^-S-1 - Y

For Y = .05 and Z = 5, expected time with saving = Z + 1/(1-Y) = 5 + 1/.95 = 6.0526 seconds
For Y = .05 and Z = 5 and S = 34, expected time without saving = (1-Y)^-S-1 - Y = .95^-35 - .05 = 5.9711 seconds
For Y = .05 and Z = 5 and S = 35, expected time without saving = (1-Y)^-S-1 - Y = .95^-36 - .05 = 6.2880 seconds

So the optimal solution is to save every 35 steps if you're going forever. But the optimal steps when X = 100 seem to be close to 10/11. Can anyone spot an error in my math? Because I sure can't.

Assuming equal spacing is in fact optimal, it doesn't make sense that there should be a difference for how many nodes to travel between "going for set distance X" and "going forever." Going forever can logically be broken up into optimizing "going for set distance X" over and over again (if 11 is the optimal number, then X should be a multiple of 11, to avoid small inaccuracies of accidentally stretching (to 12)/compressing (to 10) a section in between 2 save points).

I agree they should be similar despite the size of X, but the maths seem to indicate that a length around 35 is optimal while trial and error show that this is not the case (that 10/11 is optimal).

[Yakk]

No, you still aren't pointing out a flaw in my argument. I'll formalize it if it might help.

First, a simple lemma:
Lemma 1: Suppose you have two save points. When you add an additional save point, the optimal spot to place it (to minimize travel time between the two original save points) is the half way point.

I believe I sketched out why this is true in a previous post. Do you disagree with it?

Why is this obviously true?

Essentially I'm not seeing how this is so obvious that we can assume it to be true and base the rest of an argument off of that.

I believe I sketched out why it is true in a previous post. Namely:

Suppose our next save is going to be at location y, and we are at location x (a save point). We are only allowed one save point between x and y.

If we put a save at location z, we can work out the cost-benefit of this save point relative to others.

Now, costs of a save at a given location are fixed. So other than deciding if we want that intermediate point, we can ignore costs to determine where the ideal point is between two given save points.

The argument from symmetry is pretty decent that it should be at the half-way point. The game of "get to the middle save point" and "get from the middle save point to the end point" are only determined by the length between the points. We'd need to throw in a convexity/concavity argument or something to prove that the average point is ideal.

I can make this sketch of a proof explicit if you'd like.

We have n steps, and our goal is to minimize the time to reach step n.

Let T(z) be the time it takes, on average, to go from one save point to another one z steps away. Then if we have a gap of length n in which we put a single point z, the average time it takes to finish is T(z) + T(n-z). Clearly this is symmetric around n/2.

Suppose T(z) is convex up. Then T(lambda z) >= lambda T(z) (the definition of convex up)
Examine T( z / (n/2) * n/2 ) + T ( (n-z)/(n/2) * (n/2) ) >= (2z/n) + 2(n-z)/n) * T(n/2) = 2 T(n/2)
This means that the minimal point of T(z) is at z = n/2.

Now, for odd n, this requires filling in the blanks between the points -- but a linear interpolation between points is sufficient.

So all we have to show is that the time it takes to get to a save point z steps away is convex up.

Lemma 0: The time it takes to get to save point z steps away is convex up.

Do you see how Lemma 1 follows from 0?

That is what I meant by "you can prove this via symmetry and an argument from convexity", done a bit more formally.

The time it takes to go z steps to the next save has been covered by other posters in this thread.