# Proving that the eigenvectors of this class of matrices are the binomial coefficients

So I'm trying to figure out the behavior of this system: you have $N$ coins, and every step, you choose one of the coins randomly and flip them.

Now we imagine a bazillion of these systems. We call $\rho_n$ the percentage of the systems that have $n$ coins flipped up (heads) -- state $S_n$.

It's easy to see that the number of systems that end up in $S_1$, for example, is all of the systems that were in $S_0$ (zero heads up, the only way to go is more heads), and $2/N$ of the systems in state $S_2$. With a little more of a stretch, it can be seen that the number of systems that end up in $S_2$ is $(N-1)/N$ of the systems that were in state $S_1$ and $3/N$ of the systems that were in state $S_3$. And so on, and so on.

We can then see that $\vec{\rho}'$ (the distribution of states after an iteration) is a simple matrix multiplication/linear transformation if $\vec{\rho}$, with the coefficients of the matrix being the ones listed above.

For example, for the case of $N = 3$, we have:

$$\vec{\rho}' = \left[ \begin{array}{cccc} 0 & \frac{1}{3} & 0 & 0 \\ 1 & 0 & \frac{2}{3} & 0 \\ 0 & \frac{2}{3} & 0 & 1 \\ 0 & 0 & \frac{1}{3} & 0 \end{array} \right] \vec{\rho}$$

Which means that $\rho'_0$ (the new percentage of systems in state $S_0$) $= \frac{1}{3} \rho_1$ (1/3rds the percentage of systems that were in state $S_1$), that $\rho'_1 = \rho_0 + \frac{2}{3} \rho_2$, that $\rho'_2 = \frac{2}{3} \rho_1 + \rho_3$, etc.

More generally, for arbitrary $N$, the matrix is

$$\left[ \begin{array}{cccccc} 0 & \frac{1}{N} & 0 & 0 & \cdots & 0 & 0 \\ 1 & 0 & \frac{2}{N} & 0 & \cdots & 0 & 0 \\ 0 & \frac{N-1}{N} & 0 & \frac{3}{N} & \cdots & 0 & 0 \\ 0 & 0 & \frac{N-2}{N} & 0 & \ddots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \frac{N-1}{N} & 0 \\ 0 & 0 & 0 & 0 & \frac{2}{N} & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{N} & 0 \\ \end{array} \right]$$

I tried to find any steady states -- that is, distributions of $S_n$ that would remain unchanged under one transition. For something like $N=3$, you would expect something that "bulges" in the middle, kinda.

It turns out that the eigenvector corresponding to a steady state for $N=3$ is

$$\vec{\rho} = \left[ \begin{array}{c} 1 \\ 3 \\ 3 \\ 1 \\ \end{array} \right]$$

Which are third row of the binomial coefficients (the third row of Pascal's Triangle).

This kind of makes a lot of intuitive sense --- you want something that peaks in the middle, and tapers off, kind of like a normal distribution. One could think of the rows of Pascal's Triangle as a sort of discrete normal distribution, so this is sort of understandable.

After testing out $N=2$, which is $[ \begin{array}{ccc} 1 & 2 & 1 \end{array} ]^T$, it appears that the eigenvectors corresponding to steady states of this transition are successive rows of Pascal's Triagngle, or the binomial coefficients.

Now I understand how the binomial coefficients can show up in something like an unbiased random walk. But this isn't an unbiased random walk --- the transition probabilities depend on the current state.

How do they show up here?

It's easy to verify that the vector $b$ of binomial coefficients is an eigenvector to the eigenvalue $1$, apart from the components $0$ and $N$ (which are easily verified separately), we have the equation
\begin{align} (A\cdot b)_k &= \frac{N+1-k}{N}\cdot b_{k-1} + \frac{k+1}{N}\cdot b-{k+1}\\ &= \frac{N+1-k}{N}\binom{N}{k-1} + \frac{k+1}{N}\binom{N}{k+1}\\ &= \binom{N-1}{k-1} + \binom{N-1}{k}\\ &= \binom{N}{k}. \end{align}
As to why $b$ is an eigenvector to the eigenvalue $1$, consider each coin separately. It is heads-up with probability $\frac12$, and tails-up with probability $\frac12$ (yes, I'm waving hands here). There are $\binom{N}{k}$ configurations with $k$ coins flipped heads-up.
• Ah, it did not occur to me to simply verify this without going through all of the eigenvector math for each N. As for your hand wavy answer, I didn't realize that the binomial coefficients represented the number of configurations that resulted in $S_n$, but I did not know of why the vector of the number of possible configurations (or really, the most likely distribution of $S_n$'s) would be the eigenvector. – Justin L. Oct 23 '13 at 20:21
• Although now, on hindsight, it seems a bit obvious that the steady state distribution would be the most probable distribution. But now I do wonder -- this distribution is independent of the transition rules. Will $b$ be the eigenvector for all matrices representing all 1-norm-preserving transition rules? – Justin L. Oct 23 '13 at 20:23
• No, you need that all configurations are equally probable, so that for each coin, the probability of head/tails must be $\frac12$. If all coins have the same probability $p$ for heads, I think you get the histogram of a Binomial distribution with probability $p$ as eigenvector. – Daniel Fischer Oct 23 '13 at 20:29
• (*did realize, in my first comment) I was referring to (symmetric) arbitrary rules for transitioning from state $S_n$ to $S_m$... maybe flipping some coins more often than others, or something like that. As long as the rules are symmetric, one can assume that the most probable configuration = the steady state solution? Maybe my question is not well enough defined. – Justin L. Oct 23 '13 at 20:36