Math nerds

[Mark R]

I get 11:20. I solved this numerically.

This problem can be represented as a Markov chain model, from which it is possible to construct a sparse probability matrix M. If we create matrix P which is the probability matrix of santa's position, then it's just a matter of repeatedly mutliplying by M. Unfortunately, to make this difficult, M changes each hour.

So P is a 30 column matrix initially represented as {1,0,0,...,0}
M is a 30x30 matrix which looks like
{1/T, T-1/T, 0, 0, ..., 0}
{1/T, 0, T-1/T, 0, ..., 0}
.....
{0, 0, 0, 0, ..., 1}

After 1 move(s) [1:10], cum. prob. success is 0% (delta is 0%)
After 2 move(s) [1:20], cum. prob. success is 0% (delta is 0%)
After 3 move(s) [1:30], cum. prob. success is 0% (delta is 0%)
After 4 move(s) [1:40], cum. prob. success is 0% (delta is 0%)
After 5 move(s) [1:50], cum. prob. success is 0% (delta is 0%)
After 6 move(s) [2:00], cum. prob. success is 0% (delta is 0%)
After 7 move(s) [2:10], cum. prob. success is 0% (delta is 0%)
After 8 move(s) [2:20], cum. prob. success is 0% (delta is 0%)
After 9 move(s) [2:30], cum. prob. success is 0% (delta is 0%)
After 10 move(s) [2:40], cum. prob. success is 0% (delta is 0%)
After 11 move(s) [2:50], cum. prob. success is 0% (delta is 0%)
After 12 move(s) [3:00], cum. prob. success is 0% (delta is 0%)
After 13 move(s) [3:10], cum. prob. success is 0% (delta is 0%)
After 14 move(s) [3:20], cum. prob. success is 0% (delta is 0%)
After 15 move(s) [3:30], cum. prob. success is 0% (delta is 0%)
After 16 move(s) [3:40], cum. prob. success is 0% (delta is 0%)
After 17 move(s) [3:50], cum. prob. success is 0% (delta is 0%)
After 18 move(s) [4:00], cum. prob. success is 0% (delta is 0%)
After 19 move(s) [4:10], cum. prob. success is 0% (delta is 0%)
After 20 move(s) [4:20], cum. prob. success is 0% (delta is 0%)
After 21 move(s) [4:30], cum. prob. success is 0% (delta is 0%)
After 22 move(s) [4:40], cum. prob. success is 0% (delta is 0%)
After 23 move(s) [4:50], cum. prob. success is 0% (delta is 0%)
After 24 move(s) [5:00], cum. prob. success is 0% (delta is 0%)
After 25 move(s) [5:10], cum. prob. success is 0% (delta is 0%)
After 26 move(s) [5:20], cum. prob. success is 0% (delta is 0%)
After 27 move(s) [5:30], cum. prob. success is 0% (delta is 0%)
After 28 move(s) [5:40], cum. prob. success is 0% (delta is 0%)
After 29 move(s) [5:50], cum. prob. success is 0% (delta is 0%)
After 30 move(s) [6:00], cum. prob. success is 0% (delta is 0%)
After 31 move(s) [6:10], cum. prob. success is 0% (delta is 0%)
After 32 move(s) [6:20], cum. prob. success is 0% (delta is 0%)
After 33 move(s) [6:30], cum. prob. success is 0% (delta is 0%)
After 34 move(s) [6:40], cum. prob. success is 0% (delta is 0%)
After 35 move(s) [6:50], cum. prob. success is 0.00214334705075446% (delta is 0.00214334705075446%)
After 36 move(s) [7:00], cum. prob. success is 0.00398050166568686% (delta is 0.00183715461493239%)
After 37 move(s) [7:10], cum. prob. success is 0.00712990957699953% (delta is 0.00314940791131268%)
After 38 move(s) [7:20], cum. prob. success is 0.0269711794182694% (delta is 0.0198412698412699%)
After 39 move(s) [7:30], cum. prob. success is 0.0464846537422394% (delta is 0.01951347432397%)
After 40 move(s) [7:40], cum. prob. success is 0.0782835735045078% (delta is 0.0317989197622684%)
After 41 move(s) [7:50], cum. prob. success is 0.178160467202429% (delta is 0.0998768936979208%)
After 42 move(s) [8:00], cum. prob. success is 0.275419669717254% (delta is 0.0972592025148253%)
After 43 move(s) [8:10], cum. prob. success is 0.423316307113709% (delta is 0.147896637396455%)
After 44 move(s) [8:20], cum. prob. success is 0.764292684023601% (delta is 0.340976376909891%)
After 45 move(s) [8:30], cum. prob. success is 1.08495648052869% (delta is 0.320663796505086%)
After 46 move(s) [8:40], cum. prob. success is 1.53253621975402% (delta is 0.447579739225335%)
After 47 move(s) [8:50], cum. prob. success is 2.36631287332386% (delta is 0.833776653569843%)
After 48 move(s) [9:00], cum. prob. success is 3.13457410077715% (delta is 0.768261227453281%)
After 49 move(s) [9:10], cum. prob. success is 4.14927564954128% (delta is 1.01470154876413%)
After 50 move(s) [9:20], cum. prob. success is 5.81023839371001% (delta is 1.66096274416873%)
After 51 move(s) [9:30], cum. prob. success is 7.28440490989499% (delta is 1.47416651618498%)
After 52 move(s) [9:40], cum. prob. success is 9.10615402840808% (delta is 1.82174911851308%)
After 53 move(s) [9:50], cum. prob. success is 11.7621351083012% (delta is 2.65598107989312%)
After 54 move(s) [10:00], cum. prob. success is 14.0782252564956% (delta is 2.3160901481944%)
After 55 move(s) [10:10], cum. prob. success is 16.8273346783012% (delta is 2.74910942180563%)
After 56 move(s) [10:20], cum. prob. success is 20.5520523531351% (delta is 3.72471767483388%)
After 57 move(s) [10:30], cum. prob. success is 23.6952944614423% (delta is 3.14324210830721%)
After 58 move(s) [10:40], cum. prob. success is 27.2362143841795% (delta is 3.54091992273723%)
After 59 move(s) [10:50], cum. prob. success is 31.6784243127499% (delta is 4.44220992857038%)
After 60 move(s) [11:00], cum. prob. success is 35.3733101865109% (delta is 3.69488587376093%)
After 61 move(s) [11:10], cum. prob. success is 39.4112256404478% (delta is 4.03791545393692%)
After 62 move(s) [11:20], cum. prob. success is 44.239070610917% (delta is 4.82784497046925%)
After 63 move(s) [11:30], cum. prob. success is 48.1419257840106% (delta is 3.90285517309362%)
After 64 move(s) [11:40], cum. prob. success is 52.2296300317509% (delta is 4.08770424774024%)
After 65 move(s) [11:50], cum. prob. success is 56.8470377474321% (delta is 4.61740771568127%)
After 66 move(s) [12:00], cum. prob. success is 60.535159896163% (delta is 3.68812214873088%)
After 67 move(s) [12:10], cum. prob. success is 64.307331609279% (delta is 3.77217171311599%)
After 68 move(s) [12:20], cum. prob. success is 68.423987595519% (delta is 4.11665598624001%)
After 69 move(s) [12:30], cum. prob. success is 71.6308131030218% (delta is 3.20682550750278%)
After 70 move(s) [12:40], cum. prob. success is 74.7959555615079% (delta is 3.1651424584861%)
After 71 move(s) [12:50], cum. prob. success is 78.0989589142285% (delta is 3.30300335272055%)
After 72 move(s) [13:00], cum. prob. success is 80.6458102579237% (delta is 2.5468513436952%)
After 73 move(s) [13:10], cum. prob. success is 83.1117617805856% (delta is 2.46595152266198%)
After 74 move(s) [13:20], cum. prob. success is 85.6185429689799% (delta is 2.50678118839429%)
After 75 move(s) [13:30], cum. prob. success is 87.5087987773639% (delta is 1.89025580838401%)
After 76 move(s) [13:40], cum. prob. success is 89.2839105794407% (delta is 1.7751118020768%)
After 77 move(s) [13:50], cum. prob. success is 91.0231919513084% (delta is 1.73928137186766%)
After 78 move(s) [14:00], cum. prob. success is 92.3231396623708% (delta is 1.29994771106242%)
After 79 move(s) [14:10], cum. prob. success is 93.5245780928503% (delta is 1.20143843047944%)
After 80 move(s) [14:20], cum. prob. success is 94.6775018825279% (delta is 1.1529237896776%)
After 81 move(s) [14:30], cum. prob. success is 95.5220403739922% (delta is 0.844538491464297%)
After 82 move(s) [14:40], cum. prob. success is 96.2819858296977% (delta is 0.759945455705513%)
After 83 move(s) [14:50], cum. prob. success is 96.9888218685433% (delta is 0.706836038845615%)
After 84 move(s) [15:00], cum. prob. success is 97.5025563878162% (delta is 0.513734519272913%)
After 85 move(s) [15:10], cum. prob. success is 97.9586031597313% (delta is 0.456046771915075%)
After 86 move(s) [15:20], cum. prob. success is 98.3755840117937% (delta is 0.416980852062399%)
After 87 move(s) [15:30], cum. prob. success is 98.6731470221719% (delta is 0.297563010378188%)
After 88 move(s) [15:40], cum. prob. success is 98.9310971625% (delta is 0.257950140328156%)
After 89 move(s) [15:50], cum. prob. success is 99.1606428827377% (delta is 0.229545720237667%)
After 90 move(s) [16:00], cum. prob. success is 99.3233042673663% (delta is 0.162661384628604%)
After 91 move(s) [16:10], cum. prob. success is 99.4626633858515% (delta is 0.139359118485194%)
After 92 move(s) [16:20], cum. prob. success is 99.5849009845795% (delta is 0.122237598728003%)
After 93 move(s) [16:30], cum. prob. success is 99.6700759406701% (delta is 0.085174956090639%)
After 94 move(s) [16:40], cum. prob. success is 99.7415072227013% (delta is 0.0714312820311425%)
After 95 move(s) [16:50], cum. prob. success is 99.8026796320888% (delta is 0.0611724093875332%)
After 96 move(s) [17:00], cum. prob. success is 99.8450337531938% (delta is 0.0423541211049705%)
After 97 move(s) [17:10], cum. prob. success is 99.8801879838096% (delta is 0.035154230615797%)
After 98 move(s) [17:20], cum. prob. success is 99.9099218551467% (delta is 0.0297338713371342%)
After 99 move(s) [17:30], cum. prob. success is 99.9301908295683% (delta is 0.0202689744215778%)

