# Comparing hitting probabilities for two different random walks

Let $p$ be a probability in $]0,1[$, and let $(X^p_i)_{i \geq 1}$ be a i.i.d. family of variables with law $P(X=1)=p, P(X=-\frac{p}{1-p})=1-p$ (so that $E(X)=0$). Set $S^p_n=\sum_{k=1}^{n} X^p_k$ for $n\geq 1$, let $e(p,n)$ denote the probability that at least one of $S^p_1,S^p_2, \ldots ,S^p_n$ is positive (which means that the random walk reaches a positive value at least once during the first $n$ steps ). It is well known that for a fixed $p$, $e(p,n) \to 1$ when $n\to +\infty$.

Let $p\neq q$ be two probabilities. For large enough $n$, shall we have $e(n,p) \lt e(n,q)$ or $e(n,p) \gt e(n,q)$ ?

-
Are you comparing $p=0.01$ with $q=2/3$, or are you mainly interested in the case that both probabilities are on the same side of $1/2$? – Douglas Zare Aug 16 '11 at 1:32
@Douglas : I'm mainly interested in the case where both $p$ and $q$ are $<\frac{1}{2}$ (and $p$ and $q$ represent different gambling strategies). – Ewan Delanoy Aug 16 '11 at 5:12
If you restrict to the case where $1/p$ and $1/q$ are integers, then the analysis is nicer. Instead of saying some $S_i^p > 0$, the condition is that some $S_i^p >= 1$. Then $1$ has different sizes after you rescale by the standard deviations of the walks. – Douglas Zare Aug 17 '11 at 11:08
If $p$ and $q$ are both rational, the random walk is on $\frac{1}{n}.{\mathbb Z}$ for some $n$. – Ewan Delanoy Aug 17 '11 at 15:53

For the first question: yes, suitably scaled, the sequence $S^p_n$ tend to Brownian motion, which is positive infinitely often with probability 1. More precisely, for any fixed $p$, $e(n,p)$ will be asymptotically roughly $1-C_p n^{-\frac12}$.
As for the second question: it really depends on the range of $p$, $q$ and $n$. For fixed $n$ it is not monotone in $p$: for example, when $p$ is close to 1 we have $e(n,p)=1-p$, so it looks like it's decreasing, but when $p\approx \frac12$ we have a jump in $e(2,p)$ from around $\frac14$ to around $\frac12$.
The thing is that you have two contributing factors here: the probability of crossing 0 in the first few steps (how few depends on $p$) which is mostly a combinatorial question with incontinuity points, and the longer range behavior which is determined by the constant $C_p$ above. I guess that if you started the random walk at some distance from 0, you'd get mostly the latter factor.
The Central Limit Theorem tells us that the distribution of ${S_n}^p$ converges to $N(0,1)$. In what sense can it be said that tends to Brownian motion? Where does the $C_p$ constant come from? – Ewan Delanoy Aug 16 '11 at 5:09
I'm talking about $S^p_n$ as a sequence ($p$ fixed,$n$ goes from $1$ to $N$). When you rescale it you get a Wiener Process (en.wikipedia.org/wiki/Random_walk#Relation_to_Wiener_process). The constant comes from the variance of a single step of the random walk. – Ori Gurel-Gurevich Aug 16 '11 at 22:45