$N$-step one dimensional random walk that never returns to the origin. I am looking for how to calculate the probability that an $N$-step one-dimensional random walk (on a lattice) never returns to its origin.
I found a reference that found that the probability of never returning to the origin is $|p-q|$, but this applies only to the case that $N\to \infty$; I thought that the probability that I am looking for in this problem is:
$$1-\sum_{k=0}^n \frac{{ 2k \choose k}}{2k-1} (pq)^k$$
where $0<p=1-q<1$.
Obviously if the total number of steps $N$ is odd then with probability 1 we never return to the origin after $N$ steps.
So how to compute this probability for $N$ even?
Thanks.
N.B
$$N=2n$$
 A: You actually more or less have the answer to the question you asked, but let's go through it. Let $S_n=\sum_{k=1}^nX_k$ be a random walk started at the origin such that
$$p=P(X_k=1)=1-P(X_k=-1)=1-q$$
Let $\tau$ be the first return time. Observe that
$$P(\tau=2n\,|\,S_{2n}=0)=qP(A_n^+\,|\,S_{2n-1}=1)+pP(A_n^-\,|\,S_{2n-1}=-1)$$
where $A_n^+=\{S_k>0\text{ for }k=1,\ldots,2n-1\}$ and $A_n^-=\{S_k<0\text{ for }k=1,\ldots,2n-1\}$. By the Ballot theorem we have
$$P(A_n^+\,|\,S_{2n-1}=1)=P(A_n^-\,|\,S_{2n-1}=-1)=\frac1{2n-1},$$
so
$$P(\tau=2n\,|\,S_{2n}=0)=q\cdot\frac1{2n-1}+p\cdot\frac1{2n-1}=\frac1{2n-1}.$$
It follows that
$$P(\tau\le N)=\sum_{n=0}^{\lfloor\frac{N}2\rfloor}\frac1{2n-1}P(S_{2n}=0)=\sum_{n=0}^{\lfloor\frac{N}2\rfloor}\frac1{2n-1}{{2n}\choose n}(pq)^n$$
where the second equality is a simple counting argument. In particular, the probability that the walker does not return in the first $N$ steps is
$$P(\tau>N)=1-\sum_{n=0}^{\lfloor\frac{N}2\rfloor}\frac1{2n-1}{{2n}\choose n}(pq)^n$$
which is more or less what you wrote, modulo unnecessarily assuming $N$ was even. (Of course, the probability that the walker does not return on the $N^\text{th}$ step is $1-\frac1{N-1}{N\choose {N/2}}(pq)^{N/2}$ if $N$ is even and $1$ otherwise.) I doubt you're going to get a much more explicity result than this, however if you let $N\to\infty$ then we indeed recover the result you stated that
$$P(\tau<\infty)=1-|p-q|,$$
that is, that the probability that the walker never returns is $|p-q|$.
A: If the question is just for the N-th step, where N is even ($N=2k$), then it is simply 
$$1-C(N, k)p^kq^k$$
If the question is that is never returns within the first N step, then the Reflection Principle can be used to solve the problem. 