Program code (yeah, yeah, it's C# - not terribly analytical, but it's all I've got to hand at the moment)

        private string RunSim()
        {
            string output = String.Empty;

            double[] M1 = new double[31];
            double[,] M2 = new double[31, 31];

            M1[0] = 1.0;
            int step = 1;
            double last = 0;
            do
            {
                int t = 1 + (step / 6);

                MakeMatrix(t, ref M2);
                M1 = MultiplyMatrix(M1, M2);

                output += String.Format("After {0} move(s) [{3}:{4}0], cum. prob. success is {1}% (delta is {2}%)\r\n",
                    step, M1[30] * 100, (M1[30] - last) * 100, step / 6 + 1, step % 6);

                last = M1[30];

                step++;
            } while (step < 100);

            return output;
        }

        private void MakeMatrix(int t, ref double[,] m)
        {
            double p = 1.0 / t; // backward step probability
            double q = 1.0 - p; // forward step

            m[0, 0] = p; // Probability of getting stuck at the beginning
            m[1, 0] = q;
            m[0, 1] = p; // One step back if santa has only gone forward 1 step
            m[2, 1] = q;
            for (int i = 2; i < 30; i++)
            {
                m[i - 2, i] = p; // 2 steps back 
                m[i + 1, i] = q;
            }
            m[30, 30] = 1.0; // Once he's made it to the sleigh, he stays there
        }

        private double[] MultiplyMatrix (double[] m1, double[,] m2)
        {
            double[] m3 = new double[m1.Length];

            for (int i = 0; i < m3.Length; i++)
            {
                double total = 0;
                for (int j = 0; j < m3.Length; j++)
                {
                    total += m1[j] * m2[i, j];
                }
                m3[i] = total;
            }
            return m3;

        }

 

[Born2bwire]

The probability of number steps at each hour is 6*(x-3)/x, which is simplified from probability step back as -2/x and probability step forward as (x-1)/x, times 6 (the number of step attempts per hour). Ignore time < 4 because probability is negative.

Plug that formula into Excel and you get:

Time / Steps / Sum
04 1.50 1.50
05 2.40 3.90
06 3.00 6.90
07 3.42 10.32
08 3.75 14.07
09 4.00 18.07
10 4.20 22.27
11 4.36 26.64
12 4.50 31.14
13 4.61 35.75
14 4.71 40.47

So probability is that he will reach 30 steps near the end of 11:00am.

I still contend that this is the wrong way to do it because you are still implicitly allowing negative distances from the door. Let's take the time from 2-2:50 AM. The probability of advancing and retreating are both 50&#37;. If we look at a single event, at 2:00 AM, then the expectation value calculated naively is -0.5. However, we cannot move backwards, so the actual expectation value is 0.5 (because at 2:00 AM we know that we have to be at the doorstep). Now at 2:10 AM, we can be either at 0 or +1. The expectation values are now 0.5 and 1 for either start state, the total expectation value now being 0.75. And so on and so on. Thus, your expectation value for the hour of 2 AM cannot be zero because that is treating the entire hour as a single event in which Santa can move backwards (which, upon seeing this erroneous result you just throw it out instead of correcting it).

It's nice to see Mark R evaluate the problem in an efficient way. In brute force, I had to do 100K+ runs and even then I had a slight variance in the results (but the mean and mode remained consistent). Using the Markov chain, Mark R only needed to do a matrix multiplication to generate the results over 100 steps.

 

[BoT]

he'll never make it to the sled.
it takes him 6 steps per hour which results in 5 hours in the best case scenario
in the 5th hour the odds are 1/5 he will be going a lot more backwards then forward.

the longer the trip takes the less probable is that he will reach his goal.
he won't make it in 5 hours because by then the odds are already exceeding
he actually lost after the second hour

thats all of course if i understood that with the odds correctly

 

[mjrpes3]

I still contend that this is the wrong way to do it because you are still implicitly allowing negative distances from the door.

I agree with you; the effect is fairly minor but substantial. It probably explains why Mark R hit the 50&#37; point at 11:30-11:40 instead of 11:40-11:50 in my calculation. My goal however was to try to come up with a fairly approximate answer using as little raw calculating as possible (so you can do napkin math ). Would love to know if it would be possible to factor in the negative distance effect into the equation without it getting too complex.

EDIT: I realized I've been doing it the wrong way because I assumed some sort of linear bell shaped graph where the middle point (50%) was the highest probability. = It's roughly like that but much more coarse and uneven at top due to the discreteness here. Mark R's 11:20 delta makes sense now.

 

[mjrpes3]

Very interesting distribution (using Mark R's results). It's bell shape but with pronounced bumps in probability every 4th step.

 

[Born2bwire]

Very interesting distribution (using Mark R's results). It's bell shape but with pronounced bumps in probability every 4th step.

I found that if you allow for negative distances, the results follow a very nice bell curve. I believe that the irregularities arise due to the restriction on moving backwards. Probably has to do with the fact that there is a smaller probability of moving forward than restarting at the doorstep for the early moment around 2 AM. These cases then propagate out forward so that once we are far removed from the doorstep, the distribution is bell like, but the irregularities arise from the slight variations from the paths near the doorstep.