A Few Random Walk Questions

[HP]

Okay, so you've got your standard random walk:

Flip a coin. If heads, move one unit right, if not, one unit left. Start at x=0

The chance you will eventually get to x=1 approaches 1 as the number of additional flips you are willing to take approaches infinity, correct?

And again the chance you will eventually make it to say x=100 (or any other whole number) approaches 1 as the number of flips you are willing to take approaches infinity, correct?

I'm pretty sure the answer is yes and yes so far. How about this though:

You start off at x=1

Flip a coin. If heads, increase value by 10%. If tails, decrease value by 10%. Given you are prepared to flip forever, what are the chances you will make it to x=1.1 or higher? Is it 100% ?

If it is 100%, what if you start at x=1 and use a log-normal distribution (which yields an average change of 0) to figure out where your next step lands you. Will you always make it to a value greater than x=1 eventually ?

[sixhigh]

If I understand you correctly you mean the following: If the coin comes heads the new value (x_(n+1)) will be x_n*1.10, if the coin comes tails the new value will be x_n*0.90.

In this case the probability of reaching any point above the initial value will be less than 100%. That is because the whole process is a supermartingale - i.e. the expected value of x_(n+1) is lower than the ev of x_n

E[x_(n+1) | x_n] = 1/2 * x_n * 1.1 + 1/2 * x_y * 0.9 = 0.99 * x_n < x_n

thus E[x_n] --> 0 (for n --> \infty)

Now there are ways to calculate the exact probability of x_n reaching a certain value at least once, but iirc this is quite difficult.

I don't know what you mean by using a certain distribution to determine x_(n+1). Should the probability of moving up/down be based on the value of x?

And the answer to the first questions is yes - you will reach every value infinitely often in a one-dimensional random walk.

[HP]

thanks for the reply

[ QUOTE ]
1/2 * x_n * 1.1 + 1/2 * x_y * 0.9 = 0.99 * x_n

[/ QUOTE ]
Am I missing something here? why is it 0.99 instead of 1?

[sixhigh]

Whops - that's probably wrong. The entire post.

E[x_n] = 1 for all n,

but still x_n --> 0. (p-almost sure)

Say you walk n steps and k times the coin lands on heads. The value of x_n then will be 1 * 1.1^k * 0.9^(n-k).
For this value to be greater than (say) x_0 = 1 we get the following expression:

1.1^k*0.9^(n-k) > 1

Solving this expression for k (and using Derive) we get

k > n * ln(1/0.9) / ln(1.1/0.9)

or

k > n * 0.525

Now since k has binomial distribution (with the parameter p=1/2) we know by the law of large numbers that it will (p-almost surely) not be in this region for large n.

The EV of x_n being 1 although x_n almost surely approaches 0 follows for nearly the same reasons the St.-Petersburg paradox does.

Now since the random variable approaches zero almost surely it will almost surely never hit a certain value above 0 infinitely often. Thus (i guess) it will hit no value above 0 with probability 1.

[HP]

cool, thanks, makes sense to me

[HP]

I'm still uneasy about this all however

I had the money markets in mind when I made the OP

Let's assume an efficient market (random walk)

And let's simplify stuff and say the interest rates in the USA and Europe will always be the same. If you don't know why this matters don't worry

so, With similar logic to the above you could say that looking at the USD vs the EUR, through a random walk the USA will approach 0

But then the same could be said for the EUR vs the USD

I'm still pondering about what kind of probability density functions we have for the change of USD/EUR after a day

hmm...

[sixhigh]

This is quite easy. Decreasing a value by 10% isn't the inverse of increasing it by 10%.

For example if you increase 100 by 10% you get 110, if you decrease 110 by 10% you get 99.

The inverse to an increase by 10% is decreasing by 1/11. I.e. to increase x by 10% you multiply it by 1.1, the inverse is multiplying by (1.1)^-1.

If you take those values you will get a random walk that will reach every point [..., 0.68, 0.75, 0.83, 0.91, 1, 1.1, 1.21, 1.33, ...] infinitely often.

You might want to google 'geometric random walk' for some more infos.

[HP]

[ QUOTE ]
If you take those values you will get a random walk that will reach every point [..., 0.68, 0.75, 0.83, 0.91, 1, 1.1, 1.21, 1.33, ...] infinitely often.

