ON REACHING HEAD TO TAIL RATIOS FOR BALANCED AND UNBALANCED COINS

Tamás Lengyel Occidental College, Los Angeles, CA 90041, USA Abstract: Given a coin with head to tail probability ratio 1 to λ with integer λ ≥ 1. Let T denote the time it takes to reach the head to tail ratio r = q/(λq + m). We prove that the limit probability P (T < ∞) of ever reaching this ratio r is (λ + 1)/(m + λ + 1), as q → ∞ and q and m are co-primes. Asymptotic results for the conditional expected time E(T |T < ∞) and standard deviation σ(T |T < ∞) are also derived. A surprising aspect of the results is that these quantities are not continuous functions of the ratio r.

AMS classifications: 60C05, 05A15, 33C20 Keywords: combinatorial probability; hypergeometric functions; random walks

We flip a coin. Let X and Y denote the number of heads and tails, respectively. For a balanced coin it is well known that the probability of ever visiting the line Y = X − m is 1 for any integer m. For instance, if the line is reached when Y = n and X = n+m then the probability of this happening is P (Y = X − m = n) = \binom{2n+m}{n}/2^{2n+m}. It follows that the probability that the line Y = X − m is ever reached is 1 [2]. In fact, by binomial identities [3] we obtain

U_{m}(x) = ∑_{n=0}^{∞} \binom{2n + m}{n}x^{2n+m} = (\frac{1 − \sqrt{1 − 4x^{2}}}{2x} )^{m}/\sqrt{1 − 4x^{2}}

for |x| < 1/2. The generating function for the first return to equilibrium is F (x) = 1−\sqrt{1 − 4x^{2}}, hence we get U_{m}(x)(1−F (x)) = (\frac{1−\sqrt{1−4x^{2}}}{2x} )^{m} for the generating function of the first passage through m > 0. In particular, if x = 1/2 then this yields that the line Y = X−m will be reached with probability 1 for every finite integer m. Apparently, we can also derive the probability generating function, A_{m}(x), of the probability of the first passage through m > 0 occurring at flip n when the coin shows heads with probability h in a more direct way by applying the Catalan generating function C(x) = \frac{1−\sqrt{1−4x}}{2x}. In fact, A_{m}(x) = (hx)^{m}[C(h(1−h)x^{2})]^{m} holds, and it follows that \frac{m}{n} \binom{n}{\frac{n+m}{2}}h^{\frac{n+m}{2}} (1 − h)^{\frac{n−m}{2}} is the coefficient of x^{n}, n > 0. We might as well be interested in calculating the probability of reaching a given ratio instead of a difference. Of course, the probability of reaching ratio one (i.e., a difference of m = 0) is 1 for a balanced coin although the expected number of flips needed is infinite [2]. We study the probability of ever reaching a given (accumulated) head to tail ratio, q/p, different from 1 and given in lowest terms. We can assume that q < p as the ratios q/p and p/q can be 2 T. Lengyel

reached with the same probability for a balanced coin. We set h = 1/2, r = p+q and u(p, q) = ∑_{n=1}^{∞} \binom{rn}{qn}2^{−rn}. The probability of ever reaching the ratio q/p is w(p, q) = 1 − \frac{1}{1+u(p,q)}. Let gcd(q, m) denote the greatest common divisor of the positive integers q and m. Numerical evidence suggests that the second largest probability of reaching a ratio is around 2/3 showing a gap between 1 and the second largest probability. The limit probability of reaching the ratio \frac{q}{q+m} is \frac{2}{2+m} as q → ∞ and gcd(q, m) = 1 as showed by Theorem A([5]). For every fix m ≥ 1, we have lim_{q→∞} w(q + 1, q) = 2/3, and in general,

lim_{{q→∞ \atop gcd(q,m)=1}} w(q + m, q) = \frac{2}{2 + m}

for a balanced coin.

