5
$\begingroup$

I am preparing for an exam in probability theory and I bumped against a question I can't solve.

Given are an integer starting capital $k$, an end goal capital $m$ and a period of $n$ days. Each day I can bet some integer amount $X$ of my choosing $(X \leq k)$ on an unfair coin landing on heads. The probability the coin lands on heads is different each day, with $p_i$ denoting the probability of it landing on heads on day $i$ with $i \in (1,...,n)$. If the bet is successful, I increase my capital by $X$, if not I lose $X$ amount. (All probabilities $p_1, p_2,..., p_n$ are known before the betting process starts).

The question is: With an optimal betting strategy, what is the probability of achieving capital at least equal to $m$ after $n$ days?

An example input: $n = 5, k = 2, m = 20, p_1 = 0.3, p_2 = 0.5, p_3 = 0.2, p_4 = 0.7, p_5 = 1.0$

Though not from a homework, if this question falls under the category of questions one should solve by themselves or look for help from a tutor or elsewhere, please tell me, I will take it down. Any advice as to how to approach the problem would be awesome though.

$\endgroup$
10
  • $\begingroup$ Do you get to know the probability of heads before you decide how much to bet each day? $\endgroup$ Commented Jul 19, 2020 at 22:15
  • $\begingroup$ yes, you do, I should add this to the question. $\endgroup$
    – Baksel
    Commented Jul 19, 2020 at 22:17
  • $\begingroup$ I suppose it might also make a difference whether you are told only the probability for each day one day at a time, or if you get the full list of probabilities for the whole experiment on the first day. $\endgroup$ Commented Jul 19, 2020 at 22:24
  • $\begingroup$ noted, added to the question description $\endgroup$
    – Baksel
    Commented Jul 19, 2020 at 22:28
  • $\begingroup$ From what you've written, does it mean that after some time, e.g. $k$ days, the probability of heads=1? $\endgroup$
    – Alex
    Commented Jul 19, 2020 at 22:33

6 Answers 6

3
$\begingroup$

It's not a full solution, but for a fixed bet amount $k$, so the states/fortune increments are multiples of $k$ the mean first hitting time of the next state (e.g. you start with $X$ coins, $s_0 = X, s_1 = X+k$),

$$\mathbf{E}T_{s_0, s_1}= \sum_{j=1}^{2k+1}\mathbf{E}[T_{s_0, s_1}|D_j]P(D_j)$$

where $D_j$ is the number of days it took to reach the new state. Since you bet every day, the number has to be odd, e.g. $P(D_1)=p_1, P(D_3) = (1-p_1)p_2p_3$, and so on.

Again, it's not a full solution, perhaps there are better approaches (m.b. using Geometric probability/Coupon Collector's Problem), but this will get you started hopefully.,

$\endgroup$
2
$\begingroup$

I don't think there is a general strategy for problems like this unless there is a lot of symmetry (constant probability of heads) or a lot of throws. In your example, you need to increase your capital by a factor $10$, so three wins do not suffice. One approach is to count on winning four, decline to bet the $0.2$, and bet enough that four wins gets you the increase you need. That has a probability of success of $0.105$. You might as well bet your whole bankroll each time, because one loss guarantees you fail anyway.

The other approach is to try and succeed if you get four wins and one loss. If you bet a fraction $f$ of your capital you will have $(1+f)^4(1-f)$ times your capital at the end. We would need that to be $10$, so we solve $(1+f)^4(1-f)=(1+f)^3(1-f^2)=10$. The $1+f$ terms are at most $2$, and the $1-f^2$ term is at most $1$, so there is no solution. Follow the first approach.

$\endgroup$
2
  • $\begingroup$ What would be the approach if the probabilities of heads were the same? $\endgroup$
    – Baksel
    Commented Jul 20, 2020 at 0:09
  • $\begingroup$ In this case it doesn't change because you need to win almost all the time. If there are a lot of tosses you try to find the betting strategy that requires you to win the fewest of them to get to where you want to be. As you get toward the end of the game, you may be desperate and increase your bet fraction. $\endgroup$ Commented Jul 20, 2020 at 0:40
2
$\begingroup$

Partial solution:

Let $(x_1,...,x_n)\in [-1,1]$ be our sequence of bets on the $n$ days, with $x_i$ meaning that we bet $100|x_i|\%$ of our current capital, with the bet being on head if $x_i>0$, and on tails if $x_i<0$.

Let $(r_1,...,r_n)\in \{0,1\}$ be the sequence of realizations of the coin, with $r_i=1$ meaning head.

Then the probability that the sequence $(x_1,..,x_n)$ of bets leaves us with a capital of at least $m$ is the sum over all probabilities of realizations $(r_1,...,r_n)$ for which holds $$k \cdot\prod_{i=1}^n (1+x_i\cdot(-1)^{r_i})\ge m$$

