let $T_n$ denote the number of steps a linear random walk on the nonnegative integers takes before reaching the position $n$ for the first time. What will be $\mathbb{E}[T_n]$.
I tried to derive this:
let say to reach "$3$" we have $\mathbb{E}[3]$ expected number of steps
= probability to getting to "number 3" in 3 steps X 3 + probability of getting to "number 3" in 5 steps X 5+ probability of getting to "number 3" in 7 steps X 7 + ...
$\mathbb{E}[T_3] = \left(\frac{1}{2}\right)^2 \times 3 + \left(\frac{1}{2}\right)^4 \times 5 + \left(\frac{1}{2}\right)^6 \times 7 + ...$
assuming this "Arithmetico-geometric sequence" we get answer of approx $N$.
the correct answer is $N^2$. Anyone have idea what going wrong in my analysis?
For $x\geq 0$ define $e_x$ to be the expected number of steps needed to reach state $x+1$ starting at state $x$. Then $e_0=1$, and for $x>0$ first step analysis gives $e_x=1+(e_{x-1}+e_x)/2.$ This equation implies $e_x=2+e_{x-1}$, so by induction $e_x=2x+1$. Then $$\mathbb{E}[T_n]=\sum_{x=0}^{n-1} e_x =\sum_{x=0}^{n-1} (2x+1)= n^2.$$