Non-symmetric random walk on $\mathbb{Z}^2$

Question

a random walker, walks on a lattice with non-negative coordinates. In each step, if he is in a positive coordinate, say $(a,b)$ where $a,b>0$ he will go to $(a-1,b)$ or $(a,b-1)$ with same probability ($p=\frac12$) and whenever he reaches to $x$ or $y$ axes he will stop. Assume that this random walker starts walking from the point $(k,k)$: What is the probability that he reaches to any of axes? What is the expected value of number of steps before stopping? And what is the expected value of sum of components of coordinate of stopping point?

My effort is trying to solve this question with markov chain approach. I define $e_1=(-1,0)$ and $e_2=(0,-1)$ and also I use $S_n$ for denoting random walker's coordinate in $n^{th}$ step, hence we have $S_n=x+X_1+X_2+\dots+X_n$ where $x$ denotes the start point and for every $1<i<n$ we have $X_i \in \{e_1,e_2\} $. So, for any point like $z,y$ we have $\mathbb{P}(S_{n+1}=z \ | S_n=y)=\frac12$. But as this random walk is not symmetric I can't go further!

Answer 1

This is a slightly modified version of Banach's matchbox problem where you stop as soon as one box becomes empty, rather than when you first choose an empty box.

Let $N$ be the number of steps needed, and $R$ the sum of the coordinates of the final position. Since this sum is reduced by 1 at every step, we have $N+R=2k$, so that if you solve the second problem, you immediately get the answer for the third problem for free.

It is not hard to show that, for $1\leq r\leq k$, we have $$\mathbb{P}(R=r)={2k-r-1\choose k-1}\left({1\over 2}\right)^{2k-r-1},$$ so that $\mathbb{E}(R)=\sum_{r=1}^k r{2k-r-1\choose k-1}\left({1\over 2}\right)^{2k-r-1}=2k\,{2k\choose k}/4^k,$ and hence $\mathbb{E}(N)=2k\left\{1-{2k\choose k}/4^k\right\}.$

Answer 2

I am not an expert in probability, but here it is my approach using very naive tools:

Let $S$ denote the stopping point. The expected value of the sum of the components at the stopping point can be calculated as follows:

$$\begin{align*} P(S=(a,0))&=\left(\dfrac{1}{2}\right)^{\text{distance between $(k,k)$ and $(a,0)$}}\times \left[\text{# paths from $(k,k)$ to $(a,0)$ using $\leftarrow,\downarrow$}\right]\\ &=\left(\dfrac{1}{2}\right)^{(2k-a)} \times [\text{choose $(k-a)$ positions out of the $(2k-a)$ to put $\leftarrow$}]\\ &=\left(\dfrac{1}{2}\right)^{(2k-a)}\cdot \binom{2k-a}{k-a}\end{align*}$$ and similarly for $P(S=(b,0))$, with $1\leq a,b\leq k$. So, the expected value (vector?) of the ending position is:

$$\begin{align*}\mathbb{E}(S)&=\sum_{a=1}^k (a,0)\cdot P(S=(a,0))+\sum_{b=1}^k(0,b)\cdot P(S=(0,b))\\&=\sum_{a=1}^k\left(\dfrac{1}{2}\right)^{(2k-a)}\cdot \binom{2k-a}{k-a}[a,0]+\sum_{b=1}^k\left(\dfrac{1}{2}\right)^{(2k-b)}\cdot \binom{2k-b}{k-b}[0,b]\\ &=\left[\sum_{a=1}^k\left(\dfrac{1}{2}\right)^{(2k-a)}\cdot \binom{2k-a}{k-a}\cdot a\quad,\quad\sum_{b=1}^k\left(\dfrac{1}{2}\right)^{(2k-b)}\cdot \binom{2k-b}{k-b}\cdot b\right]\end{align*}$$

Thus, the expected value of the sum of the coordinates of $S$ is

$$\mathbb{E}(S_x+S_y)=2\cdot \sum_{a=1}^k\left(\dfrac{1}{2}\right)^{(2k-a)}\cdot \binom{2k-a}{k-a}\cdot a .$$

---

To calculate the expected value of the time we can do:

$$\begin{align*}\mathbb{E}(T)&=\sum_{t}t\cdot P(T=t)\\&=\sum_{t=k}^{2k-1} 2\cdot t\left(\dfrac{1}{2}\right)^t\cdot \binom{k}{k-t}\end{align*}$$

---

I would appreciate if somebody could tell me if my reasoning is correct, and also if I am using (implicitly) Markov chains, because I don't know what they are. I apologize for not having a closed form for the answers above, but I didn't see how to reduce them.