THE KERNEL METHOD: A COLLECTION OF EXAMPLES

HELMUT PRODINGER

Abstract. The kernel method has recently become quite popular. Roughy speaking, in certain cases one obtains for a multivariate generating function a functional equation. For certain couplings of the variables, the denominator vanishes, but since one knows a priori that a power series expansion exists, one concludes that the numerator must also vanish. This is sufficient to compute the generating function, at least at special values, and subsequently in general.

We present a collection of examples where this technique works. All of them have a certain random walk flavour.

I am very glad of having been an invited speaker at SLC50. I presented many examples, related to my own work. I had prepared some examples about the kernel method, but no time to talk about them. Since this subject is dear to my heart, I extended that section and present these examples here.

1. Introduction

In my view, the kernel method originated in Knuth’s book [9], where it was presented as an innocent exercise 2.2.1.-4. Later, it was turned into a method in [1]. It was probably rediscovered independently by many people; I recommend to follow the references in [1].

I feel that I cannot do anything better as an introduction than to reproduce Knuth’s original exercise. One starts at the origin, and can advance from (n, i) to both (n + 1, i ± 1), except in the case when i = 0, when one can only go to (n + 1, 1). In this way, one models nonnegative lattice paths (or random walks). One wants to know how many paths lead from the origin to (n, 0), and, more generally, to (n, i). Clearly, this is a very classical subject, but the derivation that Knuth presented is the subject of this note. One uses generating functions f_{i}(z), describing walks leading to (n, i); the coefficient of z^{n}, denoted by [z^{n}]f_{i}(z), is the number of walks from the origin to (n, i). The following recursions are immediate:

f_{i}(z) = zf_{i−1}(z) + zf_{i+1}(z),  i ≥ 1,
f_{0}(z) = 1 + zf_{1}(z).

Now one introduces F (z, x) = ∑_{n≥0} f_{n}(z)x^{n}, multiplies the recursion by x^{i} and sums:

F (z, x) − f_{0}(z) = zxF (z, x) + \frac{z}{x}[F (z, x) − f_{0}(z) − xf_{1}(z)],

or

F (z, x) = zxF (z, x) + \frac{z}{x}[F (z, x) − F (z, 0)] + 1,

Key words and phrases. Kernel method, generating function, random walk, bin packing, toilet paper problem, card guessing, binary tree, functional equation, Banach’s match box problem.

whence

F (z, x) = \frac{zF (z, 0) − x}{zx^{2} − x + z}.

Plugging in x = 0 leads to nothing, but the denominator factors as z(x − r_{1}(z))(x − r_{2}(z)), with

r_{1,2}(z) = \frac{1 ∓ \sqrt{1 − 4z^{2}}}{2z} .

Note that x − r_{1}(z) ∼ x − z as x, z → 0. Therefore the factor 1/(x − r_{1}(z)) has no power series expansion around (0, 0), but F (z, x) has, so this “bad” factor must actually disappear, i.e., (x − r_{1}(z)) must be a factor of the numerator as well, which leads to the equation zF (z, 0) = r_{1}(z), from which F (z, 0) can be computed. Consequently, F (z, x) is then also explicitly computed, and the factor (x − r_{1}(z)) can be cancelled from both, numerator and denominator.

From this, one finds for instance that [z^{2n}]F (z, 0) = \frac{1}{n+1} \binom{2n}{n}, a well-known Catalan number, and similar expressions for [z^{n}x^{i}]F (z, x), for n ≡ i mod 2. A technique to read off coefficients like this will be described in subsequent sections for numerous examples.

Now since I find this method fascinating, simple, and extremely useful, I tried during the last few years to collect several examples where its works. In the present paper, which can thus be seen partially as a tutorial, I present them. It is my ambitious wish that it might be useful for seminars and other courses. I rederive some known results with the kernel method but also try to work out a few new ones.

The first one (Section 2) considers random walks originating from a bin packing problem. It was originally considered by Knödel^{1}. There are bins of size 1 and randomly arriving objects of size \frac{i}{d}, for i = 1, …, d − 1, and an online strategy to fill the bins as well as possible. The problem can be described by states, coding the partially filled bins at a specific moment. We treat the instances d = 3, 4. Higher values of d lead to very complicated situations and I am not aware of any results in these cases.

The next one (Section 3) looks again at the toilet paper problem, a popular subject introduced by Knuth [10]. He considers two rolls of tissues, with m resp. n units, and random users, who are with probability p big-choosers (taking one unit from the larger roll) resp. with probability q = 1 − p little-choosers (taking one unit from the smaller roll). The parameter of interest is the (average) number of units remaining on the larger roll, when the smaller one became empty.

The following Section 4 considers walk on the comb, a theme studied by D. Bertacchi^{2} in several papers [3, 2]. The walk is on ℤ × ℤ, and from (i, j), j ≠ 0, one can reach (i, j ±1), both with probability \frac{1}{2}. If j = 0, however, one can reach (i±1, 0), (i, ±1) all with probability \frac{1}{4}. One wants generating functions f_{i,j}(z), describing all walks from the origin to (i, j). We employ the kernel method to derive the simpler generating functions ϕ_{j}(z) describing walks from the origin to (∗, j), i. e., ignoring the first coordinate. This means now a random walk on ℤ, as usual, but with different rules for 0: if one is in 0, one can stay there with probability \frac{1}{2}.

1The austrian mathematician Walter Knödel received his Ph. D. under E. Hlawka in Vienna. He eventually became a professor in Stuttgart, Germany.

2Daniela Bertacchi got her Ph. D. under Wolfgang Woess in Milano; like me, she is a frequent visitor of the Technical University Graz.

The next three sections deal with subjects that I published already in [11, 8, 15]. To extend this collection of examples, I repeat (parts of) them here.

Section 5 considers a recursion that occurs when one analyzes a certain procedure to generate binary trees. The kernel method solves it readily.

