Don't wake the baby

[dtm]

A math problem vaguely inspired by life:

Say you have to walk from point A to point B. Now, the catch is that you have to take each step so as to not wake the baby sleeping at point A. If you wake her, you have to go back to point A and spend the time during which you could take n steps comforting her until she goes back to sleep. The probability of the baby waking during any step is equal to the portion of the distance covered during that step - in other words, if you try to go from A to B in one step, she'll certainly awaken (longer steps are louder, you see). If you try to take it in two equal-sized steps, you have a 1/4 chance of making it across.

Now, you're trying to get to point B as quickly as possible. (Assume that each step takes the same amount of time). What's your optimal strategy? What is the expected number of steps taken?

First take this problem with n = 0; that is, the only penalty for waking the baby is that you have to start over from point A.

What if we change things so that the probability of her waking is equal to k times the portion of the distance covered? (So that for k=2, she is certain to wake if we try to cover half the distance in a single step)

Comments

[chrysoula.livejournal.com]

Math Dad.

Geeking

[caelano.livejournal.com]

E(x) = expected number of steps from fraction x
E(1) is of course 0 (at destination)
E(x) = 1 (take a step) + (1-(y-x))E(y) (get to y without waking baby) + (y-x)*E(0) (must see to baby)
given points x1,x2...xn(=1) as steps, recurse to find expected number of steps as a function of step points, find optimum step points given the function. Note that optimal strategy does not involve changing step points after seeing the baby.
For 2 steps, I come out with E(0) = (2-x)/(x*(1-x)) x=2-sqrt(2) for optimal strategy, or 3+2*sqrt(2) steps. [take a big step, hope to not wake the baby, then take a smaller step] 3 steps does not seem to help.

Note that (1-1/n)^n -> 1/e, so even taking many small steps does not help much to avoid waking the baby most of the time.
Recursion can be updated for extra penalty terms in the obvious way, but if the baby is very cranky, it will take you an exponentially large number of steps (1-k/n)^n ->1/e^k ...
[No testimony that my arithmetic is correct here, but I believe the recursion is right modulo typos]

Re: Geeking

[dtm]

That answer (Take 2 steps, 2 - \sqrt{2} for the first step) agrees with what I got for n=0 - my method is slightly different from yours; it was more ad hoc - but your overall method seems right.