2
$\begingroup$

$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?

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Arthur
    Apr 17, 2016 at 13:36
  • $\begingroup$ So is it $M \choose k$*$(1/2^k)$ $\endgroup$ Apr 17, 2016 at 13:39
  • $\begingroup$ 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)$. $\endgroup$
    – Arthur
    Apr 17, 2016 at 13:45
  • $\begingroup$ Shouldn't the factor be $1/2^l$ and not $1/2^M$ in the summation? $\endgroup$ Apr 17, 2016 at 13:48
  • 1
    $\begingroup$ I see. If $l$ bricks went, say left, then the others should go right. $\endgroup$ Apr 17, 2016 at 13:52

0

You must log in to answer this question.

Browse other questions tagged .