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?

Question

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?

Answer 1

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$

Answer 2

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)$.