# Two artists want to paint all sand grains in 2 colors. They stop if one artist picks a grain already painted by the other. In mean how many picks?

Let $$N$$ be the (big) number of sand grains.
Artist $$B$$ want to paint them blue. Artist $$R$$ want to paint them red.
We start with all sand grains unpainted.
They decide $$B$$ can start.

$$B$$ picks a random sand grain (all always chance $$\frac{1}{N}$$) and paint it blue.
After this it's $$R$$ turn. $$R$$ picks a random sand grain and paints it red (if not already blue).
If an artist picks a sand grain which is:

• not painted yet the artists paints it with the own color and place it back afterwards. After this it's the other artist turn again.
• already colored in the own color the same artist will pick a new sand grain (this can repeat multiple times).
• already colored but not the own color the drawing session will end for both artists.

(That means they do fair share. They have either the same amount of colored sand grains or $$R$$ has just $$1$$ more.)

What is the expected/mean count of picks required for this experiment in relation to $$N$$?
We assume $$N$$ can grow as big we want (but not $$\infty$$). Does it converge to a equation $$f(N)$$?

The expected number of picks $$n$$ could be written as: $$\mathbb{E}[n,N] = \sum_{i=2}^{\infty} i\cdot p_i$$ Can we approximate it for large $$N$$. Does it converge to something?

• When an artist gets another try because they picked a grain of their own colour, does that count as an extra pick? (I suggest you differentiate picks from turns -- a turn may consist of more than one pick.) Jun 8, 2022 at 20:15
• @TonyK yes, one turn can contain multiple picks. And I'm interested at the total number of picks (and not turns). Despite that the relation in between them could also be interesting. Jun 8, 2022 at 20:52
• Notation: \infty produces $\infty$, which I think is what you intend. Jun 8, 2022 at 21:02
• @SammyBlack thanks! You are correct. Also noticed it right now (after noticing the comment from TonyK). Jun 8, 2022 at 21:04
• (@TonyK But as the chance picking the own color is very small as well and the experiment ends if the wrong color has been picked the number of turns and the number of picks will be most likely very close to each other) Jun 8, 2022 at 21:48

## 2 Answers

Note that the problem defines a Markov chain $$X = (X_t)_{t\geq0}$$. Below is part of the diagram for this chain:

Here, the state numbered $$k$$ represents the sand pile with $$k$$ painted sand grains, and each arrow represents a pick. Also, the chain stops when it visits any of the states labeled $$\partial$$.

Suppose the chain $$X$$ has started at $$0$$, so that $$\mathbf{P}(X_0 = 0) = 1$$. Also, let

$$V_k = \inf\{ t \geq 0 : X_t = k\}$$

be the first time $$X$$ visits $$k$$. Then $$\{V_k < \infty\}$$ represents the event where the first $$k$$ turns did not result in the termination of the drawing session. Now we condition on $$\{V_k < \infty\}$$ and consider the $$(k+1)$$th turn.

Case 1. Suppose $$k$$ is even. Then $$\frac{k}{2}$$ of the sand grains have been painted by Artist $$\color{blue}{\mathsf{B}}$$ and another $$\frac{k}{2}$$ by Artist $$\color{red}{\mathsf{R}}$$. So, Artist $$\color{blue}{\mathsf{B}}$$ will pick sand grains $$\tau_{k+1} \sim\operatorname{Geom}(1-\frac{k}{2N})$$ number of times until he/she sees one not painted by him/herself. Also, that last grain will be among those $$\frac{k}{2}$$ grains painted by $$\color{red}{\mathsf{R}}$$ with probability $$\frac{k/2n}{1-k/2N}$$ and an unpainted one with probability $$\frac{1-k/N}{1-k/2N}$$.

Case 2. Suppose $$k$$ is odd. Then $$\color{red}{\mathsf{R}}$$ will pick grains $$\tau_{k+1} \sim \operatorname{Geom}(1-\frac{k-1}{2N})$$ number of times. Also, the last grain picked in this turn will be among those $$\frac{k+1}{2}$$ grains painted by $$\color{blue}{\mathsf{B}}$$ with probability $$\frac{(k+1)/2N}{1-(k-1)/2N}$$ and an unpainted one with probability $$\frac{1-k/N}{1-(k-1)/2N}$$.

From this argument, we find that

$$\mathbf{P}(V_k < \infty) = \prod_{i=0}^{k-1} \frac{1-\frac{i}{N}}{1-\frac{\lfloor i/2\rfloor}{N}} \qquad\text{and}\qquad \mathbf{E}[\tau_{k+1} \mid V_k < \infty] = \frac{1}{1 - \frac{\lfloor k/2\rfloor}{N}}.$$

So, if $$T$$ and $$P$$ denotes the total number of turns and picks until the session ends respectively, then

