# We can convert one apple to mango or vice versa in one move with equal probability. Expected moves by which only one kind of fruit will be left?

Given $$a$$ apples and $$b$$ mangoes, where $$a$$ and $$b$$ can be non negative numbers, we can convert one apple to mango or vice versa in one move. What is the expected number of moves after which only one kind of fruit will be left, i.e, one of the following condition satisfies:

1. #apples = $$a$$+$$b$$ and #mangoes = 0
2. #apples = 0 and #mangoes = $$a$$+$$b$$

My attempt: I thought of recurrence relation $$E(a,b) = 1 + \tfrac12 E(a-1,b+1) + \tfrac12 E(a+1,b-1)$$ (thanks @henry for correcting it) but could not moved further from this. Also, I thought that expected number of moves will only depend on max($$a$$,$$b$$). I am not sure but I have strong intuition that this is correct.

• For context, this question was asked in one of the programming contest I was giving few days back. Jul 13, 2021 at 10:15
• It is worth working this out for small $a$ and $b$, spotting the multiplication pattern, and then proving by induction Jul 13, 2021 at 10:19
• @Henry If a=$0$ or b = $0$, expected moves will be obviously 0. For $a$ = 1 and $b$ = 1, expected moves will be 1. For $a$=1 and $b$=2, expected moves will be 2. I was not able to calculate for further numbers. Jul 13, 2021 at 10:25

Hints:

• Except when $$a=0$$ or $$b=0$$, you will have $$E[N_{a,b}]=1+\tfrac12 E[N_{a-1,b+1}]+\tfrac12 E[N_{a+1,b-1}]$$

• As you have spotted, $$E[N_{a,0}]=E[N_{0,b}]=0$$

• It is worth working $$E[N_{a,b}]$$ out for small $$a$$ and $$b$$, spotting the multiplication pattern, and then proving by induction

• Okay, my recurrence relation was wrong. Updated in question. But how will we calculate further states from this relation? For calculating $E[N_{a,b}]$ we need future as well as past state. Jul 13, 2021 at 10:48
• Is the result $ab$? Jul 13, 2021 at 10:51
• It is, though you might want to prove (a) it satisfies the recurrence and (b) nothing else will Jul 13, 2021 at 10:52
• @Snoop No. For reference question link: my.newtonschool.co/playground/code/crm33y2jcf Jul 13, 2021 at 10:57
• @VivekMoar In order to calculate the states from the relation, you have to solve a system of linear equations. You have $a+b+1$ variables $E[N_{k,a+b-k}],\;k\in\{0,\ldots,a+b\}$ and $a+b+1$ equations, which are $E[N_{0,a+b}]=0,$ $E[N_{a+b,0}]=0$ and $a+b-1$ equations of the type $-\frac{1}{2} E[N_{a-1,b+1}] + E[N_{a,b}] - \frac{1}{2} E[N_{a+1,b-1}] = 1.$ Jul 13, 2021 at 11:27