You might want to google 'geometric random walk' for some more infos.

[/ QUOTE ]

Yes, this was my intuitive guess for perfectly efficient markets (or else it would be weird, as pointed out in my above post)

which leads me to another problem (posted in business forum, and what led to this OP):

[/ QUOTE ]
Okay I had a highly theoretical, probably not practical at all, thought the other day. Feel free to ignore if it's pointless to discuss

Assume:

a perfectly efficient money market
it is possible to borrow and lend cash at the same interest rate, in the US and in Europe
there will always be a minimum amount variance in the USD/EUR
the USD and EUR will always exist

Okay so basically we buy 100 USD worth of EUR today, and put the EUR in the bank earning interest.

We buy back USD once the exchange rate is such that we make ten times as much USD than we would have if we had just put it into a US bank account to begin with

Now, if I've understood random walk theory correctly, if there will always be a minimum amount of variance, and it's always a random walk, the chance the exchange rate will eventually hit our target (so we can make ten times as much) is 100%. It may take a number generations and our decedents may be the only ones profiting, but we don't mind we are nice people

This seems counterintuitive - it's like we are beating the perfectly efficient market. Thoughts?

[/ QUOTE ]

[HP]

for starters, if you don't understand why the difference in interest rates between the USA and Europe matters, don't worry just ignore it and assume they are always the same

[jason1990]

You are measuring one stochastic process in terms of another, which tends to complicate things. It may be clearer if you measure both USD and EUR in terms of some fixed quantity, say the 2000 USD. Let n denote the year 2000 + n, and let U_n denote the value of the USD at time n, measured in 2000 USDs. In particular, U_0 = 1. Suppose that

U_n = (1 + X_n)U_{n-1},

where {X_n} is an iid sequence with mean r. For simplicity, assume X_n = r + 0.1 or X_n = r - 0.1 with equal probability. Note that we can write

U_n = U_0*e^{S_n},

where

S_n = \sum_{j=1}^n \log(1 + X_j).

The long term behavior of U_n is determined by the long term behavior of S_n. Since S_n is a random walk, its long term behavior is determined by whether E[\log(1 + X_j)] is positive, negative, or 0.

Now let V_n denote the value of the EUR at time n in 2000 USDs. Suppose that

V_n = (1 + Y_n)V_{n-1},

where the sequence {Y_n} is independent of and has the same distribution as {X_n}. We can write

V_n = V_0*e^{T_n},

where

T_n = \sum_{j=1}^n \log(1 + Y_j).

You are interested in the exchange rates W_n = U_n/V_n and M_n = V_n/U_n. Note that

W_n = W_0*e^{S_n - T_n}.

Since S_n - T_n is a random walk with mean 0, W_n will not converge to zero. Similarly, neither will M_n. Interestingly, we can write

W_n = [(1 + X_n)/(1 + Y_n)]W_{n-1}
= (1 + Z_n)W_{n-1},

where

Z_n = (X_n - Y_n)/(1 + Y_n).

The mean growth rate of W_n is E[Z_n], and you can check for yourself that E[Z_n] is positive. Similarly, the mean growth rate of M_n is also positive. In other words,

E[(1 + X_n)/(1 + Y_n)] and
E[(1 + Y_n)/(1 + X_n)]

are both greater than 1. (This is surprising only if you forget that the expected value of a reciprocal is not the reciprocal of the expected value.)

[ QUOTE ]
Okay so basically we buy 100 USD worth of EUR today, and put the EUR in the bank earning interest.

We buy back USD once the exchange rate is such that we make ten times as much USD than we would have if we had just put it into a US bank account to begin with
...
This seems counterintuitive - it's like we are beating the perfectly efficient market. Thoughts?

[/ QUOTE ]
For simplicity, assume that interest rates are 0. At the time you make your trade, the USD is worth X 2000 USDs and the EUR is worth 100X 2000 USDs. If you have Y EUR, then you have something worth 100XY 2000 USDs. If you convert, then you will have 100Y USDs, which is again something that is worth 100XY 2000 USDs. Whether you convert back to USD or keep it in EUR, you have the same thing. Trading back and forth in this setting corresponds to sometimes following the random walk S_n, then sometimes following T_n, then back to S_n for a while, and so on. The result is just another random walk.