Imagine I have an array of N booleans with value 0. And in each turn I set one of them to 1 with equal probability. Is there any function that describes the average number of 1s per X turns?.
At start, if the N is big it would increase linearly up to a point where there are a lot more 1s than zeroes, after that it will do a curved line as the chance to set 1 on a 0 cell would decrease a lot as the amount of 0 cells decreases. It may have something to do with markov chains if i am not mistaken.
The function would kinda look like this $$f(x)=N(1-\frac{1}{g(x)}),\quad g(x)=1+x $$
but I cant figure out any hidden parameters or a better function than g(x), or even a complete different function than f(x)
Suppose we initially had $n$ zeroes, and on turn $t$ we already have $K_t$ ones. Then we have, that $K_{t+1} = K_t$ with probability $\frac{K_t}{n}$ and $K_{t+1} = K_t + 1$ with probability $1 - \frac{K_t}{n}$.
Thus, for every fixed of $K_t = c$ we have, that $$E[K_{t+1}] = \frac{c^2}{n} + c + 1 - \frac{c^2}{n} - \frac{c}{n} = c(1 - \frac{1}{n}) + 1$$ From that we can derive the following recurrent formula for $E[K_t]$:
$$E[K_0] = 0$$ $$E[K_{t+1}] = E[K_t](1-\frac{1}{n}) + 1$$
From this it follows, that
$$E[K_{t}] = \sum_{i = 0}^{t-1} (1 - \frac{1}{n})^i = \frac{1 - (1 - \frac{1}{n})^t}{1 - (1 - \frac{1}{n})} = n\Big(1 - \big(1 - \frac{1}{n}\big)^t\Big)$$