Expected travel of random walk in arbitrary game with multiple payouts

Question

As explained here, the average distance or 'travel' of a random walk with $N$ coin tosses approaches: $$\sqrt{\dfrac{2N}{\pi}}$$

What a beautiful result - who would've thought $\pi$ was involved! However, what would be the formula to use for an arbitrary paytable?

For example, a coin toss has the paytable:

• 0.5 : -1
• 0.5 : 1

...so a 50% chance of both winning or losing a point. After 10,000 coin tosses, the travel on average will be $\sqrt{10000\cdot2/{\pi}} \approx 79.788$.

However a dice roll where you need to land a six to win could have the paytable:

• 0.8333.. : -1
• 0.1666.. : 5

After 10,000 dice rolls, the travel on average will be about 178. However, I only know that because I used simulation to brute force the result - I don't know the formula.

More generally, a paytable could have multiple entries where all the probabilities add up to one:

• probability1 : payout1
• probability2 : payout2
• probability3 : payout3
• ...
• ...
• probabilityN : payoutN

Note that the total of the payouts may not necessarily be zero. It could be weighted to produce an unfair game. For example:

• 0.75 : -1
• 0.1 : 0.5
• 0.15 : 4.5

That's an average payout of $-0.025$ with a variance of $3.811875$, and using simulation, I get $\approx 268.8$ 'travel' from 10000 runs. But how would I find this out directly?

In other words, how would you find the average 'travel' of such a generalized paytable without resorting to simulation? As a side question, would this figure also be a better indication of risk for such a 'game' compared to the standard deviation of the paytable as defined here?

Here's the code I used for the simulation: http://pastebin.com/985eDTFh

It's written in C#, but is otherwise very well self-contained. Most of it is a fast random class, but you can use the default Random class if you prefer. Also, if you're not using C#, don't worry too much about converting the convertCSVtoPayoutTable() function as you can hard code the probability and payout arrays yourself if you prefer.

Answer 1

Elaborating on the comments, here is an answer to your question. Basically all the confusion lies in the difference between expected value and expected distance- at least it did for me. For a distribution centred at the origin, this difference is huge, and for large $N$ tends towards:

$$\sqrt{\dfrac{2\sigma^2 N}{\pi}}$$

This is clearly a lot bigger than the expected value, which is $0$. This makes sense, intuitively, if you draw out a normal distribution. Note that because you are adding random independent variables with a well-defined mean and variance it's OK to make the assumption of an approximate normal distribution, by the central limit theorem. The approximation gets better with $N$. Now, values cancel out in this normal distribution, leaving a mean of $0$, but distances don't. See the lines in red in the below image- these are distances- they both contribute positively towards expected distance.

OK, but what if the distribution is shifted? What does this do to the average distance? What it does is it makes it much closer to the average value. The reason is that the further you shift, left or right, the tinier the remainig positive/negative tail becomes. Hence the average distance and the average value tend towards the same thing. See the image below for what I'm talking about. In the calculation for expected value, the red shaded part cancels out its corresponding tail on the other side. In the calculation for expected distance on the other hand, the red shaded part contributes positively towards the total distance. But it's so tiny that the difference is negligible the further the distribution is shifted. This explains the tiny discrepancy between your observed $263$ and the actual mean of $250$. It makes sense: the absolute average distance must be greater than the mean, because there is no "cancelling out" of tails.

To be more formal about the whole thing, let's write some formulas. The expected distance is

$$E(|x|) = \lim_{n\rightarrow\infty}\dfrac{\sum_{i = 1}^n |x_i|}{n}$$

Whereas the expected value is:

$$E(x) = \lim_{n\rightarrow\infty} \dfrac{\sum_{i = 1}^n x_i}{n}$$

Here $x_i$ is just an observation after you run the experiment for the $i^{th}$ time. Also $n$ is the number of experiments. It's different to $N$, the number of steps (dice rolls) per experiment. Now, let Let $U$ be the bag (set with multiplicity) of values $u_i$ in the observed sample set that are positive. And let $V$ be the bag of values $v_i$ that are negative. Then we can also express expected value as follows:

$$E(x) = \lim_{n\rightarrow\infty} \dfrac{\sum_{u_i \in U} |u_i| - \sum_{v_i \in V} |v_i|}{|U| + |V|}$$

Note that $n$ is just the number of experiments/trials and $|U| + |V| = n$. Now, the expected distance is:

$$E(|x|) = \lim_{n\rightarrow\infty} \dfrac{\sum_{u_i \in U} |u_i| + \sum_{v_i \in V} |v_i|}{|U| + |V|}$$

The only difference is a plus sign. Clearly then, as either $U$ or $V$ dominates because of a sliding mean, $E(|x|)$ tends towards $|E(x)|$, with a small error term. The error term will correspond to the leftover (smaller) tail of the distribution on either the positive or negative axis. Without loss of generality, let's say there are more negative than positive values i.e. the positive tail is shorter. Then explicitly, the error term is:

$$E(|x|) - |E(x)| = \lim_{n\rightarrow\infty} \dfrac{2\sum_{u_i \in U} |u_i|}{n}$$

When the mean is $0$, this error term is maximised at:

$$\sqrt{\dfrac{2\sigma^2 N}{\pi}}$$

But as you can see from the shape of the normal curve, it rapidly decreases. This agrees with your observation, with an error term of only around $13$. Of course, I realise that this doesn't answer the question, as I haven't given an explicit formula for the error term! But I believe this answer has enough intuitive value to explain your observed results.