Section 6 reviews a card guessing game with a certain random walk flavour.

Section 7 deals with a functional equation from a queuing system.

Finally, I deal with Banach’s match box problem, see [6]. The relevant recursions somehow resemble the ones in the card guessing game. Knuth’s toilet paper problem may be seen as an extension of Banach’s match box problem, although only expectations were considered in the toilet paper problem.

2. Knödel walks

Knödel [7] formulated a simple bin packing model as a random walk on a special graph:

Some aspects of the analysis were treated by Prodinger in a series of papers [12, 13, 14]. Recently, Drmota [4] has picked up the subject again.

In the simplest version, there are bins of size 1, and items of size \frac{1}{3} resp. \frac{2}{3} arriving at random. One tries to complete as many bins as possible with an online strategy, leaving us basically with a number of bins filled \frac{2}{3}, which we reduce by 1 or augment by 1. In the initial situation, there is a special “state” β, representing a bin filled \frac{1}{3}.

Here, we want to find the bivariate generating function related to the number of steps taken and the state where the random walk currently is. From this, one can get the wasted space: State 0 contributes 0, state β contributes 2/3, and state i for i ≥ 1 contributes i/3.

Random walks in this graph, starting at state 0 will be called “Knödel walks,” in honour of their creator.

Let f_{i}(z) be the generating function, where [z^{n}]f_{i}(z) counts all Knödel walks starting at 0 and ending at state i in n steps, for i ∈ {β, 0, 1, …}. We have the following recursions:

\begin{aligned}f_{i}(z) & = zf_{i−1}(z) + zf_{i+1}(z),  for i ≥ 2, \\ f_{1}(z) & = zf_{0}(z) + zf_{β}(z) + zf_{2}(z), \\ f_{0}(z) & = 1 + zf_{1}(z) + zf_{β}(z), \\ f_{β}(z) & = zf_{0}(z). \end{aligned}  (2.1)

We introduce the bivariate generating function F (z, x) = ∑_{i≥0} f_{i}(z)x^{i} and get from summing up (2.1)

F (z, x) = ∑_{i≥2} x^{i}zf_{i−1}(z) + ∑_{i≥2} x^{i}zf_{i+1}(z)
+ xzf_{0}(z) + xzf_{β}(z) + xzf_{2}(z) + 1 + zf_{1}(z) + zf_{β}(z)

= xzF (z, x) + \frac{z}{x}F (z, x) + 1 − \frac{z}{x}f_{0}(z) + (1 + x)zf_{β}(z)

= xzF (z, x) + \frac{z}{x}F (z, x) + 1 − (\frac{z}{x} − (1 + x)z^{2})F (z, 0),

or

F (z, x) = \frac{z(1 − x(1 + x)z)F (z, 0) − x}{x^{2}z − x + z} = \frac{z(1 − x(1 + x)z)F (z, 0) − x}{z(x − r_{1}(z))(x − r_{2}(z))},

with

r_{1}(z) = \frac{1 − \sqrt{1 − 4z^{2}}}{2z} , r_{2}(z) = \frac{1 + \sqrt{1 − 4z^{2}}}{2z} .

Now x − r_{1}(z) must be a factor of the numerator, so we find

z(1 − zr_{1}(z)(1 + r_{1}(z)))F (z, 0) − r_{1}(z) = 0

or

f_{0}(z) = F (z, 0) = \frac{r_{1}(z)}{z(1 + z)(1 − r_{1}(z))}.

Therefore

F (z, x) = \frac{r_{1}(z)}{z(1 + z)(1 − r_{1}(z))} \frac{1 + xzr_{1}(z)}{1 − xr_{1}(z)}.

From this we get for i ≥ 1

f_{i}(z) = \frac{r_{1}^{i+1}(z)}{z(1 − r_{1}(z))}.

We also have

f_{β}(z) = zf_{0}(z) = \frac{r_{1}(z)}{(1 + z)(1 − r_{1}(z))}

and find as a check that

f_{β}(z) + ∑_{i≥0} f_{i}(z) = \frac{1}{1 − 2z} ,

as it should.

To extract coefficients, we use Cauchy’s integral formula:

[z^{n}]F (z) = \frac{1}{2πi} ∮ \frac{dz}{z^{n+1}} H(z)

and the substitution z = \frac{v}{1 + v^{2}} , dz = dv \frac{1 − v^{2}}{(1 + v^{2})^{2}} .

For an arbitrary generating function H(z) we have

[z^{n}]H(z) = [v^{n}](1 − v^{2})(1 + v^{2})^{n−1}H(z(v)).

And so

[z^{n}]f_{i}(z) = [v^{n}](1 − v^{2})(1 + v^{2})^{n−1} \frac{v^{i}(1 + v^{2})}{1 − v}

= [v^{n−i}](1 + v)(1 + v^{2})^{n} = \binom{n}{⌊\frac{n−i}{2}⌋}

and further

[z^{2n}] ∑_{i≥1} f_{i}(z) = 2 ∑_{i≥1} \binom{2n}{n − i} = 2^{2n} − \binom{2n}{n},

[z^{2n+1}] ∑_{i≥1} f_{i}(z) = 2 ∑_{i≥0} \binom{2n + 1}{n − i} − \binom{2n + 1}{n} = 2^{2n+1} − \binom{2n + 1}{n}.

Hence

[z^{n}](f_{0}(z) + f_{β}(z)) = [z^{n}](1 + z)f_{0}(z) = \binom{n}{⌊\frac{n}{2}⌋}.

So

[z^{n}]f_{0}(z) = ∑_{k=0}^{n} \binom{k}{⌊\frac{k}{2}⌋}(−1)^{n−k},

or

[z^{2n}]f_{0}(z) = ∑_{k=0}^{n−1} \binom{2k + 1}{k},