The proof is based on various approximation methods applied to sums involving binomial coefficients. A surprising aspect of this result is that the probability of reaching a given ratio is not a continuous function of the ratio. In fact, we can consider the ratios \frac{q}{q+1} and \frac{q}{q+2}, and select a sufficiently large odd q. The ratios can be set arbitrarily close yet the probabilities of reaching them will stay apart for w(q + 1, q) ≈ 2/3 and w(q + 2, q) ≈ 1/2. For an arbitrary (including an unbalanced) coin let h and t = 1 − h denote the probability of getting a head and a tail, respectively. The event that the number of tails equals λ times the number of heads is persistent (i.e., its probability is one) if and only if the head to tail probability ratio, h/t, is equal to 1/λ ([2]). Accordingly, we extend the study of the probability of reaching the ratio \frac{q}{λq+m} for any rational λ. Note that it is sufficient to consider integral values for λ. We extend Theorem A to coins with arbitrary head to tail probability ratios in Section 2. Some related problems concerning the time it takes to reach the targeted head to tail ratio are discussed in Section 3. We present a hypergeometric series based approach to the problems which enables us to do exact calculations in the last section.

2. The case of an arbitrary coin

Theorem A can be extended to unbalanced coins. We set p = λq + m and determine the asymptotic behavior of the probability of reaching the ratio \frac{q}{p} = \frac{q}{λq+m} in

Theorem 1. Given a coin with head to tail probability ratio 1 to λ with integer λ ≥ 1. For every fix integer m ≥ 1, the limit probability of reaching the ratio \frac{q}{λq+m} is \frac{λ+1}{m+λ+1} as q → ∞ provided gcd(q, m) = 1.

REACHING HEAD TO TAIL RATIOS FOR BALANCED AND UNBALANCED COINS 3

Note that this result is in agreement with Theorem A for λ = 1, i.e., for a balanced coin. The discontinuity phenomenon does not disappear but by increasing λ the limit probability approaches 1. The proof of Theorem 1 is a straightforward generalization of that of Theorem A [5]. We set r = q + p = (λ + 1)q + m and t_{n} = t_{n}(q, m, λ) = \binom{rn}{qn}(\frac{1}{λ+1})^{qn}(\frac{λ}{λ+1})^{pn}, and define the function U(x) = 1 + ∑_{n=1}^{∞} t_{n}x^{n}. Note that the condition on gcd(q, m) plays into the selection of binomial terms. By following [2], U(x) is closely related to the probability generating function, F (x), of the time T it takes to reach the given ratio q/p for the first time by identity

F (x) = 1 − 1/U(x).  (1)

(We can think of T that assumes ∞ when the ratio is never encountered in the course of a particular sequence of coin flips.) Clearly, we have F (x) = ∑_{n=0}^{∞} P (T = n) x^{n} and thus F (1) = P (T < ∞). We study various properties of T in Sections 3 and 4. In the proofs we approximate t_{n} to evaluate F (1), F′(1), and F ”(1).

\underline{Proof of Theorem 1.} We give only a sketch of the proof. Interested readers should consult the proof of Theorem A in [5] for similar details. The required probability is 1 − 1/(1 + ∑_{n=1}^{∞} t_{n}). We use the asymptotic identity [1]

\binom{(a + b)n}{an} ∼ \frac{(a + b)^{n(a+b)+1/2}}{a^{an+1/2}b^{bn+1/2}} \frac{1}{\sqrt{2πn}}, as n → ∞,  (2)

for positive integers a and b. Let c_{1}(q, m, λ, n) and c_{2}(q, m, λ, n) denote bounded functions of variables q, m, λ, and n. By identity (2) we obtain t_{n} = ((\frac{λ}{λ+1} \frac{r}{r−q} )^{r}(\frac{r−q}{λq} )^{q})^{n}× \sqrt{\frac{r}{2q(r−q)}} \sqrt{\frac{1}{nπ}} (1+c_{1}(q, m, λ, n)\frac{1}{qn}). Observe that (\frac{λ}{λ+1} \frac{r}{r−q} )^{r}(\frac{r−q}{λq} )^{q} = (1− \frac{m}{(λ+1)(λq+m)})^{r}(1+

\frac{m}{λq} )^{q} ∼ 1 − \frac{m^{2}}{2λ(λ+1)q} and \sqrt{\frac{r}{2q(r−q)}} ∼ \sqrt{\frac{λ+1}{2λ}} \frac{1}{\sqrt{q}} as q → ∞. Assume that q is large enough to

guarantee \frac{m^{2}}{2λ(λ+1)q} < 1. We set f(n) = \frac{1}{\sqrt{q}} ^{\frac{(1− \frac{m^{2}}{2λ(λ+1)q} )^{n}}{\sqrt{n}}}. It also follows that

t_{n} = \sqrt{\frac{λ + 1}{2λπ}}f(n)(1 + c_{2}(q, m, λ, n)\frac{1}{q}).

