A Question about Expected Value

Question

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.

Answer 1

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.)

Answer 2

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$.