Can the No Win Random Walk Conjecture Be Proven Using Martingales?

[junglebeast]

A random walk can be defined by the following recurrence relation,

[tex]
X_{t+1} = X_t + \Delta X
[/tex]

where [tex] \Delta X \sim \mathcal{N}(0, \sigma^2)[/tex].

At any time [tex]t1 \geq 0[/tex] a strategist may enter, and at any time [tex]t2 > t1[/tex] a strategist may exit. The resulting profit p is given by:

[tex]
p(t1,t2) = X_{t2} - X_{t1}.
[/tex]

Because each recursive step is IID, a sequence of n steps may equivalently be written as

[tex]
X_{t+n} = X_t + Y
[/tex]

where [tex] Y \sim \mathcal{N}(0, n \sigma^2)[/tex].

Thus, the expected value for profit if you buy at any [tex]t1[/tex] and sell at [tex]t2+n[/tex] (for any n) is zero,

[tex]
E(p(t1, t2)) = E(Y + X_t - X_t) = E(Y) = 0
[/tex]

A strategy is a method for choosing t1 and t2 without future knowledge. For example, a strategy could be:

t1 = 0
if [tex]t > 0[/tex] and: [tex]X_t > X_{t1} + 50[/tex] or [tex]X_t < X_{t1} - 100[/tex] then [tex]t2 = t[/tex]

I do not know how to calculate the expected value of that strategy but I think it is zero.

Conjecture:

There is no strategy for entering and exiting that has a non-zero expected value for profit.

Now this seems like an intuitively obvious statement -- but can it be proven mathematically?

 

[gel]

I do not know how to calculate the expected value of that strategy but I think it is zero.

That's the http://en.wikipedia.org/wiki/Optional_stopping_theorem" .

Now this seems like an intuitively obvious statement -- but can it be proven mathematically?

Yes, by the optional stopping theorem it is true whenever [itex]E[t_2]<\infty[/itex] and t1, t2 are stopping times. However, if t1 = 0 and t2 is the first time at which X(t2)-X(t1)=n (any integer n>0) then you have E[X(t2)-X(t1)]=n>0. In this case, t2 does not have finite expectation.

 

[junglebeast]

gel,

I was not aware of the concept of a "martingale" or the "optional stopping theorem," which clearly pertain to a very similar class of problems, so thank you for bringing this to my attention.

After looking it up, the optional stopping theory says that the expected value of a martingale (eg, of a random walk) at some stopping time is equal to its last recorded value. Note that I already discovered this when I showed that [tex]E( X_{t+n} ) = X_t[/tex].

Clearly, if the current time is t and one chooses any future time's t1 > t and t2 > t1, then

[tex]
E( X_{t2} - X_{t1} ) = E(X_{t2}) - E(X_{t1}) = t1 - t1 = 0
[/tex]

However, this does not alone answer the question...the expected value of profit for the strategy I provided is equal to:

[tex]
E(...) = 50*P - 100*(1-P)
[/tex]

where P is the probability that the random walk reaches t1+50 BEFORE it reaches t1-100. How do you calculate P?

Also, that is just one strategy...and more is needed to extend this to all possible strategies

 

[gel]

I'm not sure what the issue is. The optional stopping theorem does answer your question. Maybe you missed the definition of stopping time? They are random times which can be chosen 'without future knowledge', as you mentioned in your first post.

It follows from the theorem that the expected profit of your strategy is zero, and this fact can be used to calculate P. [itex] 50 p - 100 (1-p)=0[/itex] and, therefore, p = 2/3.

 

[gel]

Also, martingales are an important concept to understand if you want to consider such questions. The term 'martingale' originally referred to gambling strategies, and the mathematical term was introduced to study and prove that such such strategies cannot produce a positive profit on average. It has since developed into an important part of probability theory and the foundation of much of the field of stochastic processes.

The book I initially read when learning this topic was https://www.amazon.com/gp/product/0521406056/?tag=pfamazon01-20, which is a fairly easy introduction to the subject and only considers discrete-time processes (continuous-time is much more complicated, but also interesting). Would probably help to have an understanding of measure theory first though.