An integral equation for the gamma function [4] yields that for all α > −1

∫_{0}^{∞} xe^{−xv}v^{α}dv = \frac{1}{x^{α}} ∫_{0}^{∞} e^{−t}t^{α}dt = \frac{1}{x^{α}} Γ(α + 1).  (3)

By setting \frac{1}{s} = 1 − \frac{m^{2}}{2λ(λ+1)q} and x = ln s it follows that

∫_{0}^{∞} f(y)dy = ∫_{0}^{∞} \frac{1}{\sqrt{q}} \frac{e^{−y ln s}}{\sqrt{y}} dy = \frac{1}{\sqrt{q}} (ln s)^{−α−1}Γ(α + 1),  (4)

and in particular, we get \frac{1}{\sqrt{q}} (ln s)^{−1/2}\sqrt{π} for α = −1/2. Euler’s summation formula [4] can be applied to approximate ∑_{1≤k<n} f(k)

∑_{1≤k<n} f(k) = ∫_{1}^{n} f(y)dy − \frac{1}{2}(f(n) − f(1)) + ∫_{1}^{n} B_{1}(\{y\})f′(y)dy,  (5)

where B_{1}(y) = y −1/2 and {y} = y −⌊y⌋. Observe that f(n) = o(1) as n → ∞ and by identity (4), ∫_{0}^{∞} f′(y)dy = o( ∫_{0}^{∞} f(y)dy) for any α > −1 as q → ∞. The proof follows by identities (4) and (5), and noting that ln s ∼ \frac{m^{2}}{2λ(λ+1)q} and ∑_{n=1}^{∞} t_{n} ∼ \frac{λ+1}{m} as q → ∞.

3. Related problems

For a coin with head to tail probability ratio h/t = 1/λ, the probability of encountering the head to tail ratio 1 to λ is one and the expected time it takes is infinite [2]. On the other hand, to reach other ratios, e.g., \frac{q}{λq+m}, m ≥ 1, we get that the probability P (T < ∞) = F (1) ∼ \frac{λ+1}{m+λ+1} as q → ∞ by Theorem 1, thus it is possible to never encounter the given ratio. We restrict our investigations to cases where the event of encountering the ratio actually happens and determine the expected value and standard deviation of T provided T < ∞, i.e., we deal with E(T | T < ∞) and σ(T | T < ∞).

A related problem is to determine the expected number of times the given ratio is encountered. For this problem we consider the unconditional setting that is we include the possibility of no encounter. It turns out that this problem can be reduced to the calculation of F (1), for U(1) − 1 can be interpreted as the expected number of times that the given ratio is reached in infinitely many trials [2]. In fact, t_{n} can be viewed as the expected value of a random variable which equals 1 or 0 according to whether the ratio is or isn’t reached in the nth trial. We note that U(1) − 1 ∼ \frac{λ+1}{m} as q → ∞ by the proof of Theorem 1.

Theorem 2. Given a coin with head to tail probability ratio 1 to λ with integer λ ≥ 1. For every fix integer m ≥ 1, the conditional expected time it takes to reach the ratio \frac{q}{λq+m} is asymptotically equal to \frac{λ(λ+1)^{2}}{m(m+λ+1)} q^{2} as q → ∞ provided gcd(q, m) = 1. Its standard deviation is asymptotically equal to \frac{λ(λ+1)^{2}}{m(m+λ+1)} \sqrt{\frac{2m+λ+1}{m}} q^{2}.

REACHING HEAD TO TAIL RATIOS FOR BALANCED AND UNBALANCED COINS 5

Remark. If m = λ = 1 and q → ∞ then the expected time and its standard deviation are asymptotically equal to 4q^{2}/3 and 8q^{2}/3, respectively.

\underline{Proof of Theorem 2.} The proof is similar to that of Theorem 1 in which we calculated F (1) = 1 − 1/U(1). For F′(x) = U′(x)/U^{2}(x), the conditional expected value can be determined by taking

\frac{F′(1)}{F (1)} = \frac{1}{F (1)U^{2}(1)} ∑_{n=1}^{∞} ((λ + 1)q + m)nt_{n}.

