I tried to solve this problem analytically but I'm not being able to compute the solution:
Say we have a system of M different sites. We walk from one site to another in such a way that:
- It takes a time T1 to walk a loop (start in a site and return to the same site without visiting any other sites in the middle)
- It takes a time T2 to move from one site to any other different site without visiting any other site in the middle
- The probability of doing a loop is p
Say we already visited K sites and we are standing in a site. How long does it take in average to visit a new, previously unvisited site?
What I tried is the following: I step in a new site. The previous step I had to come from an already visited site, what took T2. To get to that site, say we got there in $N-1$ movements consisting on $m$ loops and $N-m-1$ real moves. I then arrive to an equation: $F(N-1)=\sum_{m=1}^{N-1}\frac{(N-1)!}{m!}[T1m+T2(N-m-1)]p^{m}(1-p)^{N-m-1}((K-1)/(M-1))^{m}$.
Finally, the mean time is going to be $T_{2}+(1-p)(\frac{M-K}{M-1})\sum_{N=1}^{\infty}[(N-1)T_{1}p^{N-1}+F(N-1)]$
I plug that in Maple and still calculating. There has to be a way of getting an analytical solution...
Let $\mathcal{T}$ be the total amount of time before getting to a new site and let $N$ be the random number of rounds that it took before arriving at a new site and let $X_i$ be the amount of time spent moving in the $i$'th round for $i = 1,...,N$. Then we can write the expected amount of time before getting to a new site in the following way. \begin{align} \mathbb{E}[\mathcal{T}] &= \mathbb{E}_{N} \left [ \mathbb{E}_{X_1,...,X_n} \left [ \sum_{i=1}^N X_i \ \bigg | \ N\right ] \right ] \\ &= \mathbb{E}_N \left [ \sum_{i=1}^N \mathbb{E}_{X_i} \left [ X_i \ | \ N \right ] \right ] \\ &= \mathbb{E}_N \left [ \sum_{i=1}^{N-1} \mathbb{E}_{X_i}[X_i \ | \ N] + T_2 \right ] \end{align} where we have used that $\mathcal{T}$ is the sum of all the time spent in the $N$ rounds it takes before getting to a new site in the first line. The second line uses linearity of expectation, which is still valid for conditional expectations. The last line uses that $X_N = T_2$ since the last round before we move to a new site must take $T_2$ time.
Now for $i < N$ we need to calculate $\mathbb{E}_{X_i}[X_i \ | \ N]$. To keep the expressions from here from getting really long, define the constants \begin{align} p_{stay} &\triangleq p \\ p_{vis} &\triangleq (1-p)\frac{K-1}{M-1} \\ p_{new} & \triangleq (1-p)\frac{M-K}{M-1} \end{align} which represent the chance of staying at the site, moving to a site already visited, and moving to a new site respectively. Using these we can calculate $\mathbb{E}_{X_i}[X_i \ | \ N]$ for $i < N$ as follows. Since $X_i$ is discrete we have \begin{align} \mathbb{E}_{X_i}[X_i \ | \ N] &= T_1\mathbb{P}(X_i = T_1 \ | \ N) + T_2\mathbb{P}(X_i = T_2 \ | \ N) \\ &= T_1 \frac{p_{stay}}{1-p_{new}} + T_2 \frac{p_{vis}}{1-p_{new}} \triangleq E_{miss}. \end{align} Where I'm introducing a new constant, $E_{miss}$, the expected amount of time spent in a round conditioned on that round not being a movement to a new site. The expression above uses conditional probabilities, and the conditioning is what prevents us from just using $p$ and $(1-p)$, we must account for the knowledge that we are not going to a new site.
Now plugging this into the expression above we have \begin{align} \mathbb{E}_N \left [ \sum_{i=1}^{N-1} \mathbb{E}_{X_i}[X_i \ | \ N] + T_2 \right ] &= \mathbb{E}_N \left [ \sum_{i=1}^{N-1} E_{miss} + T_2 \right ] \\ &= \mathbb{E}_N \left [ (N-1)E_{miss}\right ] + T_2 \\ &= E_{miss}\mathbb{E}_N[N] - E_{miss} + T_2 \end{align} Next we can compute the expected value of $N$ \begin{align} \mathbb{E}_N[N] &= \sum_{n=1}^\infty N\mathbb{P}(N = n) \\ &= \sum_{n=1}^\infty n(1-p_{new})^{n-1}p_{new} \\ &= \frac{p_{new}}{(1 - (1-p_{new}))^2} = \frac{1}{p_{new}} \end{align} (This is what we would expect considering $N$ follows a geometric distribution with parameter $p_{new}$). Now putting things back together, the final expression is \begin{align} \mathbb{E}[\mathcal{T}] &= \frac{E_{miss}}{p_{new}} - E_{miss} + T_2 \\ &= \left (\frac{1}{p_{new}} - 1 \right )\left ( T_1 \frac{p_{stay}}{1-p_{new}} + T_2 \frac{p_{vis}}{1-p_{new}} \right ) + T_2 \\ &= \left (\frac{1}{(1-p)\frac{M-K}{M-1}} - 1 \right )\left ( T_1 \frac{p}{1-(1-p)\frac{M-K}{M-1}} + T_2 \frac{(1-p)\frac{K-1}{M-1}}{1-(1-p)\frac{M-K}{M-1}} \right ) + T_2 \end{align} This can probably be simplified somewhat with some algebra.