show/hide this revision's text 6 added 319 characters in body; added 4 characters in body

Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the value of

$$\mathcal{P}(\alpha) := \mathbb{P}\left(\exists \ n \in \mathbb{N}: S_n > \alpha n\right)$$

In other words, I am interested in the probability that a random walk $(S_n)_{n=1}^{\infty}$ crosses the straight line through the origin with slope $\alpha$.

Since the standard random walk is recurrent, it follows that $\mathcal{P}(\alpha) = 1$ for $\alpha \leq 0$, while obviously $\mathcal{P}(\alpha) = 0$ for $\alpha \geq 1$. Hence the non-trivial part and the part I am interested in is the region $\alpha \in (0,1)$. For this region we know that $\mathbb{P}(S_1 > \alpha) = \frac{1}{2}$, hence $\mathcal{P}(\alpha) \geq \frac{1}{2}$, but finding an exact value seems difficult.

Note: One way to explicitly calculate $\mathcal{P}(0)$ is by

$$\mathcal{P}(0) = \sum_{n=1}^{\infty} \frac{C_n}{2^{2n-1}} = 1$$

where $C_n$ is the $n$-th Catalan number, as was pointed out on e.g. http://oeis.org/A000108 by Geoffrey Critzer. For general $\alpha$ however such a summation does not seem to give a nice expression, since the coefficients are uglier and the exponents of $2$ depend on $\alpha$ (for $\alpha = 0$ one gets exponents $2n - 1$, but for irrational $\alpha$ this exponent becomes something ugly). But finding a closed form for these coefficients for general $\alpha$ might also help solve this problem.

Edit: As it may be too much to ask for a nice formula for $\mathcal{P}(\alpha)$, I would also be very happy if someone could provide (good) bounds on or approximations of the value of $\mathcal{P}(\alpha)$. For example: Does $\mathcal{P}(\alpha)$ decrease linearly in $\alpha$? Any insight is very much appreciated!
show/hide this revision's text 5 edited body; edited body

Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. I would like to know the value of

$$\mathcal{P}(\alpha) := \mathbb{P}\left(\exists \ n \in \mathbb{N}: S_n > \alpha n\right)$$

In other words, I am interested in the probability that a random walk $(S_n)_{n=1}^{\infty}$ crosses the straight line through the origin with slope $\alpha$.

Since the standard random walk is recurrent, it follows that $\mathcal{P}(\alpha) = 1$ for $\alpha \leq 0$, while obviously $\mathcal{P}(\alpha) = 0$ for $\alpha \geq 1$. Hence the non-trivial part and the part I am interested in is the region $\alpha \in (0,1)$. For this region we know that $\mathbb{P}(S_1 > \alpha) = \frac{1}{2}$, hence $\mathcal{P}(\alpha) \geq \frac{1}{2}$, but finding an exact value seems difficult.

Note: One way to explicitly calculate $\mathcal{P}(0)$ is by

$$\mathcal{P}(0) = \sum_{n=1}^{\infty} \frac{C_n}{2^{2k-1}} frac{C_n}{2^{2n-1}} = 1$$

where $C_n$ is the $n$-th Catalan number, as was pointed out on e.g. http://oeis.org/A000108 by Geoffrey Critzer. For general $\alpha$ however such a summation does not seem to give a nice expression, since the coefficients are uglier and the exponents of $2$ depend on $\alpha$ (for $\alpha = 0$ one gets exponents $2k 2n - 1$, but for irrational $\alpha$ this exponent becomes something ugly). But finding a closed form for these coefficients for general $\alpha$ might also help solve this problem.
show/hide this revision's text 4 deleted 211 characters in body; edited tags

Let $(S_n)_{n=1}^{\infty}$ be a standard random walk with $S_n = \sum_{i=1}^n X_i$ and $\mathbb{P}(X_i = \pm 1) = \frac{1}{2}$. Let $\alpha \in \mathbb{R}$ be some constant. My question is: What is I would like to know the value of

$\mathcal{P}(\alpha) $\mathcal{P}(\alpha) := \mathbb{P}\left(\exists \ n \in \mathbb{N}: S_n > \alpha n\right)$? n\right)$$

In other words, what is I am interested in the probability that a random walk $(S_n)_{n=1}^{\infty}$ crosses the straight line through the origin with slope $\alpha$?\alpha$.

Since the standard random walk is recurrent, it follows that $\mathcal{P}(\alpha) = 1$ for $\alpha \leq 0$, while obviously $\mathcal{P}(\alpha) = 0$ for $\alpha \geq 1$. The Hence the non-trivial part and the part I am interested in is the region $\alpha \in (0,1)$.

Note For this region we know that one $\mathbb{P}(S_1 > \alpha) = \frac{1}{2}$, hence $\mathcal{P}(\alpha) \geq \frac{1}{2}$, but finding an exact value seems difficult.

Note: One way to explicitly calculate $\mathcal{P}(0)$ is by

$\mathcal{P}(0) $\mathcal{P}(0) = \sum_{k=1}^{\infty} c_{k-1} sum_{n=1}^{\infty} \cdot 2^{-2k+1} frac{C_n}{2^{2k-1}} = 1$ 1$$

where $c_k$ C_n$ is the k-th $n$-th Catalan number, as was pointed out on e.g. http://oeis.org/A000108:

Sum{k=1...Infinity,c(k-1)/2^(2k-1)}=1. The k-th term in the summation is the probability that a random walk on the integers (begining at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. [From by Geoffrey Critzer(critzer.geoffrey(AT)usd443.org), Sep 12 2009]. For general $\alpha$ however such a summation does not seem to give a nice expression, since the coefficients are uglier and the exponents of $c_k$ seem to be ugly2$ depend on $\alpha$ (for $\alpha = 0$ one gets exponents $2k - 1$, but for irrational $\alpha$ this exponent becomes something ugly). But finding a closed form for these coefficients for general $\alpha$ may might also help solve this problem.

Edit: The formulation of the question and the title were unfortunate and conflicting, and since it seems more natural to talk about the probability of crossing the line, I updated the definition of $\mathcal{P}(\alpha)$ to represent the probability of ever crossing the line.
show/hide this revision's text 3 deleted 8 characters in body
show/hide this revision's text 2 added 267 characters in body; deleted 1 characters in body
show/hide this revision's text 1