I'm working on a problem using an biased coin for a random walk where the probability of -1 (left) is 1/3 and +1 (right) is probability is 2/3. If we let $X_t$ be our position after $t$ time steps, then $\mathbb{E} X_t \geq t/3$.
I need to show after $t=9n$ steps, we are at a position which is at least $n$ with a probability of at least $1/4$.
I believe I can use Markov's inequality to prove (possibly by contradiction) that our position $X_t$ is within $n$. I reviewed this: Markov property in a simple random walk.
My work so far (not sure if any of this is correct):
- Markov's inequality can be written as $P(X \geq a) \leq E(X)/a$.
- From above, $X$ has an expected value of $t/3$ which gives $P(X \geq a) \leq (t/3)/a$.
- Substituting $t=9n$ gives: $P(X \geq a) \leq (9n/3)/a \implies P(X \geq a) \leq 3n/a$.
Not sure if I'm on the right track. What are my next steps? Substitute values for $a$?