[z^{2n+1}]f_{0}(z) = \binom{2n + 1}{n} − 1 − ∑_{k=0}^{n−1} \binom{2k + 1}{k}.

These formulæ evaluate [z^{n}]f_{k}(z) for any n and any state k.

Knödel walks related to \frac{1}{4}, \frac{2}{4}, \frac{3}{4}. The next model is related again to bins of size 1 and random items of size \frac{i}{4}, for i = 1, 2, 3. This time one finds two infinite sequences of states, representing i bins filled \frac{3}{4} resp. representing i bins filled \frac{3}{4} and one bin filled \frac{1}{2}.

Here is the corresponding graph.

Now we move to generating functions: f_{i}(z) represents i bins, \frac{3}{4} full, and g_{i}(z) represents i bins, \frac{3}{4} full and one bin filled \frac{1}{2}. The special h(z) represents one bin, \frac{1}{4} full.

The equations are

f_{0}(z) = 1 + zf_{1}(z) + zg_{0}(z) + zh(z),
g_{0}(z) = zf_{0}(z) + zg_{1}(z) + zh(z),
f_{1}(z) = zf_{0}(z) + zf_{2}(z) + zg_{0}(z) + zg_{1}(z) + zh(z),
f_{i}(z) = zf_{i−1}(z) + zf_{i+1}(z) + zg_{i}(z),  i ≥ 2,
g_{i}(z) = zg_{i−1}(z) + zg_{i+1}(z) + zf_{i}(z),  i ≥ 1,
h(z) = zf_{0}(z).

6 H. PRODINGER

With F (z, x) = ∑_{i≥0} f_{i}(z)x^{i}, G(z, x) = ∑_{i≥0} g_{i}(z)x^{i}, we find

F (z, x) = 1 + zxF (z, x) + \frac{z}{x}F (z, x) − \frac{z}{x}f_{0}(z) + zG(z, x) + zxg_{0}(z) + z(1 + x)h(z),
G(z, x) = zF (z, x) + zxG(z, x) + \frac{z}{x}G(z, x) − \frac{z}{x}g_{0}(z) + zh(z).

Set A(z, x) = F (z, x) + G(z, x):

A(z, x) = 1 + zxA(z, x) + \frac{z}{x}A(z, x) − \frac{z}{x}(f_{0}(z) + g_{0}(z)) + zA(z, x)
+ zxg_{0}(z) + z^{2}(2 + x)f_{0}(z),

thus

A(z, x) = \frac{1 − \frac{z}{x}(f_{0}(z) + g_{0}(z)) + zxg_{0}(z) + z^{2}(2 + x)f_{0}(z)}{1 − zx − \frac{z}{x} − z}.

Define

r_{1,2}(z) = \frac{1 − z ∓ \sqrt{1 − 2z − 3z^{2}}}{2z} .

The numerator must disappear for x = r_{1}(z), which leads to

1 − \frac{z}{r_{1}(z)}(f_{0}(z) + g_{0}(z)) + zr_{1}(z)g_{0}(z) + z^{2}(2 + r_{1}(z))f_{0}(z) = 0.

Similarly, set B(z, x) = F (z, x) − G(z, x):

B(z, x) = 1 + zxB(z, x) + \frac{z}{x}B(z, x) − \frac{z}{x}(f_{0}(z) − g_{0}(z)) − zB(z, x)
+ zxg_{0}(z) + z^{2}xf_{0}(z),

thus

B(z, x) = \frac{1 − \frac{z}{x}(f_{0}(z) − g_{0}(z)) + zxg_{0}(z) + z^{2}xf_{0}(z)}{1 − zx − \frac{z}{x} + z}.

The numerator must disappear for x = −r_{1}(−z), thus

1 + \frac{z}{r_{1}(−z)}(f_{0}(z) − g_{0}(z)) − zr_{1}(−z)g_{0}(z) − z^{2}r_{1}(−z)f_{0}(z) = 0.

Now we have two equations and can compute the functions f_{0}(z) and g_{0}(z):

f_{0}(z) = \frac{r_{1}(z) − r_{1}(−z) + r_{1}^{2}(z)r_{1}(−z) + r_{1}(z)r_{1}^{2}(−z)}{z(2 − 2zr_{1}(z) − (1 + z)r_{1}^{2}(z) + (1 − z)r_{1}^{2}(−z) − 2zr_{1}(z)r_{1}^{2}(−z))}

= 1 + 3z^{2} + 3z^{3} + 15z^{4} + 28z^{5} + 101z^{6} + 230z^{7} + 763z^{8} + 1882z^{9} + ⋯,

g_{0}(z) = \frac{r_{1}(z) + r_{1}(−z) − 2zr_{1}(z)r_{1}(−z) − zr_{1}^{2}(z)r_{1}(−z) − zr_{1}(z)r_{1}^{2}(−z)}{z(2 − 2zr_{1}(z) − (1 + z)r_{1}^{2}(z) + (1 − z)r_{1}^{2}(−z) − 2zr_{1}(z)r_{1}^{2}(−z))}

= z + z^{2} + 5z^{3} + 9z^{4} + 33z^{5} + 73z^{6} + 245z^{7} + 593z^{8} + 1921z^{9} + · · · .

The expressions for F (z, x) and G(z, x), although known in principle, become quite messy, so we don’t give them here. However, we want to compute the average wasted space after n steps. For this, we need

∑_{i≥0} \frac{i}{4}f_{i}(z) + ∑_{i≥0} (\frac{i}{4} + \frac{1}{2})g_{i}(z) + \frac{3}{4}h(z),

which we get as

\frac{1}{4} \frac{∂F}{∂x} (z, 1) + \frac{1}{4} \frac{∂G}{∂x}(z, 1) + \frac{1}{2}G(z, 1) + \frac{3}{4}zf_{0}(z).

