Proof that you cannot beat a random walk

There is much speculation to what degree financial series are random (and what kind of randomness prevails).

Is there a mathematical proof that whatever trading strategy you use you cannot beat a random walk (that is the expected value will always be 0 assuming no drift)?

(I found this blog post where the author used the so called "75% rule" to purportedly beat a random walk but I think he got the distinction between prices and returns wrong. This method would only work if you had a range of allowed prices (e.g. a mean reverting series). See e.g. here for a discussion.)

• You are not going to be able to create a "mathematical proof" without mathematical definitions of the processes followed by the financial series. Obviously an OU process in price space would be exploitable. You need to exclude that from your process definitions to have a hope of generating a proof. – Brian B Aug 18 '11 at 13:34
• @Brian: Do you know of any literature that does exactly that? I mean it seems intuitively the case but we all know intuition is not always the best judge when it comes to math... – vonjd Aug 18 '11 at 16:31
• is Bootvis's proof removed? is it possible to see it? – user12348 May 23 '14 at 10:08

I can help you beat random walk 'in the way you want', i.e. the expected value $E[\$]$will always be positive even assuming no drift. However, I have to warn people that$E[\$] > 0$ is NOT really an adequate condition for 'beating' in reality (at least to myself).

Let's define some mathematical notations for derivation, and rephrase (simplify) vonjd's question without losing generality. Assume a trader plays a fair game, and his surplus $X(0), X(1), X(2), ... X(t)$ is a martingale.

Q: Can the trader find a stopping time $s$ such that $E[X($s$)] > X(0)$?

• A proof supporting Bootvis' answer, for comparison, consider a normal trading strategy that bets evenly. Then,

\begin{align*}E[X(s)] &= E[ E[X(s)|X(s-1), X(s-2),..., X(0)] ] \\ &= E[X(s-1)] = E[X(s-2)] = ... = E[X(0)] = X(0).\end{align*}

• Now, consider a 'double-betting' strategy. We keep doubling your losing trade until first win. Let's set the initial surplus, $X(0) = 0$ for simplicity.

Accordingly, $X(k) = X(k-1) + G(k)$, where $G(k)=\pm 2^{k}$ with probability $1/2$. Note that we get the power $(k)$ of $2$ in $G(k)$ because of 'double-betting'. Our market is still random walk.

This strategy is designed stop at a time $s = min{k}$ s.t. $G(k) > 0$ (Note that $Prob{s=infinity} = 0$)

Compute $E[X(s)]$ by conditioning on s:

\begin{align*} E[X(s)] &= E[E[X(s)|s]] = \sum_{k=1}^{\infty} E[X(s)|s=k] * Prob{s=k} \\ &= \sum_{k=1}^{...} (-1-2-4-8...-2^{(k-1)} + 2^{k}) * (1/2)^{k} \\ &= \sum_{k=1}^{...} 1 * (1/2)^k = 1 > 0 = X(0)\end{align*}

Conclusion

A trader can make $E[X(s)]>0$ for random walk using the double-betting strategy. We proved that you can beat random walk in your definition of 'beating', i.e. expected value > 0.

This is actually a simplified proof supporting Akshay's answer. Whatever it's called: volatility pumping, Kelly strategy, optimal growth portfolio, and etc. These ideas simply ask one more question: why double? Is there an optimal betting ratio because of ... (various reasons and assumptions)?

• WARNING: Yes, the expected value is indeed positive, and it might be an adequate proof for people who believe winning strategy is all about searching for $E[X(s)]>0$. Unfortunately, this is NOT adequate in reality, at least to myself. You have been warned.

• A $E[X(s)]>0$ strategy is guaranteed to make you real fortune if and only if we have 'unlimited amount of capital'. For details (long story), see wiki: Martingale betting system.

• You might ask what should we do if we only have limited capital? The Kelly criteria actually kind of offers the effect of the double-betting strategy for limited capital. For example, if you have a very weak trading signal (close to random walk in which there is no signal at all), the Kelly criteria will recommend you to bet something like \$1 (initially) for \$1M capital, and increase/decrease your position by certain % when you lose/win. Yeah, \$1M indeed looks like unlimited capital to \$1.

• (From comment) There is no contradiction to the common sense that 'pure independence = zero E[PnL]'. $E[] > 0$ in my example and vonjd'd Parrondo's paradox are indeed exploited from sort of dependency. While the Parrondo's paradox exploits the dependency between two losing games, mine is exploiting the dependency from my losing trades (which is less obvious). But warn again: This is at the cost of ruin risk! Though Kelly and vol-pump strategies eliminate ruin risk, they still suffer from trending risk.