\begin{align*} \mathbf{E}[T] &= \sum_{k=0}^{N} \mathbf{P}(V_k < \infty) = \sum_{k=0}^{N} \frac{\prod_{i=0}^{k-1} ( 1-\frac{i}{N} )}{\prod_{i=0}^{k-1} ( 1-\frac{\lfloor i/2\rfloor}{N} )}, \\[0.5em] \mathbf{E}[P] &= \sum_{k=0}^{N} \mathbf{E}[\tau_{k+1} \,;\, V_k < \infty] = \sum_{k=0}^{N} \frac{\prod_{i=0}^{k-1} ( 1-\frac{i}{N} )}{\prod_{i=0}^{k} ( 1-\frac{\lfloor i/2\rfloor}{N} )} \end{align*}

The upper bound is $$N$$ because the drawing session must terminate before or at the $$(N+1)$$th turn with probability $$1$$. (The drawing session ends only when an artist picks a sand grain that is colored by the other artist!)

Below is the table of numerical computation of $$\mathbf{E}[T]$$ and $$\mathbf{E}[P]$$:

$$N$$ $$\mathbf{E}[T]$$ $$\mathbf{E}[P]$$
$$1$$ $$2$$ $$2$$
$$2$$ $$2.5$$ $$3$$
$$3$$ $$3$$ $$3.5$$
$$4$$ $$3.4166667$$ $$4$$
$$10^2$$ $$17.301962$$ $$18.213506$$
$$10^4$$ $$176.75314$$ $$177.74428$$
$$10^6$$ $$1771.9546$$ $$1772.9537$$

Indeed, we claim:

Proposition. For any fixed $$\delta \in (0, \frac{1}{2})$$, \begin{align*} \mathbf{E}[T] &= \sqrt{\pi N} - \frac{1}{2} + \mathcal{O}(N^{-1/2+\delta}), \tag{1} \\ \mathbf{E}[P] &= \sqrt{\pi N} + \frac{1}{2} + \mathcal{O}(N^{-1/2+\delta}), \tag{2} \end{align*} as $$N \to \infty$$.

I believe that the proof below can be elaborated to give more terms in the asymptotic expansion. However, that will only make the proof more complicated, so I will leave it as a future project.

The proof of $$\text{(1)}$$ and $$\text{(2)}$$ are almost identical, so we will only prove $$\text{(2)}$$. We do so by doing some hard analysis on the formula for $$\mathbf{E}[P]$$. Let $$\varepsilon = \delta / 7 \in (0, \frac{1}{14})$$.

Case 1. For $$0 \leq k \leq N^{1/2+\varepsilon}$$, Taylor theorem applied to $$\log(1-x)$$ yields the estimate

\begin{align*} \sum_{i=0}^{k} \log \left(1 - \frac{i}{N}\right) &= - \sum_{i=0}^{k} \left( \frac{i}{N} + \frac{i^2}{2N^2} + \mathcal{O}(N^{-3/2+3\varepsilon}) \right) \\ &= - \frac{k^2}{2N} - \frac{k^3}{6N^2} - \frac{k}{2N} + \mathcal{O}(N^{-1+4\varepsilon}). \end{align*}

To make use of this, we also note that

\begin{align*} \left\lfloor\frac{k-1}{2}\right\rfloor + \left\lfloor\frac{k}{2}\right\rfloor &= k - 1, \\ \left\lfloor\frac{k-1}{2}\right\rfloor^2 + \left\lfloor\frac{k}{2}\right\rfloor^2 &= \frac{k^2}{2} - k + \mathcal{O}(1), \\ \left\lfloor\frac{k-1}{2}\right\rfloor^3 + \left\lfloor\frac{k}{2}\right\rfloor^3 &= \frac{k^3}{4} - \frac{3k^2}{4} + \mathcal{O}(k). \end{align*}

So it follows that

\begin{align*} &\log \mathbf{E}[\tau_{k+1} \,;\, V_k < \infty] \\ &= \sum_{i=0}^{k-1} \log \left(1 - \frac{i}{N}\right) - \sum_{i=0}^{\lfloor (k-1)/2 \rfloor} \log \left(1 - \frac{i}{N}\right) - \sum_{i=0}^{\lfloor k/2 \rfloor} \log \left(1 - \frac{i}{N}\right) \\ &= - \frac{k^2 - \lfloor\frac{k-1}{2}\rfloor^2 - \lfloor\frac{k}{2}\rfloor^2}{2N} - \frac{k^3 - \lfloor\frac{k-1}{2}\rfloor^3 - \lfloor\frac{k}{2}\rfloor^3}{6N^2} + \frac{k + \lfloor\frac{k-1}{2}\rfloor + \lfloor\frac{k}{2}\rfloor}{2N} + \mathcal{O}(N^{-1+4\varepsilon}) \\ &= - \frac{k^2}{4N} - \frac{k^3}{8N^2} + \frac{k}{2N} + \mathcal{O}(N^{-1+4\varepsilon}). \end{align*}

