4

This is one of the questions I came across and I could only solve it partially. The question went

A man is randomly typing on a keyboard. Then, what is the probability that the word HEART comes before EARTH?

My attempts

The first $4$ letters of EARTH are the same as last 4 of HEART.

For EARTH to appear before HEART, any letter other than H must've appeared first and then should be followed by EART and then a H later on.

For HEART to appear first before EARTH, only the letter H must've appeared first and then may be followed by EART.

Since, the number of letters to appear in the case of HEART is less than EARTH, the probability of occurrence of HEART is more than that of EARTH.

To calculate how much, I'm just considering in case of

EARTH first: $$P(E)=\frac{25}{26}.\frac{1}{26}.\frac{1}{26}.\frac{1}{26}$$

HEART first: $$P(E)=\frac{1}{26}.\frac{25}{26}.\frac{25}{26}.\frac{25}{26}$$

This obviously isn't correct, since it doesn't give any individual probability for the occurrence of each letter.

So, can anyone calculate the probability for each of these two?

Your IDE
  • 1,273
  • Usually you want the argument of $P(;)$ to be unique for each event. For example, I would probably set $E$ as the event that $\mathsf{EARTH}$ comes first and $H$ as the event that $\mathsf{HEART}$ comes first. – gen-ℤ ready to perish Dec 06 '17 at 13:54
  • 1
    Roughly $\frac{1}{26}$ of cases of xxxEARTH are in fact xxHEARTH so would not count as a win for EARTH. So I would expect the probability of a win for HEART to be about $\dfrac{1}{1+\frac{25}{26}}=\dfrac{26}{51} \approx 0.5098$. This is not exact because it ignores the possibility of EARTH immediately or of patterns like xxxEARTHEART, but those are relatively less likely and would be lost in the rounding – Henry Dec 06 '17 at 15:38
  • @Henry : Using matlab to get a numerical solution to the exact DTMC gives $P[heart] \approx 0.509803921745840$, very close to your approximation above. – Michael Dec 06 '17 at 16:51

2 Answers2

4

You can assume the key options are H, E, A, R, T, X, where "X" represents any other key that is not H, E, A, R, or T. These are typed with probabilities $a, a, a, a, a, 1-5a$, respectively, for $0< a\leq 1/5$.

Next, you can model the situation with a finite state discrete time Markov chain. For example, the initial state can be labeled START, there is a trapping state HEART, and another trapping state EARTH. (A state $i$ is a "trapping state" if $P_{ii}=1$, that is, once reached, the probability of staying there is 1.)

Can you define all states in the state space $S$, draw the chain, and label the transition probabilities?

You then define $p(i)$ as the probability of eventually ending in HEART, given we start in state $i \in S$, and write recursive equations for $p(i)$. Then the probability we eventually end in HEART is just $p(START)$. Note that $p(HEART) = 1$ and $p(EARTH)=0$.

