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?
Best Answer
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]$:
Indeed, we claim:
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$