We also note that, by the Euler–Maclaurin_formula and with $$f_N(x) = \exp\left(-\frac{x^2}{4N} - \frac{x^3}{8N^2} + \frac{x}{2N}\right)$$,

\begin{align*} \sum_{1 \leq k \leq N^{1/2+\varepsilon}} f_N(k) &= \int_{0}^{\lfloor N^{1/2+\varepsilon} \rfloor} f_N(x) \, \mathrm{d}x + \frac{f_N(\lfloor N^{1/2+\varepsilon} \rfloor) - f_N(0)}{2} \\ &\qquad + \frac{f_N'(\lfloor N^{1/2+\varepsilon} \rfloor) - f_N'(0)}{6} + \mathcal{O}\left( \int_{0}^{N^{1/2+\varepsilon}} |f_N''(x)| \, \mathrm{d}x \right) \end{align*}

Through elementary but tedious computations, we can show that this reduces to

\begin{align*} &= \int_{0}^{N^{1/2+\varepsilon}} f_N(x) \, \mathrm{d}x - \frac{1}{2} + \mathcal{O}\bigl(N^{-1/2+2\varepsilon}\bigr). \end{align*}

Now substituting $$x = \sqrt{N}t$$ and expanding the resulting integrand using Taylor expansion,

\begin{align*} &= \int_{0}^{N^{\varepsilon}} \sqrt{N} \exp\left(-\frac{t^2}{4} - \frac{t^3}{8\sqrt{N}} + \frac{t}{2\sqrt{N}}\right) \, \mathrm{d}t - \frac{1}{2} + \mathcal{O}\bigl(N^{-1/2+2\varepsilon}\bigr) \\ &= \int_{0}^{N^{\varepsilon}} e^{-t^2/4}\left(\sqrt{N} - \frac{t^3}{8} + \frac{t}{2} \right) \, \mathrm{d}t - \frac{1}{2} + \mathcal{O}\bigl(N^{-1/2+7\varepsilon}\bigr). \end{align*}

Finally, using the estimate $$\int_{x}^{\infty} t^p e^{-t^2/a} \, \mathrm{d}x \sim \frac{a}{2}x^{p-1}e^{-x^2/2}$$ as $$x \to \infty$$ for $$a > 0$$, it follows that

\begin{align*} &= \int_{0}^{\infty} e^{-t^2/4}\left(\sqrt{N} - \frac{t^3}{8} + \frac{t}{2} \right) \, \mathrm{d}t - \frac{1}{2} + \mathcal{O}\bigl(N^{-1/2+7\varepsilon}\bigr) \\ &= \left( \sqrt{\pi N} - 1 + 1 \right) - \frac{1}{2} + \mathcal{O}\bigl(N^{-1/2+7\varepsilon}\bigr) \end{align*}

Summarizing, we have proved that

\begin{align*} \sum_{1 \leq k \leq N^{1/2+\varepsilon}} \mathbf{E}[\tau_{k+1} \,;\, V_k < \infty] &= e^{\mathcal{O}(N^{-1+4\varepsilon})} \left(\sqrt{\pi N} - \frac{1}{2} + \mathcal{O}\bigl(N^{-1/2+7\varepsilon}\bigr) \right) \\ &= \sqrt{\pi N} - \frac{1}{2} + \mathcal{O}\bigl(N^{-1/2+7\varepsilon}\bigr). \end{align*}

Case 2. For $$N^{1/2+\varepsilon} < k \leq N$$, noting that $$\log(1-x)$$ is decreasing in $$x$$,

\begin{align*} &\log \Biggl[ \frac{\prod_{i=0}^{k-1} ( 1-\frac{i}{N} )}{\prod_{i=0}^{k} ( 1-\frac{\lfloor i/2\rfloor}{N} )} \Biggr] \\ &\leq \int_{0}^{k-1} \log \left(1 - \frac{x}{N}\right) \, \mathrm{d}x - \int_{0}^{\lfloor\frac{k-1}{2}\rfloor+1} \log\left(1 - \frac{x}{N}\right) \, \mathrm{d}x- \int_{0}^{\lfloor\frac{k}{2}\rfloor+1} \log\left(1 - \frac{x}{N}\right) \, \mathrm{d}x \\ &\leq \int_{0}^{k} \log \left(1 - \frac{x}{N}\right) \, \mathrm{d}x - 2 \int_{0}^{k/2} \log\left(1 - \frac{x}{N}\right) \, \mathrm{d}x + \mathcal{O}(\log N). \end{align*}

Using the fact that $$\log\left(\frac{1-x/2}{1-x}\right) \geq \frac{x}{2}$$ for $$x \in [0, 1)$$, we easily find that this is further bounded by

