How to analyse a random walk with random transition probabilities Consider a $1$-dimensional random walk with discrete time steps. We start at the origin and at each integer position there is possibly different probability of moving right one step, or left one step.
For each position $i$ a single coin toss is made to fix the transition probabilities at that position.
With probability $1/2$ there  is a probability of moving right of $2/3$ and probability of moving left of $1/3$.
With probability $1/2$ there is a probability of moving left of $2/3$ and probability of moving right of $1/3$.
For a given position $i$ this coin toss is only ever done once so the transition probabilities for that position are then fixed forever.
If you start at the origin, how far away do you expect to be after $n$ steps?  I would be happy with a large $n$ approximation if that is easier.
 A: The subject is huge and called random walks in random environment. The lecture notes by Ofer Zeitouni at Saint Flour summer school in 2001 are a classical introduction but there are other good texts also available on the web.
A (perhaps counterintuitive) result one soon encounters in this theory concerns the model you describe, where each site $i$ in $\mathbb Z$ is given some probabilities $p_i$ and $q_i=1-p_i$ of transitions to the right $i\to i+1$ and to the left $i\to i-1$ respectively, and the random variables $(p_i)$ are i.i.d.
Then a necessary and sufficient condition for recurrence, almost surely with respect to the environment (see $(\ast)$ below), is not the condition that $E(p_0)=E(q_0)$, that is, $E(p_0)=\frac12$, but that $E(\log p_0)=E(\log q_0)$, that is, $$E\left(\log\frac{p_0}{1-p_0}\right)=0\tag{$\dagger$}.$$
$(\ast)$ Let us be more explicit about this point. 
Call $e=(p_i)_{i\in\mathbb Z}$ the environment, $\mathbb P$ its distribution, and, for each $e$, $P_e$ the distribution of the random walk conditionally on the environment $e$. Finally, let $\tau$ the first return time to $0$ by the random walk starting from $0$. 
Then the almost sure recurrence referred to above is the fact that $\mathbb P(A)=1$ where $$A=\{e\mid P_e(\tau\lt\infty)=1\},$$ and it holds when $(\dagger)$ holds. Otherwise,  $\mathbb P(A)=0$, that is, $P_e(\tau\lt\infty)\lt1$, $\mathbb P(\mathrm de)$-almost surely.
