# Probability: Expected distance of an accelerating car - with a twist

1. Apr 28, 2014

### HexNash

I have an expected value probability problem. Unfortunately, I do not know enough about mathematics to determine if it is even remotely feasible to try to solve it. The best way to explain it is to disguise it as a physics problem:

Imagine a race car on a never-ending straight track. Let's call the position it starts at 0 units, and its starting velocity is 0 units per turn. Suppose we generate a random number from 1 to 60. If any number except 60 comes up, its current velocity is increased by 1, and the car is moved forward the number of units corresponding to the new velocity. However, if a 60 is rolled, it crashes: the current velocity is reset to 0, and the car is not moved (as the new velocity is 0u/t).

Now, the initial problem I worked out was how many units, on average, the car will travel before it crashes once. That was fairly easy: because the distance the car travels corresponds to a triangular number [n(n+1)/2], and the probability of the trial ending is always 1/60 each turn, the expected value corresponds to the equation: sum of (n(n+1)/2)(1/60)(59/60)^n from n=0 to n=infinity = 3540

However, I have another problem I am trying to solve that is proving much more difficult:
What is the expected distance of the car after 60 (or in general, n) turns?
In this scenario, when a car crashes, its velocity is reset to 0, but it is still "in the race" for the remaining number of turns.

I have tried all different kinds of techniques to try to figure this out, but to no avail. I'm hoping this isn't too complicated or tedious to compute, but considering there are 966,467 ways to partition 60, all with differing odds of occurring, I'm not too confident. Doing some research, I found that something called a "Markov chain" might help, but I am not familiar with how those work.

Does anyone know how I can tackle this? It is nothing really important, just a thought experiment I was curious about, but it is really bugging me.

2. Apr 28, 2014

### HallsofIvy

One thing you do NOT say is how often this random number is generated. Not knowing long the car moves at a given velocity, you cannot say how far it would go.

3. Apr 28, 2014

### HexNash

It is discrete: each time a number is generated it is a turn, and the velocity is changed and the car is moved forward. For example, given the sequence of generated numbers: 53 04 34 60 23 47, that is 6 turns and the car is moved 1+2+3+0+1+2 = 9 units. What I am trying to figure out is the expected value after 60 turns.

4. Apr 28, 2014

### eigenperson

Let $d_n$ be the expected distance that the car will travel in a race of duration $n$. Let $T$ be the last time the car is stopped (so if there is no crash we'll put $T = 0$). Now we can set up the following recurrence for $d_n$:
$$d_n = \sum_{i=0}^n P(T=i)(d_{i-1} + \Delta(n-i))$$
where $\Delta(m)$ is the mth triangular number, and we assume $d_{-1} = d_0 = 0$. Now, $P(T=i) = (1/60)(59/60)^{n-i}$, so this recurrence lets you easily calculate $d_n$ for any n (using a computer, of course).

The explanation of this is simple: if the car crashes for the last time at time $i$, it traveled an average of $d_{i-1}$ steps in the time between the start of the race and $i$ and travels exactly $\Delta(n-i)$ steps after that time.