How memes propagate 
[Feb. 8th, 200504:02 am]
Arvind Narayanan

_imran_ of memeland writes:
After my first meme took close to half a million hits in a month I decided it and all of my future memes deserve their own website, so here we are. Wow, half a million hits? Are memes really that successful at selfpropagation? Can anyone write a meme and get lots and lots of hits (and ad revenue) on their web site? No, and here's why.
In probability theory memes are modeled by what is known as a birth and death process. Each node has either 0 children or 1 child or 2 children or ..., and each number of children has a certain probability of occuring. Each child again has more children and so on. Based on the probability distribution, the tree will either expand indefinitely or reach a finite number of nodes.
What is being modeled is that when a person propagates a meme, each of their friends picks it up with a certain probability.
Let us consider an extremely simple probability distribution for illustrative purposes: each node either has two children (with probability half) or no children (with probability half). This represents an 'average' meme. A highly successful meme will have lots of children at each node, and will eventually reach the entire blogosphere, while a poor meme won't be picked up by anybody and will die at the originating node. Most memes appear to be average or close to average, because whether or not a meme is picked up seems to depend as much on the level of boredom of the blogger as on the inherent quality of the meme :)
So how do average memes fare? That is, how many times can they expect to be propagated? The answer from probability theory is that it is highly variable. You can check this with a simple script:
$ for i in `seq 1 100`; do birth() { echo;if [ $[RANDOM/16%2] eq 0 ] ; then birth; birth; fi }; birth  wc l; done
(I have a shell scripting obsession).
What this does is makes 100 trials of the experiment based on the either0or2children probability distribution. I'm using RANDOM/16 because the last bit of bash's rand is not random. (RANDOM/2 is probably sufficient.)
Here are the results of the 100 trials:
1, 3, 1, 1, 5, 1, 3, 1, 7, 21, 1, 5, 1, 9, 17, 1, 7, 1, 5, 19, 1, 11, 1, 9, 3, 1, 79, 1, 1, 3, 1, 15, 1, 1, 3, 1, 3, 1, 1, 5, 1, 67, 161, 1, 11, 1, 259, 107, 1, 3, 1, 77393, 1, 9, 1, 1, 11, 1, 127, 1, 1, 15, 1, 13, 1, 1, 3, 1, 407, 1, 1, 15, 1, 5, 17, 1, 71, 1, 119, 3, 1, 17, 1, 5, 3, 1, 3, 1, 1, 57, 1, 3, 1, 1, 109, 1, 5, 1, 1, 21
Very insightful. More than half the time the meme never gets past the starting block, but if it does, there's a significant chance that it'll get to the 100's. With a small probability it becomes insanely popular.
Since this meme is exactly average, the chance that the tree will expand indefinitely (i.e reach nearly the entire blogsphere) is zero. But for a slightly above average meme, you can expect that there's a 10% chance of getting to the 1000s and a small chance like 1% or so of getting to the millions (theoretically infinite). 

