1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Justin L. Oct 23 '13 at 20:21
  • $\begingroup$ 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? $\endgroup$ – Justin L. Oct 23 '13 at 20:23
  • $\begingroup$ 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. $\endgroup$ – Daniel Fischer Oct 23 '13 at 20:29
  • $\begingroup$ (*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. $\endgroup$ – Justin L. Oct 23 '13 at 20:36
  • $\begingroup$ Well I guess you sort of answered my question, I didn't realize it. If all states are equally possible, then the steady state is the density of these states... if they are not, I guess we can say that the most probable configuration is the steady state configuration? $\endgroup$ – Justin L. Oct 23 '13 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.