random walk without replacement probabalistic bounds

[petertw]

Hi, I am trying to prove a seemingly simple property of random walks created by selecting steps without replacement.

I'm considering one-dimensional walks formed by selecting 2n steps without replacement out of an urn containing n, (+1) steps and n, (-1) steps. All walks start and end at the origin; I'm interested in how far they stray during the selection process. The position at any time is the cumulative sum of the step values.

It can be shown that such walks will remain close to the origin with high probability. Specifically, the chance of being past +- c*Sqrt(n) is approx. 2*e^(-4c^2).

I would like to show that a similar walk, created by selecting (r+1)*n steps without replacement from an urn containing n, (+1) steps and r*n, (-1/r) steps also remains "close" to the origin with high probability. Intuitively, each down-step in the first walk is just broken into r pieces sized 1/r.

Could anyone suggest an approach?

The method used to prove bounds on the first walk is to (1) show all walks equally likely, then (2) count the number of unique walks that exit the c*Sqrt(n) bound, using a technique by William Feller. Feller's technique builds a 1-1 correspondence between walks that go out of bounds with the number of <paths> from 0,0 to 2n,2*bound, by "reflecting" the rest of a walk once it leaves the bound for the first time. Unfortunately this technique does not apply to the second walk since the step sizes are asymmetric.

Any guidance would be greatly appreciated!

Thanks,
Peter

[bimmerforce]

this seems like a fun problem. anyone ?

[webcrawler07]

Hi,
You could use the following martingale method to get some bounds.

Consider a finite population (i.e. the steps in the urn) of real numbers a_1,...a_n such that a_1 + ... + a_n = 0.
Let X_1,...,X_n be a random ordering of these numbers (i.e. the process representing sampling without replacement).
Let S_k = X_1 + ... + X_k.
Then the process M_k = S_k / (n - k) is a martingale (for k=0,...,n-1).

Denote Y_k = max(|S_1|,|S_2|,...,|S_k|).
and Z_k = max(|M_1|,|M_2|,...,|M_k|).

By Doob's maximal inequality we have: Pr(Z_k >= a) <= (1 / a^2) * E[(M_k)^2].
Using symmetry we have: Pr(Y_n >= a) <= 2 Pr(Y_[n/2] >= a) <= 2 Pr(Z_[n/2] >= a/n).
And since E[(M_[n/2])^2] = (4 / n^2) * E[(S_[n/2])^2],
we have that: Pr(Y_n >= a) <= (8 / a^2) * E[(S_[n/2])^2].

It can be shown (for instance Hoeffding - Probability Inequalities for Sums of Bounded Random Variables) that for all k, E[(S_k)^2] <= ((a_1)^2 + ... + (a_n)^2) / n.

Putting this together we get: Pr(Y_n >= a) <= (8 / a^2) * ((a_1)^2 + ... + (a_n)^2) / n.
Or: Pr(max(|S_1|,|S_2|,...,|S_n|) >= a * sqrt(n)) <= (8 / a^2) * ((a_1)^2 + ... + (a_n)^2) / n^2.

In our case, we have n values of a_k which are 1, and r*n which are -1/r.
So (a_1)^2 + ... + (a_n)^2 <= n + rn/r^2 = n(1+1/r).
And therefore: Pr(max(|S_1|,|S_2|,...,|S_n|) >= a * sqrt(n)) <= C / a^2.


Hope this helps,
Yinon