I came across problem which I cannot seem to solve when self studying probability. I was wondering if people can help me out.
There are $n$ planets in an orbit. So, there are $n$ planets in a circle. An alien starts on one of the planets. With probability $p$ he can move to the right planet. With probability $1-p$ he can move to the left planet. What is the expected number of trips needed in order for the alien to visit all $n$ planets at least once.
Attempt:
Let $t$ be the number of trips or moves. We want to find $E[t|n]$. The base cases are easy: $E[t|n=1]=1$, $E[t|n=2]=2$. $E[t|n=3]$ becomes more challenging and I can't seem to find something that generalizes. I know this can also be modelled as a markov matrix, but unsure how to find the expected number of moves to visit all planets. Even assuming $p=\frac{1}{2}$ I cannot seem to find a solution or a good approach.
Let's first solve the question for case of $p=\frac{1}{2}$ Let $X=\textrm{# steps till you visit all the planets} = X_1 + X_2 + \ldots + X_n$
where $X_i$ = # steps from $(i-1)$th new visit to $i$th new visit Note $X_1 = 0, X_2=1$
Note that to calculate $E[X_i]$, once you visit your $(i-1)$th new planet, the next new planet is either 1 step(right/left) or $i-1$ steps(left/right) thus, if you lay them down flat on a straight line $E[X_i]$ boils down to calculate expected # of steps in a random walk before you reach $-1$ or $i-1$ and for $p=1/2$ it is equal to $i-1$
Hence $E[X] = \sum_{i=1}^n E[X_i] = 0+1+2+\ldots+n-1=n(n-1)/2$
For $p\neq1/2$, only change is in calculating $E[X_i]$, in a non symmetric random walk $S_n - n(2p-1)$ is a martingale, so if you use Optional Stopping time theorem, you get an exact expression for $E[X_i]$, but it is quite ugly so I'm leaving it, here is a link for your reference (3.3): https://people.maths.bris.ac.uk/~mabat/MARTINGALE_THEORY_2016/MT_SOL_03.pdf