2
$\begingroup$

Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ and lose that amount with probability $1-p$ ($p$ is known). We wish to reach target amount $T$ in the minimum expected number of plays. At each stage we can wager a different amount. To make the expectation simpler to compute we can assume that if the current amount goes below $S$ we incur a large number of additional plays, say $M$, and then our amount returns to $S$. I have a feeling that the optimal strategy for this situation depends on $p$ (and possibly $T$ and $M$) but I can't figure out how to show the optimal strategy.

$\endgroup$
  • 2
    $\begingroup$ 1. What have you tried? Where did you run across this problem? We expect you to make a serious effort, and to show us what you've tried and where you got stuck, and frame a more specific question. Right now it's just a dump of a problem. 2. I think we'll probably need more information. Are all quantities ($S$, $T$, each wager) an integer, or do you want to consider strategies with non-integral wagers? If integers, there is an obvious approach -- I suggest you spend a little more time on your own brainstorming how to approach it. $\endgroup$ – D.W. Jan 8 '15 at 5:04
  • 2
    $\begingroup$ Although this kind of thing definitely comes up in the analysis of probabilistic algorithms, I don't think this is a computer science question as it doesn't seem to have any computational aspects to it. $\endgroup$ – David Richerby Jan 10 '15 at 18:22
  • $\begingroup$ @DavidRicherby It's possible that some sort of recursive formulation could lead to an optimization algorithm, which is why I posted here. $\endgroup$ – user2566092 Jan 14 '15 at 20:35
  • $\begingroup$ @user2566092 Sure but mathematicians use recurrences, too. It's a standard technique for anything like this. $\endgroup$ – David Richerby Jan 14 '15 at 23:59
  • $\begingroup$ From my understanding of the question - the key-point here is to maximize wager while capping the probability of loosing (going broke) to a threshold level. Is it known that there isn't a neat mathematical solution for this? $\endgroup$ – user3467349 Mar 14 '15 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.