Computer algebra can generate and expression equivalent to this which is not nice, but we give its local expansion around the dominant singularity, z = \frac{1}{3}:

\frac{\sqrt{3}}{12}(1 − 3z)^{−3/2} + (\frac{1}{8} + \frac{\sqrt{3}}{24})(1 − 3z)^{−1} + ⋯,

whence we get for the average wasted W_{n} space using singularity analysis of generating functions [5]

W_{n} = \frac{\sqrt{3}}{6}\sqrt{\frac{n}{π}} + \frac{1}{8} + \frac{\sqrt{3}}{24} + O(n^{−1/2}),

with more terms being available if necessary. (There is also a singularity at z = −\frac{1}{3}, but it contributes only terms of order n^{−1/2}.)

3. The toilet paper problem

Following the description in the introduction, let m be the number of units on the larger, and n on the smaller roll; M_{m,n} is the expected number of units left on the larger roll, when the smaller one becomes empty.

The recursions are

M_{m,0} = m,
M_{m,m} = M_{m,m−1},  m ≥ 1,
M_{m,n} = pM_{m−1,n} + qM_{m,n−1},  m > n > 0.

Define

F_{0}(z) = ∑_{m≥0} M_{m,m}z^{m}, F_{1}(z) = ∑_{m≥1} M_{m,m−1}z^{m}.

Note that

F_{0}(z) = ∑_{m≥0} M_{m,m}z^{m} = ∑_{m≥1} M_{m,m−1}z^{m} = F_{1}(z).

Define

F (z, x) = ∑_{m≥n≥0} M_{m,n}z^{m}x^{m−n}.

Then, by summing up,

F (z, x) = ∑_{m>n>0} M_{m,n}z^{m}x^{m−n} + ∑_{m>0} M_{m,0}z^{m}x^{m} + ∑_{m≥0} M_{m,m}z^{m}

= ∑_{m>n>0}[pM_{m−1,n} + qM_{m,n−1}]z^{m}x^{m−n} + \frac{zx}{(1 − zx)^{2}} + F_{0}(z)

= pzx ∑_{m−1≥n>0} M_{m−1,n}z^{m−1}x^{(m−1)−n} + \frac{q}{x} ∑_{m>n>0} M_{m,n−1}z^{m}x^{m−(n−1)}

+ \frac{zx}{(1 − zx)^{2}} + F_{0}(z)

= pzx[F (z, x) − ∑_{m≥0} M_{m,0}z^{m}x^{m}] + \frac{q}{x} ∑_{m>>n≥0} M_{m,n}z^{m}x^{m−n} + \frac{zx}{(1 − zx)^{2}} + F_{0}(z)

= pzx[F (z, x) − \frac{zx}{(1 − zx)^{2}} ] + \frac{q}{x}[F (z, x) − x ∑_{n≥0} M_{n+1,n}z^{n+1} − ∑_{n≥0} M_{n,n}z^{n}]

+ \frac{zx}{(1 − zx)^{2}} + F_{0}(z)

= pzxF (z, x) + \frac{q}{x}[F (z, x) − xF_{1}(z) − F_{1}(z)] + \frac{zx(1 − pzx)}{(1 − zx)^{2}} + F_{1}(z).

(Here, we used the ad hoc notation a >> b :⇔ a − b ≥ 2.) Solving,

F (z, x) = \frac{\frac{zx(1−pzx)}{(1−zx)^{2}} + F_{1}(z)[1 − q − q/x]}{1 − pzx − q/x} = \frac{F_{1}(z)[q − px] − \frac{zx^{2}(1−pzx)}{(1−zx)^{2}}}{pzx^{2} − x + q}

= \frac{F_{1}(z)[q − px] − \frac{zx^{2}(1−pzx)}{(1−zx)^{2}}}{pz(x − r_{1}(z))(x − r_{2}(z))} ,

with

r_{1,2}(z) = \frac{1 ∓ \sqrt{1 − 4pqz}}{2pz} .

Therefore, for x = r_{1}(z), the numerator must vanish, yielding

F_{1}(z)[q − pr_{1}(z)] − \frac{zr_{1}^{2}(z)(1 − pzr_{1}(z))}{(1 − zr_{1}(z))^{2}} = 0,

or

F_{1}(z) = \frac{zr_{1}^{2}(z)(1 − pzr_{1}(z))}{(q − pr_{1}(z))(1 − zr_{1}(z))^{2}} = \frac{z}{q(1 − z)^{2}} (q − C(pqz)),

with

C(z) = \frac{1 − \sqrt{1 − 4z}}{2} .

Note that r_{1}(z) = \frac{C(pqz)}{pz} and that 1/r_{2}(z) = r_{1}(z)pz/q.

The expression for F (z, x) is ugly, but we can extend Knuth’s asymptotic analysis to M_{m,m−n} for m → ∞ and fixed n; the instance n = 0 was given in [10].

For q < p, Knuth has shown that the local expansion of C(z) around z = 1 starts like

q + (p − q)(\frac{pq}{(p−q)^{2}} (z − 1) + \frac{(pq)^{2}}{(p−q)^{4}} (z − 1)^{2} + ⋯).

Hence the local expansion of F (z, x) around z = 1 starts like

\frac{1}{1 − z} · \frac{p}{(2p − 1)(1 − x)} + · · · .

So M_{m,m−n} = p/(2p − 1) + O(r^{m}), and the n plays no role here. Well, this is intuitive, the big-choosers dominate, so it does not really make a difference whether the second roll is slightly smaller. Now let us assume that p < q. Then F (z, x) starts like

\frac{1}{(1 − z)^{2}} · \frac{2p − 1}{(p − 1)(1 − x)} + \frac{1}{1 − z} [ − \frac{1}{1 − x} + \frac{p}{q(1 − x)^{2}} − \frac{p(1 − p)}{(2p − 1)(q − px)}] + · · · .

The coefficient of z^{m} is asymptotic to

