A good old problem from an interviewer: Suppose there is a fair coin flipping game, which will be repeated for 100 times. A gambler bets $1 each time, collects $3 dollar if it shows a head and loss the bet if it shows a tail. Gambler A bets at every single round, what's his expected return? Gambler B has a bankroll of $50, will his expected return be the same, greater or smaller than that of A? Fairly standard stuff.....I answered the question, the interviewer followed up.... Now, I give you a computer how can you evaluate the expected return of B precisely. Exhausive search: too slow, Monte Carlo simulation: not precise enough; then I took out a pen, tried to simplify the problem a bit (e.g. see if reflection principle may help etc)... but, right at that point, the interviewer said I should not make things more complicated than it should: there should exist an easy programming solution (not analytical one). I got stuck. Any idea how should I calculate that?

Sorry, gambler B bets max every time??? it's not clear from the statementIf so, his probability to have any money at the end is 2^-100If he does win every bet, his wealth will be 50*3^100, since he triples his money each time. The product of these should give the expected value for gambler B. But probably I mis-understood his strategy or something.e.g. E(value) = (1 - 2^-100) * 0 + (2^-100)*50*(3^100) = 50 * 1.5^100. That number isn't insanely big...you can store it as a double easily I think.

I'd create a modified version of Pascal's triangle (to accommodate the bankruptcy condition for gambler B). It would need only one nested double-loop to generate the full triangle and a second to analyze the results (with a bit of clever logic, one can embed the analyzer into the generator, but I'd fear adding bugs in the looping and access logic). I know this might be what the interviewer called "exhaustive search" but we're only talking a few tens of thousands of multiply-accumulates, so the execution time should be sub-millisecond.

QuoteSorry, gambler B bets max every time??? it's not clear from the statementIf so, his probability to have any money at the end is 2^-100Sorry for the confusion. The gamblers can bet $1 in each game. Therefore, if he wins 100 games, he can earn $200 (net gain is $2 in a game). If he has a bankroll >=$100 at start and loses 100 games, he will loss $100.

Got it...now I understand thanks

Binormial tree with stopping strategy. Using backtrack to get the expected payoff.I guess.