# With what frequency should points in a 2D grid be chosen in order to have roughly $n$ points left after a time $t$

Say I have a 2D array of $$x$$ by $$y$$ points with some default value, for generalisation we'll just say "0".

I randomly select a pair of coordinates with a frequency of $$f$$ per second and, if the point selected is 0: flip it to 1. However, if the point is already $$1$$ then do not change it.

How then, given a known $$x$$ and $$y$$ (thus known total points as $$xy$$) can I calculate a frequency $$f$$ that will leave me with approximately (as this is random) $$n$$ 0 points remaining, after a set time $$t$$? Where $$t$$ is also seconds.

For some context I am attempting some simplistic approximation of nuclear half-life but I'm not sure how to make use of the half-life equation for this, nor do I think that it is strictly correct to apply it given my implementation isn't exactly true to life, picking single points at a time.

• I have a feeling that the Coupon Collector Problem could be useful here. You could approach it so that you have a large number of different coupons, and at every time step you "find" one. The first one is obviously a new one. For the second one, you still have a pretty big probability that it's also a new one. But it starts decreasing ... Apr 19, 2021 at 11:25

Let's start with $$n_1$$ points are $$0$$'s at the start, and end when there are $$n_2$$ $$0$$'s, where $$n_1>n_2$$

We will compute the expected number of flips to turn all of them to 1. Then calculate the frequency.

For the first pick, you can select any of the $$0$$'s. There are $$n_1$$ such points. You can do this w.p $$\mathbb P[\text{select a 0 point}] = \frac{n_1}{xy}$$. The expected number of flips to then flip a $$0$$ is then $$\frac{1}{\mathbb P[\text{select a 0 point}] } = \frac{xy}{n_1}$$

For the second pick you can select any of the $$n_1-1$$ points. Therefore the probability is $$\frac{n_1-1}{xy}$$ that you select a $$0$$. Then the expected number of attempts to flip a $$0$$ is equal to $$\frac{xy}{n_1-1}$$ to select such a point. We continue like this till we are left with $$n_2$$ 0's.

At this point, the probability of secting this point is $$\frac{n_2+1}{xy}$$, and the expected number of flips to flip a $$0$$ is $$\frac{xy}{n_2+1}$$

Therefore the total expected number of attempts to pick all points is \begin{align*} \text{number of attempts} &=\frac{xy} {n_1}+\frac{xy} {n_1-1}+\frac{xy} {n_1-2}+\dots+\frac{xy}{n_2+1}\\ &=xy\left(\frac{1} {n_1}+\frac{1} {n_1-1}+\frac{1} {n_1-2}+\dots++\frac{1}{n_2+1} \right)\\ &=xy\cdot [H(n_1)-H(n_2)] \end{align*} where $$H(n_1)$$ is the $$n_1$$'th harmonic number

If you have a fixed time $$t$$, then you get frequency, as \begin{align*} \text{freq}\times\text{time}=\text{number of attempts}\\ \text{freq}=\frac{xy[H(n_1)-H(n_2)]}{t}\\ \end{align*} You can approximate this using the $$\log$$ function $$\text{freq}\simeq\frac{xy}{t}\log\left(\frac{n_1}{n_2}\right)$$

EDIT: This is an instance of the Coupon Collector Problem as pointed out in the comments

This started out as a comment about the setting but got way too long.

As has been noted, this is a coupon collector process. However, since you're interested in continuous time, you might want to Poissonise the sampling - the idea being that you draw times at which a sample is collected according to a Poisson process with rate $$f$$. Note that this is commonly used in physical settings (because of the memorylessness of increments) and for $$t \gg 1/f,$$ the number of samples drawn is sharpy concentrated around $$ft$$ so the model remains faithful.

One big advantage is that under the Poissonised sampling, the number of draws of each coupon up to time $$t$$ are iid $$\mathrm{Poisson}(ft/N)$$ random variables (more generally, if samples are drawn according to $$p$$, then the number of times $$i$$ was observed is $$\mathrm{Poisson}(ft p_i)$$). The independence makes many computations very easy. For instance, we can trivially get the distribution of the number of unobtained coupons - if we call this $$Z(t)$$, then $$P(Z(t) = k) = \binom{N}{k} e^{-kft/N} (1 - e^{-ft/N})^{N-k},$$ which arises simply from asking how likely it is that $$k$$ out of $$N$$ independent Poisson processes take the value $$0$$. If you want that at a fixed time $$t$$ it holds that $$Z(t) \approx n$$ with high probability, just picking $$f_*$$ such that $$e^{-f_*t/N} = n/N \iff f_* = \frac{N \log N/n}{t}$$ ensures that, as long as $$n\gg1$$, with high probability $$Z(t) = n + O(\sqrt n).$$ (Note that this answer is identical to the coupon collector heuristic computation by Rahul - this is largely due to the strong concentration of the Poisson I mentioned above).

Also, if you're interested in characterising half-life, then you should actually care about the random time $$\tau = \inf\{t : Z(t) < N/2\}$$. A decent heuristic for $$\mathbb{E}[\tau]$$ should come from the fact that if $$\mathbb{E}[Z(t)] < N/2 - \sqrt{N}$$, then $$P(Z(t) \ge N/2) \ll 1$$ which yields $$\mathbb{E}[\tau] \approx \frac{N \log 2}{f},$$ but this is not rigorous and I don't have experience working with this process enough to say how easy or not figuring out the law of $$\tau$$ is.