Random walk - Markov chain I have a problem.If we start at place $0$ and the probability to go right is $p$ and the probability to go left $q$. I need to calculate the probability after 100 steps that the maximum place when we were in all the experiment is at least 16.
At place 0 we have a barrier on left so we if we want to go left we stay at 0.
How can I start?

 A: Consider the same chain but make state #16 absorbing: $P(16\to 16)=1$. Let the corresponding (tri-diagonal) transition matrix be $P$. Then you are looking for $P^{100}_{0,16}$ - probability of transitioning from $0$ to $16$ in $100$ steps. I don't know a good way to compute this for general $p$ other than taking $P$ to the $100$th power with computer's help since all eigenvalues of $P$ are $1$ with a single eigenvector.
But you can compute a lower bound. If you remove the reflecting barrier at $0$ (hence decreasing probability of reaching state $16$ significantly), the probability to reach $16$ in infinitely many steps becomes $(\frac p q)^{16}\approx 0.04$ - which must be close to probability of hitting $16$ in $100$ steps since after $100$ steps the (modified) walk will drift down to almost normal with mean $100(p-q)=-10$ and standard deviation $10\sqrt{pq}\approx 5$.

It can be shown that expected time to go from state $n-1$ to state $n$ in the original chain is ($q/p=\alpha$):
$$E_{n-1,n}=\frac 1 p \Big(\frac {\alpha^n-1}{\alpha-1}\Big)$$ and hence
$$E_{0,n}=\frac 1 p\frac 1 {\alpha-1}\Big(\frac {\alpha^{n+1}-1}{\alpha-1}-(n+1)\Big)$$
For $p=0.45$, we get
$$E_{0,16}\approx 1148.45$$
which tells you that $P(T_{0,16}\leq 100)$ should be rather small.
