It's Everywhere!
May. 15th, 2011 05:08 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stoutfellowI have, over the years, assembled a whole bunch of pictures which I use as backgrounds on my computer. On the old computer, I would manually change the background every evening, going in alphabetical order. With the new computer and the switch to Windows 7, I no longer have to do this; instead, I've set the computer itself to randomly pick a new background every day.
Being, as usual, of an ordinological bent, I began tracking which backgrounds come up back in February, and also noting which ones have been used more than once (and how often), and which have not appeared at all yet. A couple of days ago, I found myself sucked into viewing this as a mathematical question: if you have k pictures, how long can you expect to wait before each of the pictures has shown up at least once? (Not for the first time, the problem occurred to me in the shower, and I stayed too long under the hot/warm/tepid blast trying to figure out how to attack it.)
Yesterday, I made considerable progress, and got an expression for the expected length of time. It took most of the combinatorial techniques I know to get there. (Combinatorics is the mathematics of counting things, especially in cases where simple enumeration - "1. 2. 3...." isn't practical. The things being counted have to have some kind of structure for this to work, and half the task is figuring out that structure.) It turns out that the expected number of days has the form k2xk-1, where xk is the sum, as i ranges from 0 to k, of (-1)iC(k,i)/(i+1)2. C(k,i) is the binomial coefficient k!/(i!(k-i)!). The first few values of xk, as k ranges from 0 to 9, are (to six figures) 1, .75, .611111, .520833, .456666, .408333, .370408, .339732, .314330, .292290. Here, I'm stuck. The numbers seem to be slowly closing in on 0, but I have no ideas on how to prove that, or to figure out at what rate they're doing it. (They look like they're closing in slightly slower than 1/k does.) I've gone as far as to try to set up differential equations - not, normally, my cup of tea - that describe what's going on, without much luck. It's frustrating.
I've got to stop thinking in the shower.
Being, as usual, of an ordinological bent, I began tracking which backgrounds come up back in February, and also noting which ones have been used more than once (and how often), and which have not appeared at all yet. A couple of days ago, I found myself sucked into viewing this as a mathematical question: if you have k pictures, how long can you expect to wait before each of the pictures has shown up at least once? (Not for the first time, the problem occurred to me in the shower, and I stayed too long under the hot/warm/tepid blast trying to figure out how to attack it.)
Yesterday, I made considerable progress, and got an expression for the expected length of time. It took most of the combinatorial techniques I know to get there. (Combinatorics is the mathematics of counting things, especially in cases where simple enumeration - "1. 2. 3...." isn't practical. The things being counted have to have some kind of structure for this to work, and half the task is figuring out that structure.) It turns out that the expected number of days has the form k2xk-1, where xk is the sum, as i ranges from 0 to k, of (-1)iC(k,i)/(i+1)2. C(k,i) is the binomial coefficient k!/(i!(k-i)!). The first few values of xk, as k ranges from 0 to 9, are (to six figures) 1, .75, .611111, .520833, .456666, .408333, .370408, .339732, .314330, .292290. Here, I'm stuck. The numbers seem to be slowly closing in on 0, but I have no ideas on how to prove that, or to figure out at what rate they're doing it. (They look like they're closing in slightly slower than 1/k does.) I've gone as far as to try to set up differential equations - not, normally, my cup of tea - that describe what's going on, without much luck. It's frustrating.
I've got to stop thinking in the shower.