• Thank you - how does this square with "constant rebalancing"? Is this the same as "volatility pumping"? Could you show a more direct connection between your first proof and the other concepts that seem to use some kind of "Parrondo's paradox"? Thank you again. – vonjd Aug 22 '11 at 7:43
• Thank you for accepting the answer, vonjd. I also like the analogy you found in Parrondo paradox. Though not sure how to answer your questions? here is my attempt: First, all mentioned strategies propose to add(cut) risk exposure when lose(win). For example, if you long stock and you lose/gain 1 dollar when market moves, kelly or vol-pump will require you buy/sell in order to maintain constant betting ratio. This makes volatility your friend (pumping). But trend is your enemy! In this case, is random walk more like your enemy or your friend? – 楊祝昇 Aug 24 '11 at 8:29
• Second, there is no contradiction to the common sense that 'pure independence = zero E[PnL]'. E[] > 0 in my example and your Parrondo's paradox is indeed exploited from sort of dependency. While Parrondo exploits the dependency between two losing games, mine is exploiting the dependency on my losing trades (which is less obvious). But (warn again), this is at cost of ruin risk! Note that Kelly/Vol-pump eliminate ruin risk, but still suffer tail risk. Conclusion? Find dependency had better, create it if you must. – 楊祝昇 Aug 24 '11 at 9:13
• there is at least one hole in this answer, how do you know that financial valuations are really dependent on the past, not on the last stage (Markov assumption) or perhaps something else? I agree that you can beat RW with arbitrary assumptions but are you sure about your premise here about the historical dependency? – hhh Dec 8 '11 at 9:09
• ＠hhh, Nobody here tried to beat real financial data. Vonjd was asking whether we can/can't beat the 'random walk', not the 'real world', in the way he wants. We are indeed aware of the difference between RW and real world, but thanks for reminding us. :) – 楊祝昇 Feb 18 '12 at 4:37

If the price of every asset follows an independent random walk without drift then every position has an expected return of zero. So, in expectation, there is no combination of positions that has an expectation different from zero.

• Thank you. I think this is an important part of a proof but not the full story. E.g. a mean reverting process can also have an expected value of 0, yet you can exploit the underlying mathematical structure (see the paper above). A random walk also has some mathematical structure, the problem is to show that there is no way to exploit this. – vonjd Aug 18 '11 at 10:38
• @vonjd, I think Bootvis's proof already handles that objection. Presumably, a mean-reverting process has an increased chance of returning to the starting point (to 0), compared to a rnadom walk. Thus a mean-reverting process differs from a random walk in the following respect: fix a point in time where the value is positive; then the conditional expectation of the future returns for a random walk is zero, but negative for a mean-reverting process. Bootvis's proof relies upon the fact that, for a random walk, conditional expectation is always 0. – D.W. Aug 18 '11 at 19:58
• @D.W.: Good point: Both expectation and conditional expectation are 0 with a random walk. Thank you. – vonjd Aug 18 '11 at 20:12
• @Bootvis - this argument does not take into account dynamic replicability of a position. I can have a risk-free bond and a stock - both having iid returns/price processes. I can create an option to exploit the volatility characteristics of the processes. See my answer below. – Akshay Aug 18 '11 at 21:06
• @akshay I think vonjd's original question was only regarding the trading of a single asset. – Tal Fishman Aug 19 '11 at 13:41

That post has been up since March. Either he hasn't figured it out, or he's trying to get people to click through to the book.

In the following statement, isn't he implying that "rw" is a return (as in....random walk)?

rw <- rnorm(100)


In the following statements, isn't he calling a "trade" the DIFFERENCE IN RETURNS? Isn't that meaningless?

if(rw[i] < m) trade[i] <- (rw[i+1]-rw[i])
if(rw[i] > m) trade[i] <- (rw[i]-rw[i+1])


From there on, isn't the whole thing a waste of time? Likewise, when I opened that .pdf file, the first thing I saw was Sornette's name. There's no need to read further.

As far as "proofs" go, how are you going to agree on the properties of the market? If you can't, then the idea of a "proof" goes poof.

• I am not so much trying to find a 1-to-1 correspondence to the statistical properties of the market. It is more a purely intellectual endavour to find out what underlying structure in a random process is exploitable (e.g. mean reverting random walk) and what is not. There is always some structure but it won't be always exploitable. I started with the well known (i.i.d.) random walk, but this can be broadened later on. – vonjd Aug 18 '11 at 16:11
• ...and to add to your point: What is wrong with Sornette? At least he is bringing some new ideas into the field. And in this article he shows that you cannot exploit the 75%-rule. – vonjd Aug 18 '11 at 16:40
• @vonjd, Actually, it is a 1-to-1 property issue. Just try to get two people to agree on the properties. Also, it is one thing to explain what happened in the market, it is totally different to predict the same thing. And, we can't even explain it. The "exploited issues" are typically something different. If I'm a market maker, I have a lot of exploitable advantages over my prey. If I'm a hedge fund manager, I really can't lose. 2 and 20 means I'll get at least 2% of your money. As far as Sornette goes, just read 4 or 5 of his articles (or his book). You'll understand. – bill_080 Aug 18 '11 at 17:30
• @vonjd, Just a few of many examples of Sornette's "work". safehaven.com/author/37/didier-sornette – bill_080 Aug 18 '11 at 17:42

