Could any equation have predicted the results of this simulation? Suppose there is a coin that has a 5% chance of landing on HEADS and a 95% chance of landing on TAILS. Based on a computer simulation, I want to find out the following :

*

*The average number of flips before observing HEADS, TAILS, HEADS (note: not the probability, but the number of flips)

Using the R programming language, I tried to make this simulation (this simulation keeps flipping a coin until HTH and counts the number of flips until this happens - it then repeats this same process 10,000 times):
results <- list()

for (j in 1:10000) {

  response_i <- ''
  i <- 1

  while (response_i != 'HTH') {
    response_i <- c("H","T")
    response_i <- sample(response_i, 3, replace=TRUE, 
                         prob=c(0.05, 0.95))
    response_i <- paste(response_i, collapse = '')

    iteration_i = i
    if (response_i == 'HTH') {
      run_i = data.frame(response_i, iteration_i)
      results[[j]] <- run_i
      }
    i <- i + 1
  }
}

data <- do.call('rbind', results)

We can now see a histogram of this data:
hist(data$iteration_i, breaks = 500, main = "Number of Flips Before HTH")


We can also see the summary of this data:
summary(data$iteration_i)

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
    1.0   119.0   288.0   413.7   573.0  3346.0

My Question:

*

*Could any "mathematical equation" have predicted the results of this simulation in advance? Could any "formula" have shown that the average number of flips to get HTH would have been 413? Can Markov Chains be used to solve this problem?


*Based on the "skewed" shape of this histogram, is the "arithmetical mean" (i.e. mean = sum(x_i)/n) a "faithful" representation of the "true mean"? Looking at the above histogram, we can clearly see that you are are more likely to see HTH before 437 iterations compared to seeing HTH after 437 iterations, e.g. (on 100,000 simulations, the new average is 418):

nrow(data[which(data$iteration_i <418), ])

63184

nrow(data[which(data$iteration_i > 418), ])

36739
For such distributions, is there a better method to find out the "expectation" of this experiment?
Thanks!

There is a fun way to answer this problem using martingales, and in particular using https://en.wikipedia.org/wiki/Optional_stopping_theorem.  I first saw this trick in the book A First Look at Rigorous Probability Theory by Jeffrey S. Rosenthal, in the martingale chapter. (I don't have the book in front of me at the moment but I'll edit and add a page or equation number when I do.)
Imagine that at each time step $t$ a person arrives and places a bet on the outcome of the next coin toss.  The payoff to their first bet is:
$\begin{equation}
\begin{cases}
-1 &\mbox{if toss } t \mbox{ is T} \\
+19 &\mbox{if toss } t \mbox{ is H} \\
\end{cases}
\end{equation}$
If they are wrong (i.e. lose money) on this bet, they stop betting. Note that their net gain if they exit at this point is $-1$. If they are correct, they continue to betting on toss $t+1$ and receive the following payoff:
$\begin{equation}
\begin{cases}
+\frac{20}{19} &\mbox{if toss } t+1 \mbox{ is T} \\
-20 &\mbox{if toss } t+1 \mbox{ is H} \\
\end{cases}
\end{equation}$
If they are wrong on this second bet, they stop betting. Again, note that their net gain if they exit at this point is (by design) $19-20 = -1$. If they were correct for this second bet, they proceed to betting on the outcome of toss $t+2$ and receive:
$\begin{equation}
\begin{cases}
-\frac{400}{19} &\mbox{if toss } t+2 \mbox{ is T} \\
+400 &\mbox{if toss } t+2 \mbox{ is H} \\
\end{cases}
\end{equation}$
If they are incorrect, they exit with a net gain of $19 + \frac{20}{19} - \frac{400}{19} = -1$. If they are correct, everything stops: we have just seen a HTH sequence, and the person who started betting at the beginning of that sequence has just won $19 + \frac{20}{19} + 400 = 420.0526$.
Note that two people have started betting after this big winner: one person whose first bet was incorrect (they exit with $-1$), and a second person whose first bet was correct (they win $19$ but nothing more because the process stops).
Let $\tau$ denote the stopping time, and let $X_t$ denote the cumulative net amount won by all gamblers up to and including time $t$. Let $X_0 = 0$, and note that $X_t$ is a martingale because all bets are (by construction) fair, with an expected payoff of $0$.  This will let us use https://en.wikipedia.org/wiki/Optional_stopping_theorem and in particular $\mathbf{E}[X_\tau] = \mathbf{E}[X_0] = 0$.
$X_\tau$ is the total amount won when we reach the stopping time. At this point $\tau - 3$ people will have lost their bets and exited with a net gain of $-1$, one person will have won $420.0526$, and we also have to account for the last two people who start betting after the winner. We have:
$\begin{equation}
\mathbf{E}[X_\tau] = 0 = (\mathbf{E}[\tau]-3)*(-1) + 420.0526 + (-1) + 19
\end{equation}$
Which leads to $\mathbf{E}[\tau] = 420.0526 + 3 + 18 = 441.0526$, which agrees with the answers posted earlier.
