DIAMMIBENVERMk1

2022-07-02

Suppose ${a}_{k}=\frac{1}{2}p\left({a}_{k+1}+1\right)+\frac{1}{2}p\left({a}_{k-1}+1\right)+\left(1-p\right)\left({a}_{k}+1\right)$ for $0 and ${a}_{0}={a}_{n}=0$ and $0. How do we find a closed form of ${a}_{k}$? For $p=1$, I know the solution is ${a}_{k}=k\left(n-k\right)$. But I have no idea about this case. It is a system of linear equations, so I think it will a unique solution. In fact, the problem comes from random walk on $\left\{0,1,2,...,n\right\}$ with absorbing states $0,n$. And ${a}_{k}$ is the expectation of number of steps reaching absorbing states when starting at $k$.
${a}_{k}=\frac{1}{2}p\left({a}_{k+1}+1\right)+\frac{1}{2}p\left({a}_{k-1}+1\right)+\left(1-p\right)\left({a}_{k}+1\right)⇔p{a}_{k}=1+\frac{1}{2}p{a}_{k-1}+\frac{1}{2}p{a}_{k+1}$. Thus if we let ${b}_{k}=p{a}_{k},$, then it is equivalent to ${b}_{k}=1+\frac{1}{2}{b}_{k-1}+\frac{1}{2}{b}_{k+1}$, which has solution as above. But how to solve this one about ${b}_{k}$?

trantegisis

Expert

Hint: sum $\phantom{\rule{thickmathspace}{0ex}}{a}_{j+1}-2{a}_{j}+{a}_{j-1}=-\frac{2}{p}\phantom{\rule{thickmathspace}{0ex}}$ for $\phantom{\rule{thinmathspace}{0ex}}j=1,\cdots ,k\phantom{\rule{thinmathspace}{0ex}}$ and watch most terms telescope, leaving ${a}_{k+1}-{a}_{k}-{a}_{1}+{a}_{0}=-\frac{2k}{p}\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}{a}_{k+1}-{a}_{k}={a}_{1}-\frac{2k}{p}$ since ${a}_{0}=0\phantom{\rule{thinmathspace}{0ex}}$.
Sum $\phantom{\rule{thickmathspace}{0ex}}{a}_{j+1}-{a}_{j}={a}_{1}-\frac{2j}{p}\phantom{\rule{thickmathspace}{0ex}}$ for $\phantom{\rule{thinmathspace}{0ex}}j=1,\cdots ,k\phantom{\rule{thinmathspace}{0ex}}$ and telescope again: $\phantom{\rule{thinmathspace}{0ex}}{a}_{k+1}-{a}_{1}=k{a}_{1}-\frac{\overline{)2}}{p}\frac{k\left(k+1\right)}{\overline{)2}}\phantom{\rule{thinmathspace}{0ex}}$, or $\phantom{\rule{thickmathspace}{0ex}}{a}_{k}=k{a}_{1}-\frac{k\left(k-1\right)}{p}\phantom{\rule{thinmathspace}{0ex}}$.
Lastly, let $k=n-1$ and determine ${a}_{1}$ from the condition $0={a}_{n}=n{a}_{1}-\frac{n\left(n-1\right)}{p}\phantom{\rule{thinmathspace}{0ex}}$, which gives ${a}_{1}=\frac{n-1}{p}\phantom{\rule{thinmathspace}{0ex}}$, so in the end ${a}_{k}=k{a}_{1}-\frac{k\left(k-1\right)}{p}=\frac{k\left(n-1\right)}{p}-\frac{k\left(k-1\right)}{p}=\frac{k\left(n-k\right)}{p}\phantom{\rule{thinmathspace}{0ex}}$.

Do you have a similar question?