A book with only two letters

Question

Dr. G somehow detests reading novels but he decided to read a one then he naturally got bored and decided to delete all letters except A and B letters in the book.

So with this new book which consists of only A and B letters, what is the chance to find "ABA" word before "BABA" when you try to form a word with letters in order from the very beginning?

Answer 1

There is a nice general theorem governing this sort of thing (which I'll give at the end), but here's how to do it from first principles.

I'll assume, for reasons set out in my comment on the original question, that A and B appear independently with probability 1/2 each in each position. The probability we're after will be different if the frequencies of A and B are different, or if their probabilities in different places are not independent.

OK. Now draw a graph (in the dots-and-arrows sense, not the how-y-depends-on-x sense) whose vertices are the prefixes of the words ABA and BABA. That is: [empty], A, B, AB, BA, ABA, BAB, BABA. We want to find, for each prefix p, the probability that if we have just read p (and not any longer prefix) we will find ABA before BABA when we continue.

The cases p=ABA and p=BABA are easy (the probabilities are 1 and 0 respectively) and the case p=[empty] is the one whose answer we actually want, which I'll call q. (With hindsight, using "p" to stand for "prefix" may have been a bad choice.) Let's call the others pA, pB, pAB, pBA, pBAB. We can write down a bunch of simultaneous equations for them, the idea being that e.g. if we've just seen BA then after the next letter we'll have seen BAB or BAA, with probability 1/2 for each -- and the latter is exactly equivalent to having just seen A.

So:

$\eqalign{q &= (pA+pB)/2 \\ pA &= (pA+pAB)/2 \\ pB &= (pBA+pB)/2 \\ pAB &= (1+pB)/2 \\ pBA &= (pA+pBAB)/2 \\ pBAB &= (0+pB)/2 }$

The first equation doesn't tell us much yet. The next two tell us that $pAB=pA$ and $pBA=pB$ and the last tells us $pBAB=pB/2$, so now we have everything in terms of pA and pB.

$\eqalign{q &= (pA+pB)/2 \\ 2pA &= 1+pB \\ pB &= (pA+pB/2)/2 }$

So, finally,

the simultaneous equations yield $pA=3/4,pB=1/2$ and then the first equation gives $q=5/8$.

I promised to tell you the general theorem, so here it is. You can find it in the "Discrete probability" chapter of "Concrete Mathematics" by Graham, Knuth and Patashnik. It's due to John Horton Conway (as if he didn't have enough other neat mathematical things to his credit!).

Given a string s of As and Bs, define prefix(s,k) to be its first k letters and suffix(s,k) to be its last k letters. For two strings s,t, say s ~k~ t if suffix(s,k) = prefix(t,k): the end of s matches the beginning of t. And now define a number s:t which has bit k-1 set iff s ~k~ t.

Theorem: the odds in favour of seeing s before we see t are t:t-t:s to s:s-s:t.

So in the present case s=ABA and t=BABA; so

in binary we have s:s=101, s:t=010, t:t=1010, t:s=101, so the odds are (10-5) : (5-2) = 5:3, which is the same thing as the probability being 5/8.

Answer 2

The chance is pretty high.

specifically, 5.47% more likely to find sequences that start with an "A" rather than a "B", since "A" is that much more frequently used, and 55,727.55% more likely to find the sequence "ABA" than "BABA" - although sequences with multiple "A"s in a row will be more common than either.

Because

first, I was thinking that the chance would be 50% - after all, there are just two possibilities, A is first or B is first. But that's not right, it doesn't take letter frequency into account. So, looking up letter frequency, I found A is the third most common letter, while B is the 20th. The first eight letters take up 60% of the total usage, and the first twelve take up 85%. The third, eighth, and nineteenth most common letter pairs, include "A", while "B" doesn't even appear on the list. So, there's a very big gap between the two letters in both frequency and volume, and it is much more likely that any given sequence will start with "A", because it is a lot more "A"s will be found in the text.

So, onwards to specific calculations

the specific relative frequency of "A" is 8.167%, and the specific relative frequency of "B" is 1.492%. It is therefore 5.47 (maybeso rounded to five and a half) times as likely for A to occur rather than B. But wait, that's not all - we're looking for sequence "ABA" vs "BABA". Given it is five and a half times more likely for a letter to be "A" rather than "B", there should be 5.47% chance for the first "A", then .18% chance that "A" is followed by a "B", and 5.47% chance that B is followed by another A, giving .00054% chance of the sequence of "ABA". On the other hand, the sequence of "BABA" is even worse, with .00000000969% chance of the sequence. So you are 55,727.55 times more likely to find a sequence of "ABA" instead of "BABA". [note that "BAB" has a chance of .000000177%, making the sequence "ABA" only 3050.85% more likely than "BAB", making the extra letter in the sequence very expensive].

Bonus:

here is my answer in the same format as that book (more or less) - a. aaaa "A" aaa "B", "A"aa "ABA" a "BABA" a "A" aa. B aaabaaab "A" "B". Baaa. "A" "B". aa,aaa. aa "A", "B" aa. aabba, aaaa "A", baa "A" b. aaa a "A", a "B". (abaa) a "A" aa "B". Ba, aa "ABA" "BABA". aaaa "A" aa "B", a "A", aa "A" ba "B", aaa "B" ba "A", a "ABA". a "BABA" aaa "ABA" a "BABA". [a "BAB" aaaa "ABA" a "BAB", aa]. B: a