I am given the following Markov chain and would like to estimate my expected position after $k$ iterations.
The chain is in $\mathbb{Z}$. I start at position $1$, with probability $q_1$, I stay at the same position. With probability $1-q_1$, I move to the position $2$. When I am at location $i$, either with probability $q_i$ I stay or with probability $1-q_i$ I move to location $i+1$, for $i = 1, 2, \ldots, k-1$. It is important to note, that we cannot go back.
Hypothesis: We assume that, $0 \leq q_1 \leq q_2 \leq \ldots \leq q_{k-1} \leq 1$. This means that the more we more along the chain, the likelier we are to stay at the same position.
We start at position $1$ and perform $k-1$ steps. Hence, the maximum position is $k$ at the end. We say that a location $j$ is unvisited, if after $k-1$ steps, we stop at location $i$ with $i < j$.
I would like to upper bound the expected number of unvisited position and show the following, $$ \mathbb{E}\left[ |\textrm{unvisited}| \right] = \sum_{i = 1}^{k-1} \mathbb{P}\left( \textrm{be at $i$ after $k-1$ steps} \right)\cdot (k-i) \leq \sum_{i = 1}^{k-1} q_i. $$
I have seen that it works for $k = 2, 3, 4$, but could not manage to do it in a general case. It is important to use that $0 \leq q_1 \leq q_2 \leq \ldots \leq q_{k-1} \leq 1$.
Let $X_k$ denote the position after $k$ steps, then, for every $k\geqslant1$, the one-step Markov property of the process yields $$E(X_{k+1}\mid X_k=x)=x+1-q_x$$ Since $X_k\leqslant k$ almost surely and $q_x\leqslant q_k$ for every $x\leqslant k$, $$E(X_{k+1}\mid X_k=x)\geqslant x+1-q_k$$ hence $$E(X_{k+1}\mid X_k)\geqslant X_k+1-q_k$$ Integrating both sides of this inequality, one sees that $$E(X_{k+1})\geqslant E(X_k)+1-q_k$$ Since $X_1=1$ almost surely, this yields $$E(X_k)\geqslant1+\sum_{i=1}^{k-1}(1-q_i)=k-\sum_{i=1}^{k-1}q_i$$ Finally, the number $U_k$ of vertices less than $k$ unvisited at time $k$ is $U_k=k-X_k$, hence, as required, for every $k\geqslant1$, $$E(U_k)\leqslant\sum_{i=1}^{k-1}q_i$$