1

Let $p$ be a real number between $0$ and $1$. Simone has a coin that lands heads with probability $p$ and tails with probability $1-p$; she also has a number written on a blackboard. Each minute, she flips the coin, and if it lands heads, she replaces the number $x$ on the blackboard with $3x+1$; if it lands tails she replaces it with $\frac x2$.

Given that there are constants $a,b$ such that the expected value of the value written on the blackboard after $t$ minutes can be written as $at+b$ for all positive integers $t$, compute $p$.

My only idea is that it feels like a binomial distribution but with a different random variable. So I know the expected value of the number of heads is $tp$, and it is $t(1−p)$ for the number of tails. But when I think about permuting those linear operations on $x$. I am totally muddled. I think that the critical point is that I do not know how to utilize the $at+b$ condition.

Any idea or hint would be appreciated.

Thanks to the hints by kimichi and lulu, I have gained quite a lot progress on this question. Below is the furthest that I have got.

$\left(\frac {5p+1}{2}\right)^{t-1}\left(1-\frac {5p+1}{2}-\frac px\right)=t\left(\frac px-1\right)+1+\frac {2}{1-5p}$

where $x$ is constant, and I need to find $p$ which is a probability; also, this equation holds for all positive integers $t$.

Remark. Problem solved by kimichi; also thanks for lulu's useful suggestion. Nevertheless, any other new approach is always welcome.

IncredibleSimon
  • 933
  • 1
    Till where did you reach? So that we may give hints accordingly. – SarGe Aug 21 '20 at 10:28
  • My only idea is that it feels like a binomial distribution but with a different random variable. So I know the expected value of the number of heads is $tp$, and it is $t(1-p)$ for the number of tails. But when I think about permutating those linear operations on $x$, I am totally muddled. I think that the critical point is that I do not know how to utilize the $at+b$ condition. Thanks for asking, SarGe. @SarGe – IncredibleSimon Aug 21 '20 at 10:40
  • Well, if you believe that $a,b$ exist you can solve for them just by considering small $t$. It's not obvious that $a,b$ exist (at least not to me) but it's easy to compute what they have to be. – lulu Aug 21 '20 at 10:44
  • 1
    Simon is a she? (and is she working on the Collatz problem?) – Gerry Myerson Aug 21 '20 at 11:23
  • LoL, it should be 'Simone'. Oh, thanks for mentioning the name 'Collatz'; I did not know that. @GerryMyerson – IncredibleSimon Aug 21 '20 at 12:22
  • Hi, lulu. I have no idea how to confirm $a$ and $b$ because they involve $x$ and $p$, and when I fix $t$ I can literally factor out a $t$ from any term, thus making the task of confirming $a$ and $b$ implausible. @lulu – IncredibleSimon Aug 21 '20 at 13:50
  • I don't understand. We know $E[0]=x$ yes? Therefore $a\times 0+b=x$ so $b=x$. Similarly, we know $E[1]=p(3x+1)+(1-p)\left(\frac x2\right)=a+b$ so you can compute $a$. Easy! Of course it relies on the strong assumption, but I expect it's easy enough to prove the strong assumption. – lulu Aug 21 '20 at 14:03
  • Wait, that assumption is for all positive integers $t$, so $t=0$ is not included. @lulu – IncredibleSimon Aug 21 '20 at 14:09
  • So, do $t=1$, $t=2$ then. But I expect it works just fine for $t=0$. – lulu Aug 21 '20 at 14:14
  • 2
    If the claim of the problem is that it works for some $p$ (or one $p$) but not for general $p$, then you'll need to compare a couple of values. The assumption tells us that $E[t+1]-E[t]$ is a constant ($=a$). Ok, so compute that difference for a couple values of $t$. – lulu Aug 21 '20 at 14:16
  • Oh, wow. That is genius, lulu! Thanks a lot. Let me try. @lulu – IncredibleSimon Aug 21 '20 at 14:18

2 Answers2

3

After $t$ tosses, Simone's expected fortune $f(t)$ is given by the following expression involving the $t$-th power of a matrix: $$\pmatrix{f(t)\\1}=\pmatrix{3p+q/2&p\\0&1}^t\pmatrix{x\\1}=M^t\pmatrix{x\\1},\tag1$$ where $$ M=\pmatrix{3p+q/2&p\\0&1}=pH +q T$$ where $$H = \pmatrix{3&1\\0&1}\text{ and } T=\pmatrix{1/2&0\\0&1}$$ are the update rules for Simone's fortune on seeing a single head or single tail: if head, $x\to3x+1$, and if tail, $x\to x/2$.

Put another way, $H$ transforms the vector $\pmatrix{x\\1}$ to the vector $\pmatrix{3x+1\\1}$, and $T$ transforms the vector $\pmatrix{x\\1}$ to the vector $\pmatrix{x/2\\1}$. A particular sequence of coin flip outcomes, such as "heads, tails, tails" generates the transformation of initial vector $v=\pmatrix{1\\1}$ to $TTHv$. The expectation of the outcome over all 8 possible three-long outcome sequences is $(pH+qT)(pH+qT)(pH+qT)v$, and so on, yielding (1) above.

Reconciling (1) with the $at+b$ Ansatz gives rise to an extra equation involving $p$. Namely, to avoid exponential dependence on $t$, the matrix $M$ must be of the form $M=\pmatrix{1&p\\0&1}$, that is, $3p+(1-p)/2=1$ or $p=1/5$. (The form $M=\pmatrix{0&p\\0&1}$ is not possible if $p$ is a probability.)

kimchi lover
  • 24,277
0

Here is another very clever way to tackle this problem, taught by a teacher in my academy.

Let $a_n$ denote the expected value after $n$ minutes.
$a_{n+1}=p(3a_n+1)+(1-p)(a_n/2)$
Then by the strong assumption $a_n=an+b$ which is linear, hence $a_{n+1}-a_n=a$. If we substitute the last-line expression for $a_{n+1}$ into this preceding equation, we will get $\left(\left(\frac {5p+1}{2}\right)-1\right)a_n+p=a$. Because $a_n$ varies with $n$, its coefficient must be $0$, leading to $p=\frac 15$.

IncredibleSimon
  • 933