# Placing 2N bricks on two piles of N

$2N$ bricks are to be placed on two piles of $N$. The bricks are placed one by one. If one of the piles is already complete(has $N$ bricks) all the successive bricks will be placed on the other pile. Otherwise there is equal probability that a brick will be placed on either of the two piles.

Let $k$ be the position which denotes the $k$th brick in a pile. If $M$ bricks have been placed already, what is the probability that the $k$th position of a given pile is occupied?

Trivially, if $M<k$ then the probability is $0$. Also if $M\geq N+k$ then the probability is $1$ since there is no way to place $N+k$ bricks without occupying the $k$th position of any pile. So the problem is really for the case $k\leq M<N+k$.

Also, when $M=k$ all the $k$ bricks should go to one pile, so the probability should be $1/2^k$. What about the other cases?

• If $k\leq M<N+k$, then you want the probability that at least $k$ of the $M$ bricks have, say, left chosen for them. This is binomial. Apr 17, 2016 at 13:36
• So is it $M \choose k$*$(1/2^k)$ Apr 17, 2016 at 13:39
• You're close. First, by the formula for binomial probability it's $\binom{M}{k}(1/2^M)$. Second, since we want at least $k$ bricks, not exactly $k$ bricks to be chosen for the left pile, we get the sum $\sum_{l=k}^M\binom Ml(1/2^M)$. Apr 17, 2016 at 13:45
• Shouldn't the factor be $1/2^l$ and not $1/2^M$ in the summation? Apr 17, 2016 at 13:48
• I see. If $l$ bricks went, say left, then the others should go right. Apr 17, 2016 at 13:52