Expectation of first visit in a random walk

Question

We consider a vertice $O$ with two adjacent vertices $A$ and $B$. We denote $a$ the edge $\{O,A\}$ and $b$ the edge $\{O,B\}$. At each stage $t\geq 1$, edge $a$ is active with probability $p$ and inactive with probability $1-p$. The same goes for $b$.

We adopt the following policy:

In $O$, if neither $A$ nor $B$ has been visited before,

• If both edges are inactive, stay in $O$,

• If only one edge is active, take it,

• If both edges are active, go to $A$ with probability $\alpha$ and to $B$ with probability $1-\alpha$.

In $O$, if $a$ has already been visited (but not $b$), take $b$ when active. And symetrically if $b$ has already been visited.

In $A$, go to $O$ when $a$ is active. And similarly for $B$.

My goal is to compute the average time needed to visit $A$ for the first time, denoted $T$.

We have $$E[T] = E[T|A \text{ is visited first}]P(A \text{ is visited first})+E[T|B \text{ is visited first}]P(B \text{ is visited first}).$$

I have computed $P(A \text{ is visited first}) = \frac{p(1-p)+\alpha p^2}{1-(1-p)^2}$ and $P(B \text{ is visited first}) = \frac{p(1-p)+(1-\alpha) p^2}{1-(1-p)^2}$.

My problem is to compute $E[T|A \text{ is visited first}]$.

Answer 1

Note that the number of steps it takes to leave $O$ is independent of where you go after you leave. You leave as soon as at least one edge is active: this happens with probability $1 - (1-p)^2$, so the expected number of steps until this happens is the expected value of a geometric distribution: $$\frac1{1-(1-p)^2}.$$ This is also the value of $\mathbb E[T \mid A \text{ is visited first}]$: we can think of "$A$ is visited first" as the event "once an edge becomes active, it's possible to go to $A$ and we do", so all we have to do is wait for an edge to become active.

Similarly, in the case $B$ is visited first, geometric distributions tell you everything. You have:

• A $\text{Geometric}(p)$ number of steps to wait until we can return to $O$;
• A $\text{Geometric}(1-(1-p)^2)$ number of steps to wait until we go to either $A$ or $B$ again;
• This is repeated $\text{Geometric}(q)$ times, where $q$ is the probability that, when leaving $O$ after we've already been to $B$, we'll end up at $A$ next.

In this case, linearity of expectation and independence let us add and multiply the expected values of the above in the naive way to compute $\mathbb E[T \mid B \text{ is visited first}]$.

---

Note: in this answer, I'm adopting the convention that a geometric random variable has support $\{1,2,\dots\}$ (the positive integers).