Abrazolica

A coin is tossed \(n\) times. What is the probability that the number of tails in the sequence never exceeds the number of heads?

The problem can be represented as a walk on the infinite state automaton shown in the figure below.

The start state is \(0\) and all states are end states. When the automaton is in state \(k\) there have been \(k\) more heads than tales.

We will solve the problem by finding the probability generating function. For that we need the generating function for the number of walks that start at state \(0\) and end at any of the states. Since this is an infinite automaton the usual approach of using the transition matrix or a regular expression will not work. We can however use a recursive regular expression for this problem. The following pair of expressions describe walks that start at state \(0\) and end at any state including \(0\).

\[\begin{align} S & = A+AhA+AhAhA+\cdots\nonumber\\ & = A(\epsilon+hA+hAhA+\cdots\nonumber\\ & = A(hA)^{*}\nonumber\\ A & = (hAt)^{*}\nonumber \end{align}\]

The regex \(A\) is for starting at a state, visiting any number of states to the right, and ending back at the starting state. The first term in the regex \(S\) represents starting and ending at state \(0\). The second term represents starting at \(0\) and ending at \(1\), and so on.

We get the generating function by converting these regular expressions into algebraic form. The generating function is

\[g(h,t) = \frac{A(h,t)}{1-hA(h,t)}\]

where \(A(h,t)\) is a solution of the following equation.

\[A(h,t) = \frac{1}{1-htA(h,t)}\]

The solution we want is

\[A(h,t) = \frac{1-\sqrt{1-4ht}}{2ht}\]

Substituting this into the expression for \(g(h,t)\) and simplifying, we get the following generating function

\[g(h,t) = \frac{2}{1-2h+\sqrt{1-4ht}}\]

The coefficient of \(h^{k}t^{l}\) in the power series expansion of this function is the number of coin toss sequences of length \(n=k+l\) that have \(k\) heads and \(l\) tails where the number of tails never exceeds the number of heads. To get the probability generating function, we make the substitutions \(h\rightarrow pz\), and \(t\rightarrow qz\) where \(p\) is the probability of heads, and \(q=1-p\) is the probability of tails. The probability generating function is then

\[\begin{align} f(p,z) & = g(pz,qz)\nonumber\\ & = \frac{2}{1-2pz+\sqrt{1-4pqz^{2}}}\nonumber \end{align}\]

The coefficient of \(z^n\) in the power series expansion of \(f(p,z)\) is the probability that in a sequence of \(n\) coin tosses, the number of tails never exceeds the number of heads. If you do the power series expansion you will notice that the probability for a sequence of length \(2m\), i.e. an even length sequence, is always equal to the probability for the sequence of length \(2m-1\). This is because for an odd length sequence, the number of heads must always be greater than the number of tails, so it can be extended by getting either a head or a tail. The probabilities for \(n=10,20,30\), respectively, are shown below and are plotted in the following figure.

\[14p^9-70p^8+135p^7-120p^6+42p^5\]

\[\begin{align} &-4862p^{19}+48620p^{18}-217360p^{17}+570570p^{16}-969969p^{15}+\nonumber\\ &1108536p^{14}-852720p^{13}+426360p^{12}-125970p^{11}+16796p^{10}\nonumber \end{align}\]

\[\begin{align} &2674440p^{29}-40116600p^{28}+280073300p^{27}-1206469600p^{26}+\nonumber\\ &3583214712p^{25}-7763631876p^{24}+12658095450p^{23}-15781521600p^{22}+\nonumber\\ &15123958200p^{21}-11090902680p^{20}+6129183060p^{19}-2476437600p^{18}+\nonumber\\ &691945800p^{17}-119759850p^{16}+9694845p^{15}\nonumber \end{align}\]

Probability that the number of tails never exceeds the number of heads in n=10, 20, 30 tosses of a coin as a function of p = probability of heads.