$$- \frac{k^2}{4N} + \mathcal{O}(\log N).$$

This allows us to produce a tail bound

\begin{align*} \sum_{N^{1/2+\varepsilon} < k \leq N} \mathbf{E}[\tau_{k+1} \,;\, V_k < \infty] &\leq \sum_{N^{1/2+\varepsilon} < k \leq N} e^{-k^2/4N + \mathcal{O}(\log N)} \\ &\leq \left( e^{-N^{2\varepsilon}/4} + \int_{N^{1/2+\varepsilon}}^{\infty} e^{-x^2/4N} \, \mathrm{d}x \right) e^{\mathcal{O}(\log N)} \\ &\leq e^{-N^{2\varepsilon}/4 + \mathcal{O}(\log N)}. \end{align*}

Conclusion. Combining all the estimates, we conclude that the desired asymptotic formula $$\text{(2)}$$ holds. $$\square$$

• Your $E[T]$ showed I had missed a $1$ in my sum, now corrected - thank you Jun 9, 2022 at 7:58
• Thank you for that detailed proof! I didn't fully understood it yet but I will mark it as new answer. I hope Henry is ok with this. Jun 9, 2022 at 9:37
• @J.Doe - in general I am indifferent to votes and points here - and in this case Sangchul Lee has provided an analytical justification for the $\sqrt{\pi}$ compared to my empirical answer (which included searching for $1.77245384$ or $1.77245385$ and finding it in Twilight fan-fiction), so is better Jun 9, 2022 at 11:38

This is a collision problem, so if it follows the pattern of other collision problems it seems reasonable to guess that the answer will be $$O(\sqrt{N})$$.

If there have been $$2j$$ turns without stopping then the conditional probability B paints the next grain blue is $$\frac{N-2j}{N-j}$$

while if there have been $$2j+1$$ turns without stopping then the conditional probability R paints the next grain red is $$\frac{N-2j-1}{N-j}$$

so the probability they have not stopped after $$2j+1$$ turns is $$\frac NN\frac {N-1}{N} \frac {N-2}{N-1} \frac {N-3}{N-1} \cdots \frac{N-2j}{N-j} =\frac{ (N-j)!(N-j-1)!}{(N-2j-1)! N!} =\frac{2N-2j-1 \choose N}{2N-2j-1 \choose N-j}$$

and that they have not stopped after $$2j+2$$ turns is $$\frac NN\frac {N-1}{N} \frac {N-2}{N-1} \frac {N-3}{N-1} \cdots \frac{N-2j}{N-j}\frac{N-2j-1}{N-j} =\frac{ ((N-j-1)!)^2}{(N-2j-2)! N!}=\frac{2N-2j-2 \choose N}{2N-2j-2 \choose N-j-1}$$

To find the expected time when they stop, you have to sum these two sets of probabilities from $$j=0$$ upwards until they become $$0$$ (which they do after $$N+1$$ turns) plus the probability of $$1$$ they have not stopped by $$0$$ turns. This is easy enough to program though I do not see an easy way to get a closed form. Empirically, the expected number of turns seems to be close to $$\sqrt{N\pi }$$ and even closer to $$\sqrt{N\pi } - \frac12$$ for large $$N$$.

The $$\sqrt{N}$$ is not a surprise, but why this particular expression I do not know. For example using R:

expectedturns <- function(N){
probstillplaying <- 1
cumprobsum <- 1
j <- 0
while (probstillplaying  > 0){
probstillplaying <- probstillplaying * (N - 2*j) / (N - j)
cumprobsum <- cumprobsum + probstillplaying
probstillplaying <- probstillplaying * (N - 2*j - 1) / (N - j)
cumprobsum <- cumprobsum + probstillplaying
j <- j+1
}
return(cumprobsum)
}


with example expectations

expectedturns(1)
# 2
expectedturns(2)
# 2.5
expectedturns(3)
# 3
expectedturns(4)
# 3.416667
expectedturns(10^2)
# 17.30196
expectedturns(10^4)
# 176.7531
expectedturns(10^6)
# 1771.9546


Note that that $$\sqrt{1000000\pi }-\frac12 \approx 1771.95385$$ so very close. The error in the approximation seems to be $$O\left(\frac1{\sqrt{N}}\right)$$.

• This is related to the birthday problem where the expected number of people for the first match is about $\sqrt{\frac{\pi}2 N} + \frac23 + O\left(\frac1{\sqrt{N}}\right)$ Jun 8, 2022 at 23:02
• (repost of edied) Thanks for an answer. In some simulation I also got a factor close to $\sqrt{\pi}$. But it would be interesting why that is $\pi$ or if the true number is just very close to this. Has anyone any idea about this? Jun 8, 2022 at 23:37