Here is a more or less formal proof of the fact that "the system can't be beaten". The argument works whenever the underlying process is a martingale. In particular, it is valid for a random walk without drift.

Let $S=\{S_n\}$ be a discrete-time martingale which represents a series of games played at times $n=1,2,...$. Assume that $S_0=0$ (no game at time $n=0$). Let $\mathcal A=\{\mathcal A_n\}$ be a filtration of $\sigma$-algebras $\mathcal A_0\subset \mathcal A_1\subset\ ...$, such that the process $S$ is adapted with respect to $\mathcal A$, i.e. $S_n$ is $\mathcal A_n$-measurable for each $n$. Intuitively speaking, this implies that $\mathcal A_n$ contains all information about the outcomes of the game after the first $n$ rounds, and the value of $S_n$ is known to the player at time $n$.

We may think of the difference $S_n-S_{n-1}$ as the net winnings per unit stake in game $n$. Since $S$ is a martingale, $$\mathbb E(S_n-S_{n-1}|\mathcal A_{n-1})=0,\qquad n=1,2,...$$ Now let $C=\{C_n\}$ be a previsible bounded process, i.e. $C_n$ is $\mathcal A_{n-1}$-measurable and $$\sup|C_n(\omega)|\leq K$$ for each $n=1,2,...$ and some constant $K$. $C_n$ represents the player's stake in game $n$. Obviously, the value of $C_n$ must be determined based on the history up to time $n-1$ (the player has no information about the value of $S_n$ before the n-th round is played). Thus the total winnings up to time $n$ are $$X_0=0,\qquad X_n=\sum\limits_{k=1}^{n}C_k(S_k-S_{k-1}),\quad n\geq1.$$ Since the process $C$ is previsible and bounded, using the standard properties of the conditional mean, we have that
$$\mathbb E(X_n-X_{n-1}|\mathcal A_{n-1})=\mathbb E(C_n(S_n-S_{n-1})|\mathcal A_{n-1})= C_n\mathbb E(S_n-S_{n-1}|\mathcal A_{n-1})=0$$ for each $n=1,2,...$. In other words, $X=\{X_n\}$ is an adapted integrable process such that $$\mathbb E(X_n|\mathcal A_{n-1})=X_{n-1}$$ for all $n\geq 1$, i.e. it's a martingale itself. It immediately follows that $\mathbb E(X_n|\mathcal A_{m})=X_m$ when $m<n$ and that the unconditional mean $\mathbb E(X_n)=\mathbb E(X_0)=0$ does not depend on $n$.

"Probability with Martingales" by Williams is a good and fairly standard reference for this stuff.

• Thank you. What I learned by reading the other answers is that a random walk CAN in fact be beaten. You can call the mechanisms Shannon's demon, volatility pumping, growth-optimal portfolio or Kelly criterion. How would one resolve this contradiction?!? Thank you again. – vonjd Aug 23 '11 at 15:21

I think you mean to say any self-financing trading strategy would give you zero returns - which it will - the principle of no-arbitrage ensures that.

For example, say you have a stock whose returns follow a random walk pattern with expected return equal to zero. The only way this can happen is (a) the stock stays fixed at a value K or (b) the stock has an equal probability of being +x% or -x% tomorrow or (c) the stock can go +x% with probability p1 and -y% with probability p2 with p1*x + p2*y = 0.

Now, for all of these cases, I can have an options-based long straddle centered around K. With non-zero volatility (stochastic as well as determinate), it is far more likely that my straddle will earn me a positive return than not. The down-side is - other traders also realize this fact and so I can't have that straddle for free (and thus earning a clean expected non-zero return).

So it is not the iid process by itself which is non-exploitable (sure it is, as in the strategy above if arbitrage exists or, even simpler, in the case of a "buy-low, sell-high" strategy which can earn a positive return from an iid). The "mathematical structure"which can be exploited is known as the process volatility. It is no-arbitrage which disallows an iid process from being exploited for returns in excess of those commensurate with its volatility - not any property of the process itself.

• I think I don't get your point in its entirety. So you are basically saying that a random walk per se can be beaten when you assume that the behaviour of other traders doesn't have an influence on it? And are you saying that you can actually beat a random walk by volatility pumping (related: quant.stackexchange.com/questions/352/…) Could you please give references for your points or expand on them - Thank you! – vonjd Aug 19 '11 at 7:58
• See the follwing link for some simulations on volatility pumping: financialwebring.org/gummy-stuff/volatility-pumping.htm - so it really seems there is a way to beat a random walk after all... – vonjd Aug 19 '11 at 8:47