(m + 1) · \frac{2p − 1}{(p − 1)(1 − x)} + [ − \frac{1}{1 − x} + \frac{p}{q(1 − x)^{2}} − \frac{p(1 − p)}{(2p − 1)(q − px)}].

And the coefficient of x^{n} (n fixed) in this is

(m + 1) · \frac{2p − 1}{p − 1} + [ − 1 + \frac{p}{q}(n + 1) − \frac{p}{2p − 1}(\frac{p}{q})^{n}],

or

m · \frac{1 − 2p}{q} + \frac{pn}{q} + \frac{p}{1 − 2p}(\frac{p}{q})^{n},

For n = 0, we find again Knuth’s value \frac{q−p}{q}m + \frac{p}{q−p}. Perhaps it is not very intuitive at the first glance why this grows with n. However, for larger n, the process tends to be over more quickly, and so more will be left on the large roll.

Now let us discuss the case p = q. Then

C(pqz) = \frac{1}{2} − \frac{1}{2}\sqrt{1 − z},

and

F (z, x) ∼ (1 − z)^{−3/2} · \frac{1}{1 − x} − (1 − z)^{−1/2} · \frac{1 − 2x}{(1 − x)^{3}} ,

and the coefficient of z^{m} behaves like

[2\sqrt{\frac{m}{π}} + \frac{3}{4\sqrt{πm}}] · \frac{1}{1 − x} − \frac{1}{\sqrt{πm}} · \frac{1 − 2x}{(1 − x)^{3}} .

Furthermore the coefficient of x^{n} (n fixed) in this is

2\sqrt{\frac{m}{π}} + \frac{3}{4\sqrt{πm}} + \frac{1}{\sqrt{πm}} · \frac{(n + 1)(n − 2)}{2}.

For n = 0 we find again

2\sqrt{\frac{m}{π}} − \frac{1}{4\sqrt{πm}}.

Again, since everybody takes at random, the process tends to be over more quickly, leaving more on the other roll.

4. Walks on a comb

As explained in the introduction, we walk on the integers as described in the following graph.

10 H. PRODINGER

One derives recursions for the probability generating functions immediately:

ϕ_{0}(z) = 1 + \frac{z}{2}(ϕ_{−1}(z) + ϕ_{1}(z)) + \frac{z}{2}ϕ_{0}(z),
ϕ_{1}(z) = \frac{z}{4}ϕ_{0}(z) + \frac{z}{2}ϕ_{2}(z),
ϕ_{i}(z) = \frac{z}{2}(ϕ_{i−1}(z) + ϕ_{i+1}(z)),  i ≥ 2,
ϕ_{−i}(z) = ϕ_{i}(z).

Now set

F (z, x) = ∑_{i≥0} x^{i}ϕ_{i}(z).

As a check, we should have 2F (z, 1) − F (z, 0) = \frac{1}{1−z}.

Summing, we get

F (z, x) = 1 + zϕ_{1}(z) + \frac{z}{2}ϕ_{0}(z) + x\frac{z}{4}ϕ_{0}(z) + x\frac{z}{2}ϕ_{2}(z) + ∑_{i≥2} x^{i} \frac{z}{2}(ϕ_{i−1}(z) + ϕ_{i+1}(z))

= (1 − \frac{z}{2})ϕ_{0}(z) + \frac{z}{2}ϕ_{0}(z) + x\frac{z}{4}ϕ_{0}(z) + x\frac{z}{2}ϕ_{2}(z) + \frac{zx}{2} ∑_{i≥1} x^{i}ϕ_{i}(z) + \frac{z}{2x} ∑_{i≥3} x^{i}ϕ_{i}(z)

= ϕ_{0}(z) + \frac{zx}{4}ϕ_{0}(z) + \frac{zx}{2}[F (z, x) − ϕ_{0}(z)] + \frac{z}{2x}[F (z, x) − ϕ_{0}(z) − xϕ_{1}(z)].

Therefore

F (z, x)[1 − \frac{zx}{2} − \frac{z}{2x}] = ϕ_{0}(z) + \frac{zx}{4}ϕ_{0}(z) − \frac{zx}{2}ϕ_{0}(z) − \frac{z}{2x}ϕ_{0}(z) − \frac{z}{2}ϕ_{1}(z)

= ϕ_{0}(z) − \frac{zx}{4}ϕ_{0}(z) − \frac{z}{2x}ϕ_{0}(z) − \frac{1}{2}(1 − \frac{z}{2})ϕ_{0}(z) + \frac{1}{2}

and

F (z, x) = ϕ_{0}(z) + \frac{zx}{4}ϕ_{0}(z) − \frac{zx}{2}ϕ_{0}(z) − \frac{z}{2x}ϕ_{0}(z) − \frac{z}{2}ϕ_{1}(z)

= \frac{ϕ_{0}(z) − \frac{zx}{4}ϕ_{0}(z) − \frac{z}{2x}ϕ_{0}(z) − \frac{1}{2}(1 − \frac{z}{2})ϕ_{0}(z) + \frac{1}{2}}{1 − \frac{zx}{2} − \frac{z}{2x}}

= \frac{F (z, 0)(−x + \frac{zx^{2}}{2} + z − \frac{zx}{2}) − x}{zx^{2} − 2x + z}.

Now, set as usual

r_{1}(z) = \frac{1 − \sqrt{1 − z^{2}}}{z} , r_{2}(z) = \frac{1 + \sqrt{1 − z^{2}}}{z} .

KERNEL METHOD: EXAMPLES 11

For x = r_{1}(z) the numerator vanishes, as always:

F (z, 0) = \frac{2r_{1}(z)}{−2r_{1}(z) + zr_{1}^{2}(z) + 2z − zr_{1}(z)}

= \frac{2r_{1}(z)}{−2r_{1}(z) + 2r_{1}(z) − z + 2z − zr_{1}(z)}

