4

Suppose that we have two towers of equal height $N$, each tower consisting of $N$ coins piled on top of each other. Now suppose we have a machine or whatever that takes a coin from one of the towers and move it to the other one. That is, a coin can be moved from tower $A$ to tower $B$ with $50\%$ probability or from $B$ to $A$ with $50\%$ probability.

The question is: How many such moves on average will it take before the height of either tower $A$ or tower $B$ i zero?

It can be transformed into an equivalent problem, where a machine prints $0$ or $1$ with equal probability and we want to find the average length of the sequence before there are $N$ more $0$'s than $1$'s or the other way around.

I think I have solved it, though I'm not sure my though process is correct.

The solution is:

Let $f(n)$ be the average number of steps, where $n$ is the height of the towers. Now, suppose we double the height of each tower and we want to find $f(2n)$.

By definition, the average number of steps required before either tower $A$ or $B$ have height $n$ is $f(n)$. From here, there is an equal probability that we either go back to the starting position or that the tower becomes empty.

So: $$f(2n) = f(n) + 0.5[f(n) + f(2n)] + 0.5f(n)$$

Solving for $f(2n)$ we get:

$$f(2n) = 4f(n)$$

Hence, $f(n)$ must take the form $f(n)=cn^2$, where $c$ is a constant.

Since $f(1) = 1 \Rightarrow c=1$, the solution is: $f(n) = n^2$.

Community
  • 1
Boazobargi
  • 47
  • I'm not 100% here, but I think this is equivalent to the problem of the Nth return to zero for a simple random walk? In which case you might be able to compare your answer with the literature on that topic. Your answer looks correct from what I remember. – Chill2Macht Apr 28 '16 at 02:33
  • 1
    @William If the pile sizes are $m, n$ I think it's equivalent to how many steps it takes to reach the origin or $m+n$ having started at $m$ (or $n$). Edit: Just realized the tower sizes are equal size, but I don't know if that reduces to returning to zero from $n$ times a constant – MT_ Apr 28 '16 at 02:42
  • I have one question about your argument: Sure, the number of steps before either tower has height $n$ is $f(n)$, but I don't know if that alone implies that the recurrence you state holds. (For example, it is very much possible that we get to zero before $f(n)$ steps -- how is that accounted for?) To me it kind of seems like to me that you're taking average case behavior and saying that by taking averages over all of the steps you will still get the right answer, which is somewhat questionable to me – MT_ Apr 28 '16 at 02:47
  • @Soke I'm not sure either; I was lazy and didn't think about it as much as I should. – Chill2Macht Apr 28 '16 at 02:55
  • 1
    @William I don't think it is: in the case where we just have to return to origin, it is possible we go way to the right (in particular, past $2n$), but in this formulation we call it a win once we get to $2n$. – MT_ Apr 28 '16 at 03:03

1 Answers1

0

A start: Try modeling the behavior as a random walk where we start at $0$ and try to get to $-n$ or $n$.

We can model this behavior per-step as a binomial distribution.

In particular, after one step we have a $1/2$ probability to be on $-1$ and $1/2$ probability to be on $1$.

After $k$ steps $k < n$, we have a $\frac{1}{2^k} {k \choose m}$ probability to be at position $m$ and the same probability for $-m$.

Hence, the least number of steps we have to take is $n$ and this happens with probability $2 \frac{1}{2^n} {n \choose n} = \frac{1}{2^{n-1}}$.

We continue the binomial distribution behavior, taking into account that those probabilities who have reached the end are now "done" and so do not contribute to the next layer of the distribution (thinking in terms of Pascal's triangle). Perhaps we can get something good from modelling it like this.

MT_
  • 19,603
  • 9
  • 40
  • 81