A unit segment [0, 1] is colored randomly using two colors, white and black, according to the following procedure. The segment starts white. On each step, we choose two random points a and b on the segment and switch the color of each point between them. (The points a and b are uniformly distributed on [0, 1]). We repeat this procedure n times, choosing two inde- pendent points on each step. What is the probability that the midpoint 1/2 of the segment [0, 1] is black after n steps? (n is arbitrary) Also : What is the expected total length of the black region after n steps?

  • 2
    $\begingroup$ For each step, the probability that the midpoint changes color is $1/2$. $\endgroup$ – Arthur Jul 24 '16 at 7:26

The point $z\in[0,1]$ is black after $n$ steps exactly if an odd number of the $2n$ points chosen are on either side of it. The probability for this is

\begin{align} \sum_{k\text{ odd}}\binom{2n}kz^k(1-z)^{2n-k} &= \frac12\left(\sum_k\binom{2n}kz^k(1-z)^{2n-k}-\sum_k(-1)^k\binom{2n}kz^k(1-z)^{2n-k}\right) \\ &= \frac12\left(1-(1-2z)^{2n}\right)\;. \end{align}

For $z=\frac12$, this is $\frac12$ for any $n\ge1$. Integrating the probability over $[0,1]$ yields the expected length of black after $n$ steps:

$$ \int_0^1\frac12\left(1-(1-2z)^{2n}\right)\mathrm dz=\frac12-\frac1{4n+2}\;. $$

We can also compute the variance of this length. This is the same as the variance of the length of white, which I find a bit easier to think about. To find the expected square of the length of white, we need the probability that two points $x\le y$ are both white after $n$ steps. This occurs exactly if an even number of the $2n$ points chosen are in each of the three segments on either side of $x$ and $y$ and between them. The probability for this is

\begin{align} & \sum_{k\text{ even}}\binom{2n}kx^{2n-k}(1-x)^k\cdot\frac12\left(1+\left(1-2\cdot\frac{y-x}{1-x}\right)^k\right) \\ ={}& \sum_{k\text{ even}}\binom{2n}kx^{2n-k}\cdot\frac12\left((1-x)^k+(1+x-2y)^k\right) \\ ={}& \frac14\left(1+(1-2x)^{2n}+(1-2y)^{2n}+(1+2x-2y)^{2n}\right) \end{align}

Thus the variance of the length of white (or black) is

\begin{align} & 2\int_0^1\int_0^y\frac14\left(1+(1-2x)^{2n}+(1-2y)^{2n}+(1+2x-2y)^{2n}\right)\mathrm dx\,\mathrm dy-\left(\frac12+\frac1{4n+2}\right)^2 \\ ={}& \frac14\left(1+\frac1{2n+1}+\frac1{2n+1}+\frac1{2n+1}-\left(1+\frac1{2n+1}\right)^2\right) \\ ={}& \frac14\left(\frac1{2n+1}-\left(\frac1{2n+1}\right)^2\right) \\ ={}& \frac n{2(2n+1)^2}\;. \end{align}

  • $\begingroup$ Thanks bud! That helped significantly :) this was a contest problem I didn't reap full pointage and I see why now 👽👍. I basically said the same thing for first part as u, about picking the second point opposite the first which is 1/2 . The part u brought to light was using integral to find length!! Thanks again as this problem was really eating at me ;) $\endgroup$ – Randin Jul 24 '16 at 15:02
  • $\begingroup$ Where else can I find this problem or similar ones ? $\endgroup$ – Randin Aug 9 '16 at 6:08

Take a point $z\in [0,1]$. First, we calculate the probability that $z$ lies in a black region after one step. Certainly, this happens only if the two randomly chosen points $x$ and $y$ satisfy $x<z<y$ or $y<z<x$. So the probability of this is $$(P(x<z)\cdot P(y>z))+(P(y<z)\cdot P(x>z)) = 2(P(x<z)\cdot P(y>z))=2z(1-z)$$ To find the probability that $z$ is black after $n$ steps, we can imagine this as running the above trial $n$ times, and "succeeding" in exactly an odd number of trials. Let $P_k$ denote the probability that $z$ lies between the two points in exactly $k$ trials. Then $$P_k = \binom{n}{k}(2z-2z^2)^k(2z^2-2z+1)^{n-k} = (2z)^k\binom{n}{k}(1-z)^k(2z^2-2z+1)^{n-k}$$ For $z = \frac{1}{2}$, the sum of this over all odd $k$ reduces to $\frac{1}{2}$.

  • $\begingroup$ Where does the $(-1)^k$ term come from? It might be clearer to go straight to the right-hand side in the final equation, since you already have the factored form above. Finally, for the expected total length of the black region, you should integrate the sum over odd k over [0,1]. $\endgroup$ – Shagnik Jul 24 '16 at 7:43
  • $\begingroup$ The $(-1)^k$ was a mistake. Thank you. $\endgroup$ – florence Jul 24 '16 at 7:45
  • 1
    $\begingroup$ Using the usual trick that $\sum_{k\text{ odd}} a_k = \frac12 \big( \sum_k a_k + \sum_k (-1)^k a_k \big)$, it's not hard to show that the sum over all odd $k$ is $\frac12(1+(1-2z)^{2n})$. Integrating this expression over $z\in[0,1]$ yields the answer $\frac12 + \frac1{4n+2}$. $\endgroup$ – Greg Martin Jul 24 '16 at 7:48
  • 1
    $\begingroup$ @GregMartin: The plus sign yields the sum over the even terms, so you actually calculated the expected length of white. $\endgroup$ – joriki Jul 24 '16 at 8:17
  • $\begingroup$ Thanks joriki, something felt a little off. $\endgroup$ – Greg Martin Jul 25 '16 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.