So in other words, we obtain the following optimization problem:

$$ \max_{(x_1,...,x_n)\in[-1,1]} \sum_{(r_1,...,r_n)\in \{0,1\}^n} \left(\sum_{i=1}^n \left(1-r_i + p_i·(2·r_i - 1)\right) \delta_{\prod_{i=1}^n (1+x_i\cdot(-1)^{r_i})\ge\frac mk}\right) $$

Where $\delta$ is the Dirac-Delta.

Since the inner sum has $2^n$ summands, this maximization problem is only really solvable for small $n$.

It is probably possible to rewrite this optimization problem to fit better within the existing optimization frameworks, though this goes beyond my knowledge.

$\endgroup$
1
$\begingroup$

If there's no ideas how to solve specific case, in general I would solve it in kind of dynamic programming way. Since numbers are not so big you can probably do it by hand

First, notice that it never makes sense to bet more than you need to get $m$.

Let $d_{ij}$ be a probability to win if you start after $i$ days and your capital is $j$ for each $0 \le i \le n, 0 \le j \le m$.

What is $d_{nm}$?

What is $d_{nj}$ for $j \ne m$ ?

Now, go in order of decreasing $i$ and solve for each $i$ and $j$: bruteforce your bet from 0 to $\min(j, n-j)$ and choose the best probability to win.

Now answer is $d_{0k}$

Note, that you can optimise you calculations:

  1. You know all of $d_{i0}$, $d_{in}$
  2. You can skip some of the number you won't care about, e.g since the last throw is always good, you know, that you'll always bet maximal allowed bet this turn
  3. You don't need to calculate all of $d_{0j}$
  4. You don't need $d_{1,5}$ and similar.
$\endgroup$
2
  • $\begingroup$ wonderful idea, It worked for this input example and a couple others, I will try to write out the recursive formula. Thank you :) $\endgroup$
    – Baksel
    Commented Jul 20, 2020 at 10:31
  • $\begingroup$ Well, it works more or less by construction (but please do understand why it works, I think it's a good exercise). The problem is that it's not easy to compute by hand $\endgroup$
    – RiaD
    Commented Jul 20, 2020 at 10:39
1
$\begingroup$

It seems to me that this question is much easier than people are making it out to be, although I might be wrong here.

First: The optimal strategy will at each betting day be the one that increases the expected gains the most. Therefore you should bet all your capital if $p>0.5$, since the expected return is the largest.

Second: The probability of having capital after n days with the optimal strategy is equal to the product of the probabilities of the days you bet, so hence: $$P(\text{"Return larger than m"}) = \begin{cases}\prod_{bet\in bets}p_{bet}&2^{|bets|}k>m\\0&\text{else}\end{cases}$$ For your example $n=5,k=2,m=20,p_1=0.3,p_2=0.5,p_3=0.2,p_4=0.7,p_5=1.0$, we have that the probability of having capital left is: $p_4p_5=0.7$, but since $m=20$ the probability that we end up with a return greater or equal to this value is 0.

I think most other people here have attempted to solve the much harder problem of optimizing the probability of having the return be greater or equal to m, but from what I understand that is not the actual assignment, so the solution I presented here should be correct.

Also, this problem reminds me a lot of the St. Petersburg paradox, which I quite like.

$\endgroup$
2
  • $\begingroup$ Are you considering that "optimal" means "one that maximizes EV?" It might be what is meant but it's very unnatural given the problem statement $\endgroup$
    – RiaD
    Commented Jul 20, 2020 at 11:05
  • $\begingroup$ Yes, and you have a point that its a bit unnatural. $\endgroup$ Commented Jul 20, 2020 at 15:42
1
$\begingroup$

You can also try to solve each particular case separately, some of them would be easier and some of them are harder.

For you proposed input:

  1. Obviously the game is equivalent to get at least 10 before the last turn. If you don't you can't double. If you do, you will success 100%

  2. There are 2 kind of strategies

  • That do not bet anything on the first turn. In that case you have to win 4 next times, so the probability is not better then $0.5 \cdot 0.7 \cdot 0.2 \cdot 1$ and we know that there's a better strategy that gives us at least $0.5 \cdot 0.7 \cdot 0.3 \cdot 1$ (why?), so this type of strategy is not interesting.

  • That bet something on the first turn. In that case they have to win on the first bet (otherwise we'll have 1 and will need to get 20 which is impossible in 4 turns(why?)). Then we may as well bet everything on the first turn (why?).

So we basically know the first and the last our turns and we have smaller problem, where $n=3, k=4, m=10, p_1=0.5,𝑝_2=0.2,p_3=0.7$ (and we need to multiply result by 0.3). Now you can use the more general idea but which will require less calculation now or continue with solving particular case

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .