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

Question

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.

Answer 1

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

Answer 2

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.