Accordingly, we set f(n) = \frac{1}{\sqrt{q}} (1 − \frac{m^{2}}{2λ(λ+1)q} )^{n}((λ + 1)q + m)\sqrt{n}, α = 1/2, and keep the definition of s in identity (4). Note that \frac{U′(1)}{(λ+1)q+m} ∼ \sqrt{\frac{λ+1}{2λπ}} \frac{1}{\sqrt{q}} ( ln s)^{−3/2}Γ(3/2) ∼ \frac{λ(λ+1)^{2}q}{m^{3}} . The proof can be concluded by applying identities (4) and (5). The asymptotic relation for the standard deviation also follows by changing the exponent of n in the definition of f(n) and using (7).

4. Exact calculations

In the previous sections we used asymptotic estimations to determine the limit probability and the asymptotics of the expected time and its standard deviation of reaching a given ratio. In this section we use a generating function based method to exactly calculate these quantities. We note, however, that these methods do not seem to help in obtaining the limits given in Theorems 1 and 2. We can use generalized hypergeometric series to carry out some of the calculations. Although we derive the probability generating function, F (x), of reaching the given ratio in n steps for the first time implicitly only, hypergeometric transformations will enable us to calculate all relevant quantities in terms of hypergeometric series. In particular, the rules of differential calculus for hypergeometric series [3] come handy in determining derivatives of F (x) as the derivatives of hypergeometric series can be expressed in terms of other hypergeometric series. We note that the underlying hypergeometric series are convergent in the applied cases.

A large class of sums can be expressed as hypergeometric series in a canonical way. In particular, hypergeometric series have great relevance in dealing with sums involving binomial coefficients and binomial coefficient identities. Recent developments regarding symbolic and algebraic manipulations of indefinite and definite sums of hypergeometric terms might offer surprising simplifications for these sums.

6 T. Lengyel

Example. We study the problem of reaching the head to tail ratio 1/2 for a balanced coin. We set U(x) = 1 + ∑_{n=1}^{∞} \binom{3n}{n}(\frac{x}{2})^{3n} to obtain the probability generating function F (x) = 1 − 1/U(x). For the conditional distribution of T we get P (T = n | T < ∞) = P (T = n)/F (1), and for the conditional expected time

E(T | T < ∞) = \frac{F′(1)}{F (1)} = \frac{U′(1)}{U(1)(U(1) − 1)}.  (6)

We take E(T^{2} | T < ∞) = ∑_{n=0}^{∞} n^{2}P (T = n | T < ∞) which can be computed by applying the identity ∑_{n=0}^{∞} n^{2}P (T = n | T < ∞) x^{n} = (x^{2}F ”(x) + xF′(x))/F (1). This implies that

σ(T | T < ∞) = \sqrt{\frac{F ”(1) + F′(1)}{F (1)} − (\frac{F′(1)}{F (1)})^{2}}  (7)

for its standard deviation. We can rewrite the binomial sum U(x) in its hypergeometric form. The term t_{n} = \binom{3n}{n}(\frac{x}{2})^{3n} is hypergeometric in n, for t_{n+1}/t_{n} = \frac{(3n+3)(3n+2)(3n+1)}{(2n+2)(2n+1)(n+1)}(\frac{x}{2})^{3} = \frac{3^{3}}{2^{2}} (\frac{x}{2})^{3} \frac{(n+ \frac{1}{3} )(n+ \frac{2}{3} )}{(n+ \frac{1}{2} )(n+1)} is a rational function of n. Thus

U(x) = _{2}F_{1}[ \begin{matrix}1/3, 2/3 \\ 1/2 \end{matrix} |(\frac{x}{2})^{3} \frac{3^{3}}{2^{2}} ] = \frac{cos (\frac{1}{3} arcsin(\frac{3}{4} \sqrt{\frac{3}{2}x^{3}}))}{\sqrt{1 − \frac{27 x^{3}}{32}}}.  (8)

It follows that the probability of reaching the ratio 1/2 is

1 − (_{2}F_{1}[ \begin{matrix}1/3, 2/3 \\ 1/2 \end{matrix} |\frac{1}{2^{3}} \frac{3^{3}}{2^{2}} ])^{−1} = 1 − (4 \sqrt{\frac{2}{5}} cos (\frac{1}{3} arcsin(\frac{3}{4} \sqrt{\frac{3}{2}})))^{−1} ≈ .573.

We also obtain 5.683 for the expected time by (6) and (8), and 5.976 for the standard deviation by (7). Note that U(1) − 1 ≈ 1.342 implies that the ratio 1/2 is reached 1.342 times on the average.

