I have series of binomial variables $\xi_1, \xi_2, \dots, \xi_n$ which form a random walk. Variables can be $\pm 1$ with probability $\frac{1}{2}$ and we define $S_n = \sum_{i=1}^n \xi_i$. We start our walk from 0.
My question is how to find the number of random paths such that $\exists k: S_k \ge N$ for some integer N. In other words, I need to find the number of paths which cross the horisontal line $y = N$.
I even don't know how to start. Any useful hints are welcome.
For any fixed $N \in \mathbb{N}$, there is at least one path that goes straight $0 \to N$ in $N$ steps, and it has probability $2^{-N}$, hence for any fixed $N$, such $k$ exists with probability 1.
UPDATE
Hint for the updated question. Since your number of steps is bound to be $n$, what you have to do is look at the $0 \to N$ path and insert the number of $+1$ and $-1$ there so that there is at least as many $+1$ as $-1$, and then find the number of places in the sequence into which they can be inserted (to do the last one, consider a sequence of length $n$, of which you pick $N$ to be your up points, and distribute the rest)