Michael
  • 23,905
  • Using matlab to solve this DTMC witih $a=1/26$ gives $P(HEART) \approx 0.509803921745840$, which is very close to Henry's approximation of $26/51$. – Michael Dec 06 '17 at 16:50
  • Using $a=1/5$ gives $P(HEART) \approx 0.555555555555501$, very close to $1/(1+4/5)$. – Michael Dec 06 '17 at 16:57
  • Gandalf observes that, by permuting letters, the expected time to get HEART is the same as EARTH. Moreover, it holds that the random time to get HEART has the same distribution as the random time to get EARTH. However, the probability of getting HEART first is larger than $1/2$. To see simpler examples of when this can happen, consider the random vector $(X,Y)$ that takes values equally likely over the set ${(0,1), (1,2), (2,0)}$. Then $X$ and $Y$ have the same distribution, but $P[X<Y] = 2/3$. – Michael Dec 06 '17 at 18:45
  • Interesting observation there w.r.t. to the state transition between the strings, but it'd just prove that HEART has greater probability than EARTH, which I've already proved in my original question; I wanted to know by how much exactly? As for your comment for running through MATLAB, that's absolutely brilliant ; but this question is supposed to be actually calculated manually with the probability theory. Nonetheless, your answer is brilliant. I'll run it on Java random string of char. generator and verify it !! But can you prove it manually? – Your IDE Dec 07 '17 at 06:37
  • @YourIDE In your original question, I do not see a proof that the probability HEART comes first is greater than 1/2. Actually, I did not follow your reasoning in your attempts given there (you also ended with "this is obviously incorrect" so I did not feel inclined to look closely at your attempts). This looks difficult to compute exactly without the DTMC; Henry gave an accurate approximation in his comment. – Michael Dec 07 '17 at 10:01
  • 1
    I used matlab to solve the linear $Pq = q$, $q_{11}=1, q_6=0$ equations for $q=(q_1, ..., q_{11})$, where $P$ is an $11 \times 11$ matrix. You can do it by hand if you want but that takes more time. Here $q_i$ is the probability of eventually ending in HEART (state 11) given we start in state $i$. I numbered my states so that 6 corresponds to EARTH. – Michael Dec 07 '17 at 10:12
-3

First some notation - let $E(s)$ denote the expected number of letters that are typed before string $s$ is observed.

Now suppose that $E(HEART) < E(EARTH)$. Letters are typed at random, so we can rename the letters without affecting probabilities. By renaming letters H to E, E to A etc. we can show that $E(EARTH) < E(ARTHE)$. And by applying this argument several time we have

$E(HEART) < E(EARTH) < E(ARTHE) < E(RTHEA) < E(THEAR) < E(HEART)$

which is a contradiction.

If we assume $E(HEART) > E(EARTH)$ we can also derive a contradiction. So the only possible conclusion is $E(HEART) = E(EARTH)$ and so the probability that HEART is observed before EARTH is 0.5.

(This is essentially a symmetry argument).

gandalf61
  • 15,326
  • It is true that $E[HEART] = E[EARTH]$, and for 26 possible letters these are both equal to $26^5$ (this is the expected time to get HEART, including the last letter "T"). However, the probability that HEART occurs first is slightly larger, even though these expectations are the same. – Michael Dec 06 '17 at 17:03
  • @gandalf61 No, they're not equal... I already proved it above. – Your IDE Dec 06 '17 at 18:17
  • @gandalf61: You may be interested in the last comment in my answer regarding the distributions of times to HEART and EARTH being the same (for the same reasoning as your permutation argument). So if two independent monkeys are racing, one types until it gets HEART, the other types until it gets EARTH, neither monkey has a larger chance of finishing first. But each individual monkey is more likely to type HEART before it types EARTH. Overall, you could keep this answer as valid if you just change your final conclusion that the probability of observing HEART first is $0.5$. – Michael Dec 06 '17 at 18:59
  • I stand by my conclusion. If HEART is more likely to occur before EARTH then by the same argument THEAR is more likely to occur before HEART; RTHEA before THEAR; ARTHE before RTHEA; and EARTH before ARTHE. These relations are transitive, so now EARTH is more likely to occur before HEART and we have the same contradiction. I will run a simulation to confirm this and come back with results. – gandalf61 Dec 07 '17 at 06:57
  • Simulation results suggest that HEART is more likely to occur before EARTH. I am surprised. My symmetry argument must be wrong somewhere. – gandalf61 Dec 07 '17 at 07:54
  • @gandalf61 The individual steps in your above comment are correct (indeed THEAR is more likely to be seen before HEART and so on). The mistake is concluding "these relations are transitive." They are not. For a simpler example, consider three events $a, b, c$. Suppose they are equally likely to happen in the following 3 possible orders: ${abc, cab, bca}$. So $a$ is more likely to occur before $b$ (prob 2/3); $b$ is more likely to occur before $c$ (prob 2/3); $c$ is more likely to occur before $a$ (prob 2/3). A non-transitive "triangle." – Michael Dec 07 '17 at 10:31