Probability of a typing monkey backspacing all letters.

Question

Suppose a monkey is typing on a keyboard into a word document. The word document has x letters already in the document. The keyboard has n number keys on it (i.e. keys that cause another digit to appear on the screen) and k backspace keys. If the monkey types for an infinitely long time, what is the probability that at any point there will be 0 characters on the screen?

Answer 1

Short easy answer

Edited after @Hurkyl observation.

[Corrected] It is a known result that an (unconstrained) simple 2D-random walk visits every position infinitely many times, except of course if the probability $p$ of up-steps is $0$ or $1$, in which cases the walk is not random.

Therefore, if in your example both $k$ and $n$ are strictly positive, than you may consider the problem as a simple 2D-random walk with $\frac{n}{n+k}>0$ probability of up-steps and $\frac{k}{n+k}>0$ of down-steps, starting at position $x$, and ending when position $0$ (clear screen) is reached (this is the constrained version). Anyhow, position $0$ is clearly reached.

Long answer (not even complete)

Starting at position $s(0)=x$ (characters), at each time $k\in\mathbb N$ either you go up one step with probability $\frac{n}{n+k}$ or you go down with probability $\frac{k}{n+k}$. If you reach position $s(k)=0$ you stop. If you count up-steps $u$ and down-steps $u$, in $k$ time units the possible distance run is, say, $\Delta$ (i.e. the difference $\Delta$ between the final and the initial number of characters characters after $k$ types). Then $d$ satisfies $$ \begin{cases} u-d~=&\Delta \\ u+d~=&k\\ u,\,d\in&\mathbb N \end{cases} \quad\rightarrow\quad \begin{cases} u~=&\frac{k+\Delta}2 \\ d~=&\frac{k-\Delta}2\\ u,\,d\in&\mathbb N \end{cases} $$ Then, as expected, in order $u,d$ to be positive integers, $$ -k\leq\Delta\leq k \quad\text{and}\quad k+\Delta~\text{even} $$ You want $\Delta=-x$ for some $k\geq x$, corresponding to $u=\frac{k-x}2$ up-steps and $d=\frac{k+x}2$ down-steps.

Let us first assume $x=2y$ even; then $k=2h$ must be even as well. The probability that in exactly $k\geq x$ steps (types) you reach $0$ following a specific sequence of $u$ up-steps $U$ and $d$ down-steps $D$, is then $$ \left(\frac{n}{n+k}\right)^u \left(\frac{k}{n+k}\right)^d ~=~ \left(\frac{n}{n+k}\right)^{\frac{2h-2y}{2}} \left(\frac{k}{n+k}\right)^{\frac{2h+2y}{2}} ~=~ \frac{n^{h-y}k^{h+y}}{(n+k)^{2h}} $$ Note that not every sequence of $U$ and $D$ goes well for our purposes, i.e. $$ \delta_1\,\delta_2\,\delta_3\,\ldots\,\delta_k \qquad\delta_i\in\{U,D\} $$ must satisfy that for every $j=1\ldots k$, the subsequence $\delta_1\,\delta_2\,\delta_3\,\ldots\,\delta_j$ does not reach $0$. Clearly it cannot go below $0$, and in order not to overcount the events it neither can reach $0$ before, in which case we would have stopped at time $j$.

Then, let $u_j$ and $d_j$ be the number of up-steps and down-steps in the sequence up to time $j$. Then $$ u_k=u,~d_k=d \qquad\text{and}\qquad n+u_j-d_j > 0 \quad\forall\, j=1\ldots k $$ Then it is a matter of determining how many such sequences exist and summing over $k=n\ldots \infty$. The case $x$ odd is similar.