Say I am drunk and at every second I can move 1m to the left or 1m to the right. My home is 10m to the right, and if I reach it, I will fall to my bed and the game will end. What is the probability that I will ever reach my bed.
I know that in general such problems are solved by considering the probability transition matrix, diagonalising it and multiplying it to the power infinity, thus obtaining the extremal case. However, in this case the matrix is infinite. Ideas?
Edit: Thoughts so far:
Let $p[x,t]$ be an infinite vector of probabilities of my locations at time step $t$, such that $p[0,t]$ corresponds to being 10m to the right. Initially $p[10, 0] = 1$ and the rest of $p[*, 0] = 0$. The equation for 1 time step can be written as
$\vec{p}[t+1] = T \times \vec{p}[t]$
where $T$ is the probability transition matrix. The transition matrix can be written as
$T[i,j] = 0.5(\delta_{j, i-1} + \delta_{j, i+1})$ if both $i>0$ and $j>0$, and
$T[i,j] = \delta_{i,j}$ otherwise
We are interested in the quantity $p[0, \infty]$
Edit 2:
Ok, I have a high suspicion that the answer is approximately $50\%$. It should be easy to see that the solution for the unbounded problem is a normalized Pascal's triangle, which eventually becomes a Gaussian with ever-spreading width. Thus, over time, the starting point is irrelevant, and for any integer, $50\%$ of the probability will be on the left and 50 on the right of it. In the bounded case, the probability should be slightly higher, because the trajectories that reach the final destination are not allowed to go back.
There is a standard "renewal theory" approach. First you solve a different problem: what's the probability to hit a subset $A$ of the state space before hitting a subset $B$ started at each point $x$? Call this $q(x)$ then it satisfies the system of linear equations
$$(Lq)(x)=0 \quad x \not \in A \cup B \\ q(x)=0 \quad x \in B \\ q(x)=1 \quad x \in A$$
where $L=P-I$ and $P$ is the (row stochastic) transition probability matrix. This result is basically obtained by writing $q(x)$ as the average of $q(y)$ over the "neighbors" of $x$ in the state space.
Now you can use this to solve your problem by computing the associated $q_n$ with $A_n=A=\{ 10 \}$ and $B_n=\{ -n \}$. Then your desired answer is $\lim_{n \to \infty} q_n(0)$. One may explicitly compute $q_n(0)$ for all $n$ by recurrence relation techniques and then take the limit.