Usually my first impulse with this kind of problem is to whip up a quick Monte Carlo simulator to see how the numbers behave. So I wrote this:
#!/usr/bin/python
import random
totalRolls = 0
for i in xrange(0, 1000):
if i % 10 == 0:
print i
aCount = 0
bCount = 0
numRolls = 0
curBase = 1
while numRolls == 0 or bCount < curBase:
if random.random() > .5:
aCount += 1
if aCount == curBase:
curBase += 2
else:
bCount += 1
numRolls += 1
totalRolls += numRolls
print totalRolls / 1000.0
and then sent it off...and it hung around 970, generating increasingly massive numbers of rolls as the bully became horribly unlucky for a spell. Then I reran it and it finished nigh-instantly with an answer of 497.885. And reran it again and got 2910.299, and so on.
I don't think this problem is amenable to Monte Carlo approaches. :)
Edit: turned off HTML so it wouldn't mangle my less-than and greater-than signs.