= \frac{2r_{1}(z)}{z(1 − r_{1}(z))}

and

F (z, x) = \frac{\frac{2r_{1}(z)}{z(1−r_{1}(z))}(−x + \frac{zx^{2}}{2} + z − \frac{zx}{2}) − x}{zx^{2} − 2x + z}

= \frac{−2z + zr_{1}(z)x}{z^{2}(x − r_{2}(x))(1 − r_{1}(z))}

= \frac{2zr_{1}(z) − 2xr_{1}(z) + xz}{z^{2}(1 − r_{1}(z))(1 − xr_{1}(z))}.

From this explicit form we can now read off coefficients:

[x^{n}]F (z, x) = \frac{2zr_{1}(z)}{z^{2}(1 − r_{1}(z))}r_{1}^{n}(z) + \frac{−2r_{1}(z) + z}{z^{2}(1 − r_{1}(z))}r_{1}^{n−1}(z)

= \frac{2r_{1}^{n+1}(z)}{z(1 − r_{1}(z))} − \frac{2r_{1}^{n}(z)}{z^{2}(1 − r_{1}(z))} + \frac{r_{1}^{n−1}(z)}{z(1 − r_{1}(z))}

= r_{1}^{n−1}(z)\frac{2zr_{1}^{2}(z) − 2r_{1}(z) + z}{z^{2}(1 − r_{1}(z))}

= r_{1}^{n−1}(z)\frac{2r_{1}(z) − z}{z^{2}(1 − r_{1}(z))}

= r_{1}^{n−1}(z)\frac{zr_{1}^{2}(z)}{z^{2}(1 − r_{1}(z))}

= \frac{r_{1}^{n+1}(z)}{z(1 − r_{1}(z))}.

This is only correct for n ≥ 1.

And now set z = 2v/(1 + v^{2}), which is the trick we used before. Then r_{1} = v;

[z^{m}]\frac{r_{1}^{n+1}(z)}{z(1 − r_{1}(z))} = \frac{1}{2πi} ∮ \frac{dz}{z^{m+1}} \frac{r_{1}^{n+1}(z)}{z(1 − r_{1}(z))}

= \frac{1}{2πi} ∮ \frac{(1 − v^{2})(1 + v^{2})^{m+1}}{2^{m}v^{m+1}(1 + v^{2})^{2}} \frac{v^{n+1}(1 + v^{2})}{v(1 − v)}dv

= \frac{1}{2πi} ∮ \frac{2(1 + v)(1 + v^{2})^{m}}{2^{m+1}v^{m−n+1}} dv

= 2^{−m}[v^{m−n}](1 + v)(1 + v^{2})^{m}

= 2^{−m}\binom{m}{⌊\frac{m−n}{2}⌋}.

For n = 0 we can do this:

[x^{0}]F (z, x) = F (z, 0) = \frac{2r_{1}(z)}{z(1 − r_{1}(z))},

and one must multiply the previous formula by 2:

[z^{m}x^{0}]F (z, x) = 2^{1−m}\binom{m}{⌊\frac{m}{2}⌋}.

5. A recursion from generating binary trees

We don’t aim to describe how the following recursion is related to generate binary trees; we merely show how to solve it with the kernel method.

The recursion is

g_{n,k} = g_{n−1,k−1} + 2g_{n−1,k} + g_{n−1,k+1} + 1 for 0 ≤ k ≤ n

with the assumption that all values g_{n,k} outside the range 0 ≤ k ≤ n are zero. We set up the generating function

G(z, x) = ∑_{0≤k≤n} g_{n,k}x^{k}z^{n}.

Summing up the recursion (multiplied by x^{k}z^{n}) we find

G(z, x) = zxG(z, x) + 2zG(z, x) + \frac{z}{x}(G(z, x) − g(z)) + ∑_{0≤k≤n} x^{k}z^{n},

with g(z) = G(z, 0). Note that

∑_{0≤k≤n} x^{k}z^{n} = ∑_{k≥0} ∑_{j≥0} x^{k}z^{k+j} = \frac{1}{1 − z} ∑_{k≥0}(zx)^{k} = \frac{1}{(1 − z)(1 − zx)}.

Hence

G(z, x) = \frac{zg(z) − \frac{x}{(1−z)(1−zx)}}{zx^{2} + (2z − 1)x + z}

Now note that

zx^{2} + (2z − 1)x + z = z(1 − xr_{1}(z))(1 − xr_{2}(z))

with

r_{1,2}(z) = −1 + \frac{1 ∓ \sqrt{1 − 4z}}{2z} .

Since the denominator vanishes for x = r_{1}(z), the numerator should also vanish, which means

zg(z) = \frac{r_{1}(z)}{(1 − z)(1 − zr_{1}(z))},

which leads already to the solution

g(z) = \frac{r_{1}(z)}{z(1 − z)(1 − zr_{1}(z))},

whence G(z, x) is known as well.

6. A card guessing game

One starts with a deck of cards consisting of m red and n black cards. A guess is made as to the colour of the top card, after which it is revealed and discarded. To maximise the number of correct guesses one chooses the colour corresponding to the majority of cards remaining in the deck. We rederive here the probability distribution for the number of correct guesses for a pack of m+n cards, found originally by Sulanke [16].

In what follows, m always refers to the number of cards of the colour that is predominant, n to the other colour.

Let p(m, n; k) denote the probability that, assuming that one has m cards of one colour and n cards of a second colour, with m ≥ n ≥ 0, that one guesses k cards correctly. Introducing probability generating functions

φ_{m,n}(u) = ∑_{m≤k≤m+n} p(m, n; k)u^{k},

one sees the recursions

φ_{m,n}(u) = u\frac{m}{m + n}φ_{m−1,n}(u) + \frac{n}{m + n}φ_{m,n−1}(u) for m > n ≥ 0,
φ_{m,m}(u) = \frac{1 + u}{2}φ_{m,m−1}(u) for m ≥ 1, φ_{0,0}(u) = 1