In some special cases, similar to the one in the Example, the hypergeometric series can be converted into other functions often involving simplifications and simple or special functions. In general, the theory of hypergeometric summations might offer further insight in terms of closed forms. Unfortunately, the sum ∑_{n=1}^{N} t_{n} can not be expressed as a linear combination of a fixed number of hypergeometric terms according to Gosper’s algorithm [6]. It does not exclude the possibility of conversion to special functions, yet for more involved examples it might be difficult to find a simple form for U(x). However, we can use a simplification to avoid direct differentiation seen in the Example. This is accomplished by the following REACHING HEAD TO TAIL RATIOS FOR BALANCED AND UNBALANCED COINS 7

Theorem B ([3]).

\frac{d}{dx}(_{p}F_{q}[ \begin{matrix}a_{1}, a_{2}, … a_{p} \\ b_{1}, b_{2}, … b_{q} \end{matrix} |x] ) = \frac{∏_{i=1}^{p} a_{i}}{∏_{j=1}^{q} b_{j}} _{p}F_{q}[ \begin{matrix}a_{1} + 1, a_{2} + 1, … a_{p} + 1 \\ b_{1} + 1, b_{2} + 1, … b_{q} + 1 \end{matrix} |x] .

The actual calculations in order to determine P (T < ∞), E(T | T < ∞), and σ(T | T < ∞) can be carried out by applying Theorem 3 to (1), (6), and (7) with x = 1.

Theorem 3. Given a coin with head to tail probability ratio 1/λ with integer λ ≥ 1. We set p = λq + m with an integer m (m ≥ 1 and gcd(q, m) = 1), c = (\frac{1}{λ+1})^{q}(\frac{λ}{λ+1})^{p}, and d = c \frac{(q+p)^{q+p}}{q^{q}p^{p}}. The probability generating function, F (x), of reaching the ratio q/p in n steps for the first time is F (x) = 1 − 1/U(x) with hypergeometric series

U(x) = _{q+p−1}F_{q+p−2}[ \begin{matrix}\frac{1}{q+p}, …, \frac{q+p−1}{q+p} \\ \frac{1}{q}, …, \frac{q−1}{q}, \frac{1}{p}, …, \frac{p−1}{p} \end{matrix} |d x^{q+p}] .

We also have

U′(x) = x^{q+p−1}(q + p)c\binom{q + p}{q}_{q+p−1}F_{q+p−2}[ \begin{matrix}\frac{1}{q+p} + 1, …, \frac{q+p−1}{q+p} + 1 \\ \frac{1}{q} + 1, …, \frac{q−1}{q} + 1, \frac{1}{p} + 1, …, \frac{p−1}{p} + 1 \end{matrix} |d x^{q+p}]

and

\begin{matrix}U”(x) = (q + p − 1)\frac{U′(x)}{x}+ \\ x^{2(q+p−1)}2(q + p)^{2}c\binom{2(q + p)}{2q}_{q+p−1}F_{q+p−2}[ \begin{matrix}\frac{1}{q+p} + 2, …, \frac{q+p−1}{q+p} + 2 \\ \frac{1}{q} + 2, …, \frac{q−1}{q} + 2, \frac{1}{p} + 2, …, \frac{p−1}{p} + 2 \end{matrix} |d x^{q+p}] . \end{matrix}

Note that all these hypergeometric series have radii of convergence exceeding one. We omit the proof of Theorem 3 which is a straightforward application of Theorem B and binomial identities.

References

[1] Comtet, L. (1974). Advanced Combinatorics, D. Reidel, Dordrecht

[2] Feller, W. (1968). An Introduction to Probability Theory and Its Applications, vol. I, Wiley, 3rd edition, New York–London

[3] Graham, R. L., D. E. Knuth, and O. Patashnik (1994). Concrete Mathematics, Addison-Wesley, 2nd edition, Reading, MA

[4] Knuth, D. E. (1973). The Art of Computer Programming, vol. 1, Addison-Wesley, Reading, MA, 2nd edition

[5] Lengyel, T. (1995). On the probability of reaching a given head to tail ratio. J. Combin. Inform. System Sci. 20, 273–278.

[6] Petkovšek, M., H. S. Wilf, and D. Zeilberger (1996). A = B, A. K. Peters, Wellesley, MA