How to find the average number of iterations for a variable to reach a number

Question

Suppose I have an infinite loop with a variable x that starts at 0. Every iteration of the loop, x has a 10% chance of being increased by 1 and a 90% chance of being decreased by 1, but it cannot go below 0. How can I calculate the average number of iterations of the loop for x to reach a certain number?

Answer 1

As per MSE protocol, I can't give a full answer, but just to start you off, suppose you want to know the expected # of steps to get to $4$ on the natural number line from $0$,

we can start by writing$\;\;S_0 = 1+ 0.1S_1+0.9S_0$

This equation means that with one step from $0$, we either move with $Pr=0.1$ to step $1$ or fall back to step $0$ (since we can't go below $0$) with $Pr= 0.9$, and we can frame similar equations step by step, so the four equations will be

$S_0 = 1+ 0.1S_1+0.9S_0$
$S_1=1+0.1S_2+0.9S_0$
$S_2=1+0.1S_3+0.9S_1$
$S_3=1+0.9S_2$

The last equation means that
from $3$ either you get to $4$ with one step or fall back to step $2$

Why don't you try to solve this system of linear equations for $S_0$, and explore ?
And read about random walks ?