almost immediately. If one defines Φ_{m,n}(u) = \binom{m+n}{m}φ_{m,n}(u) instead, the recursions are nicer, viz.

Φ_{m,n}(u) = uΦ_{m−1,n}(u) + Φ_{m,n−1}(u) for m > n ≥ 0,
Φ_{m,m}(u) = (1 + u)Φ_{m,m−1}(u) for m ≥ 1, Φ_{0,0}(u) = 1.

Now we use the kernel method to get the probabilities p(m, n; k): We set

F (z, x) = ∑_{m≥n≥0} Φ_{m,n}(u)z^{m}x^{m−n},
F_{0}(z) = ∑_{m≥0} Φ_{m,m}(u)z^{m},
F_{1}(z) = ∑_{m≥1} Φ_{m,m−1}(u)z^{m}.

The first and second recursion for Φ_{m,n}(u) give

F (z, x) − F_{0}(z) = uzx F (z, x) + \frac{1}{x}[F (z, x) − F_{0}(z) − F_{1}(z)x]

and F_{0}(z) = 1 + (1 + u)F_{1}(z), respectively. Hence

(1 − x + uzx^{2})F (z, x) = 1 − x + (1 + u − ux)F_{1}(z).

Now the fact that the power series F (z, x) remains finite at x = λ := 2/(1+\sqrt{1 − 4uz}) gives F_{1}(z) = (λ − 1)/(1 + u − λu) and finally

F (z, x) = (\frac{1 + \sqrt{1 − 4uz}}{2} − \frac{1 − \sqrt{1 − 4uz}}{2} u)^{−1}(1 − \frac{1 − \sqrt{1 − 4uz}}{2} x)^{−1}.

From this, using the expansion of the geometric series and the identity [6, (5.61)]

∑_{n≥0} \binom{2n + k}{n}X^{n} = \frac{2^{k}}{\sqrt{1 − 4X}(1 + \sqrt{1 − 4X})^{k}}

we eventually find

p(m, n; k) = \frac{1}{\binom{m+n}{m}}[\binom{m + n}{k} − \binom{m + n}{k + 1}] for m ≤ k ≤ m + n.

7. A functional–difference equation of Runyon, Morrison, Carlitz, and Riordan

A certain functional–difference equation that Runyon encountered when analyzing a queuing system was solved in a combined effort of Morrison, Carlitz, and Riordan. Here we apply the kernel method to it.

The functional–difference equation is

(x − α)(α − β)^{n−1}g_{n}(x) = α(x − β)^{n}g_{n−1}(α) − x(α − β)^{n}g_{n−1}(x), n ≥ 1, g_{0}(x) = 1.

We introduce the generating function

G(x, t) := ∑_{n≥0}(α − β)^{n−1}g_{n}(x)t^{n}.

Multiplying the recursion by t^{n} and summing we get

G(x, t) = \frac{α ∑_{n≥1}(x − β)^{n}t^{n}g_{n−1}(α) + \frac{x−α}{α−β}}{x − α + xt(α − β)^{2}} = \frac{α(x − β)(α − β)tG(α, \frac{t(x−β)}{α−β}) + \frac{x−α}{α−β}}{x − α + xt(α − β)^{2}} .

For

x = x̄ = \frac{α}{1 + t(α − β)^{2}}

the denominator vanishes. Consequently, the numerator must also vanish:

∑_{n≥1}(x̄ − β)^{n}t^{n}g_{n−1}(α) = \frac{x̄ − α}{(β − α)α}.

Now we set T = (x̄ − β)t, i. e.,

t = \frac{1 − T (α − β) − \sqrt{1 − 2T (α + β) + T^{2}(α − β)^{2}}}{2β(α − β)} .

So

∑_{n≥0} T^{n}g_{n}(α) = (α − β)G(α, \frac{T}{α−β} ) = \frac{1 + T (α − β) − \sqrt{1 − 2T (α + β) + T^{2}(α − β)^{2}}}{2T α} .

Since this series is now known, the generating function G(x, t) is known as well. From this, one can expand this function and describe its coefficients. We refer for this to the original paper.

8. Banach’s match box problem

This is a very classical exercise. A certain mathematician has two match boxes in each of his two pockets. Initially, both contain m matches each. He makes random drawings for one of his pockets to get one match box. How many matches are left in the larger box when one box has become empty? A small variation is to count the remaining matches when he tries to get a match and finds that his chosen box is empty. In what follows, m (n) is always the number of matches in the larger (smaller) box. We want the probability generating function φ_{m,n}(u), where the coefficient of u^{k} is the probability that this parameter is k. The following recursions are self-explanatory:

φ_{m,n}(u) = \frac{1}{2}φ_{m−1,n}(u) + \frac{1}{2}φ_{m,n−1}(u) for m > n ≥ 1,
φ_{m,m}(u) = φ_{m,m−1}(u) for m ≥ 1,
φ_{m,0}(u) = u^{m},  for m ≥ 0.

Define

F (z, x) = ∑_{m≥n≥0} φ_{m,n}(u)z^{m}x^{m−n},

F_{0}(z) = ∑_{m≥0} φ_{m,m}(u)z^{m}, F_{1}(z) = ∑_{m≥1} φ_{m,m−1}(u)z^{m},

Summing the recursion, we get

∑_{m>n≥1} φ_{m,n}(u)z^{m}x^{m−n} + ∑_{m≥1} φ_{m,m}(u)z^{m}

= \frac{1}{2} ∑_{m>n≥1} φ_{m−1,n}(u)z^{m}x^{m−n} + \frac{1}{2} ∑_{m>n≥1} φ_{m,n−1}(u)z^{m}x^{m−n} + ∑_{m≥1} φ_{m,m−1}(u)z^{m}

