[pzhon]

The involution method is a technique in combinatorics with many applications. An involution is just a fancy name for a permutation of order two. Every item is either fixed by the involution, of swapped with another item. The idea is that we would like to count a set S. Instead, we count a larger set T (containing S) where some of the elements count as positive and some negative, and find an involution I so that

[img]/images/graemlins/diamond.gif[/img] Every element of S is fixed by the involution.
[img]/images/graemlins/diamond.gif[/img] Every element of T\S has its sign reversed by I.

Then the signed count of the elements of T equals the count of the elements of S.

The reflection argument was an example of the involution method. We counted the paths from 0 to a that never reached k by counting the elements in a larger set, the paths from 0 to a and the paths from 0 to 2k-a, where the paths from 0 to 2k-a were given a negative sign. The involution was to reflect the part of the path after the path first hit k. This had no effect on the paths that never reached k, and it changed every path from 0 to 2k-a into a path from 0 to a that reached k and vice versa.

We'd like to apply the same idea to the paths from 0 to a that didn't reach k or -k. One possibility is to reflect the remainder of the paths when they first hit k or -k. However, this doesn't work as before, since a path from 0 to a might hit both -k and k, so it would correspond to a path from 0 to 2k-a and to a path from 0 to -2k-a. It would be removed twice if we take nC(n-a)/2 - nC(n-2k+a)/2 - nC(n+2k+a)/2.

Let's look for a simple signed set T so that the involution of reflecting the first time the paths reach +-k leaves only the paths that stay between -k and k fixed. We'll give a positive sign to paths of length n from 0 to elements of a set P, and negative signs to paths of length n from 0 to elements of a set N. We need to determine P and N.

P should contain a, since we need to give a positive sign to the paths to a that stay between -k and k.

N should contain 2k-a and -2k-a, since these are images of paths to a under the reflections at k and -k.

P should contain 4k+a and -4k+a, since there are the images of paths to -2k-a and 2k-a under the reflections.

N should contain 6k-a and -6k-a.
P should contain 8k+a and -8k+a.
...
P should contain 4mk+a for each integer m.
N should contain (4m+2)k-a for each integer m.

The involution switches paths to P and paths to N except that it leaves fixed the paths to a staying between -k and k. So, the number of paths from 0 to a staying between -k and k is

Sum n choose (n-b)/2 -
b in P

Sum n choose (n-b)/2
b in N

=

Sum n C (n-4mk-a)/2 -
m

Sum n C (n-(4m+2)k+a)/2
m

To find all constrained paths, you can sum over all possible values of a between -k+1 and k-1:

Sum (n C (n-a)/2) f(a)
a

where

f(a) = +1 if a mod 4k is in (-k+1,k-1)
f(a) = 0 if a mod 4k is -k or k
f(a) = -1 if a mod 4k is in (k+1,3k-1)

For example, the number of paths of length 20 that stay strictly between -3 and 3 is

-20C0 (a=20)
-20C1 (a=18)
-20C2 (a=16)
+20C3 (a=14)
+20C4 (a=12)
+20C5 (a=10)
-20C6 (a=8)
-20C7 (a=6)
-20C8 (a=4)
+20C9 (a=2)
+20C10 (a=0)
+20C11 (a=-2)
-20C12 (a=-4)
-20C13 (a=-6)
-20C14 (a=-8)
+20C15 (a=-10)
+20C16 (a=-12)
+20C17 (a=-14)
-20C18 (a=-16)
-20C19 (a=-18)
-20C20 (a=-20)
---------------
78,732

An alternative method is to take the 20th power of the transfer matrix

01000
10100
01010
00101
00010

9842 0 19683 0 9841
0 29525 0 29524 0
19683 0 39366 0 19683
0 29524 0 29525 0
9841 0 19683 0 9842

The sum of the middle column or row is 78,732, confirming the count by the involution method.

The same argument works for Brownian motion, though the result is that the probability density of the constrained paths is an infinite sum of signed densities. The same argument also works for paths constrained asymmetrically, e.g., paths constrained to stay between 0 and k, inclusive.