or

F (z, x) − ∑_{m≥0} φ_{m,0}z^{m}x^{m}

= \frac{zx}{2} ∑_{m≥n≥1} φ_{m,n}(u)z^{m}x^{m−n} + \frac{1}{2x} ∑_{m−1>n≥1} φ_{m,n}(u)z^{m}x^{m−n} + F_{1}(z)

or

F (z, x) − \frac{1}{1 − zxu}

= \frac{zx}{2}[F (z, x) − \frac{1}{1 − zxu}] + \frac{1}{2x}[F (z, x) − xF_{1}(z) − F_{0}(z)] + F_{1}(z).

Note F_{1}(z) = F_{0}(z) − 1. We get

F (z, x) = \frac{\frac{1}{1−zxu}(1 − \frac{zx}{2}) + \frac{x−1}{2x}F_{0}(z) − \frac{1}{2}}{1 − \frac{zx}{2} − \frac{1}{2x}} = \frac{\frac{x}{1−zxu}(zx − 2) + (1 − x)F_{0}(z) + x}{zx^{2} − 2x + 1}.

Now set r_{1}(z) = \frac{1−\sqrt{1−z}}{z}; as before, (x−r_{1}(z)) must be a factor of the numerator, which gives us the equation

\frac{r_{1}(z)}{1 − uzr_{1}(z)}(zr_{1}(z) − 2) + (1 − r_{1}(z))F_{0}(z) + r_{1}(z) = 0

whence

F_{0}(z) = \frac{r_{1}(z)(−zr_{1}(z) + 1 + uzr_{1}(z))}{(1 − uzr_{1}(z))(1 − r_{1}(z))}.

We don’t want to explore that in much detail; let us just compute the averages, as this is the classical problem. So, we differentiate this with respect to u and set u = 1 and get the generating function E(z) of the averages:

E(z) = \frac{(zr_{1}(z) − 2) zr_{1}^{2}(z)}{(1 − zr_{1}(z))^{2} (1 − r_{1}(z))}.

With the substitution z = 4v/(1 + v)^{2},

E(z) = \frac{4v(1 + v)}{(1 − v)^{3}}.

Hence

[z^{m}]E(z) = \frac{1}{2πi} ∮ \frac{dz}{z^{m+1}} E(z) = \frac{1}{2πi} ∮ \frac{4dv(1 − v)(1 + v)^{2m+2}}{(1 + v)^{3}(4v)^{m+1}} \frac{4v(1 + v)}{(1 − v)^{3}}

= 4^{1−m}[v^{m−1}]\frac{(1 + v)^{2m}}{(1 − v)^{2}}

= 4^{1−m} ∑_{k=0}^{m−1} \binom{2m}{k}(m − k) = 4^{1−m} \frac{(2m − 1)!}{(m − 1)!^{2}} ∼ 2\sqrt{\frac{m}{π}}.

Note that this is the special case p = q of the toilet paper problem, considered in Section 3. However, there, the recursions were only set up for the averages (expectations), whereas here we have full access to the probability generating functions.

One could consider them in the toilet paper as well. We leave this to the interested reader. All one has to do is to replace the boundary conditions M_{m,0} = m by M_{m,0} = u^{m}.

Acknowledgment. Thanks are due to Margaret Archibald and Michael Drmota who read earlier drafts of this paper.

References

1. C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps, Generating functions of generating trees, Discrete Mathematics 246 (2002), no. 1-3, 29–55.

2. D. Bertacchi, Inhomogeneous quantities for the simple random walk on the 2-comb, (2003).

3. D. Bertacchi and F. Zucca, Uniform asymptotic estimates of transitiion probabilities on combs, (2003).

4. M. Drmota, Discrete random walks on one-sided “periodic” graphs, Discrete Mathematics and Theoretical Computer Science, submitted (2003).

5. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM Journal on Discrete Mathematics 3 (1990), 216–240.

6. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics (second edition), Addison Wesley, 1994.

7. W. Knödel, Über das mittlere Verhalten von on-line-Packungsalgorithmen, EIK 19 (1983), 427– 433.

8. A. Knopfmacher and H. Prodinger, A simple card guessing game revisited, Electron. J. Combin. 8 (2001), Research Paper 13, 9 pp. (electronic).

9. D. E. Knuth, The art of computer programming, vol. 1: Fundamental Algorithms, Addison-Wesley, 1973, Third edition, 1997.

10. , The toilet paper problem, Amer. Math. Monthly 91 (1984), 465–470, reprinted in: Selected papers on analysis of algorithms, CSLI lecture notes, 2000.

11. A. Panholzer and H. Prodinger, Towards a more precise analysis of an algorithm to generate binary trees : A tutorial, The Computer Journal 41 (1998), 201–204.

12. H. Prodinger, Einige Bemerkungen zu einer Arbeit von W. Knödel über das mittlere Verhalten von on-line–Packungsalgorithmen, EIK 21 (1985), 3–7.

13. , Further results on a problem of Knödel concerning the analysis of bin–packing, Number– theoretic Analysis (E. Hlawka and R. F. Tichy, eds.), Lecture Notes in Mathematics, vol. 1452, 1990, pp. 193–198.

14. , Einige Bemerkungen zu einer Bin–Packing Aufgabe von W. Knödel, Computing 47 (1992), 247–254.

15. , On a functional-difference equation of Runyon, Morrison, Carlitz, and Riordan, Sém. Lothar. Combin. 46 (2001), Art. B 46a, 4 pp. (electronic).

16. R. Sulanke, Guessing, ballot numbers, and refining Pascal’s triangle (9 pages), http://diamond.idbsu.edu/∼sulanke/recentpapindex.html (1995).

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, Private Bag 3, Wits, 2050 Johannesburg, South Africa

E-mail address: helmut@maths.wits.ac.za