<s>[INST] Profit maximization with Markov Chains 
Problem : An opera singer is due to perform a long series of concerts. Having a bad temper, they are liable to pull out each night with probability $1/2$ . Once this has happened they will not sing again until the promoter convinces them of the promoter’s high regard. This the promoter does by sending flowers every day until the singer returns. Flowers costing $x$ thousand pounds, $0 ≤ x ≤ 1$,
bring about a reconciliation with probability $\sqrt{x}$ .The promoter stands to
make $£750$ from each successful concert. How much should they spend on flowers?

I'd like to have solution verification or alternative approaches .
(Problem's from exercise 1.10.4 of Markov Chains by J.R. Norris)

Interpretation : I suppose the singer pulls out independent of the past given that they performed last night.  Also I suppose $x$ is "how much they[the promoter] should spend on flowers", which is time-homogeneous. I suppose promoter wants to maximize their expected profit.

Plan : I'll use a 2 state MC to track whether the singer performs or not . Then I'll find the long-run proportion of time that singer performs : $v(x)$ . Finally $x$ will be the maximizer of  $f(x) = 750v(x)-x(1-v(x))$ , I think $f(x)$ should approximate the expected profit .
If the MC turns out to be irreducible , then by Theorem 1.10.2 , $v(x)$ will almost surely be the inverse of expected return time of the state that the singer performs .

Theorem 1.10.2  Let $P$ be irreducible and let $\lambda$ be any distribution . If $(X_n)_{n\ge 0}$ is Markov$(\lambda,P)$ then
$$
\mathbb{P}\left( \frac{V_i(n)}{n} \to \frac{1}{m_i} \text{ as } n \to \infty  \right) = 1 
$$
where $V_i(n) = \sum_{k=0}^{n-1} 1_{\{X_k = i\}}$ and $m_i$ is expected return time to state $i$ .


Attempt :
Let
$(X_n)_{n\ge 0}$ be a Markov chain such that the initial distribution is uniform and
$
X_n = 
\left\{\begin{array}{cc}
1 & \text{if singer performs } \\
0 & \text{else } 
\end{array}\right.
$ . So transition probabilities are
$$
\left\{\begin{array}{cc}
p_{10} = 1/2  , &  p_{11} =  1/2 \\
p_{01} = \sqrt{x} , & p_{00} = 1 - \sqrt{x}
\end{array}\right.
$$ with $x\in (0,1] $ . $(X_n)_{n\ge 0}$ is irreducible on state space $\{0,1\}$  . The expected return time to $1$ is  $m_1 = 1 + \frac{1}{2}\frac{1}{\sqrt{x}} $ , so
$v(x) = 1/m_1  $  .
When $x = 0 $ , $\{0\}$ becomes the absorption state , the expected profit is
$\frac{1}{2} 750 \sum_{x=1}^{\infty}  x\left(\frac{1}{2}\right)^x  = \frac{1}{2} 750(2) = 750 $ .
Numerically I found the maximum of $f(x) , x\in (0,1]$ is around $500$ at $x=1$ .
So should I conclude that he should spend $x=0$ GBP on her ?
 [/INST] Suppose the opera singer has $n$ performance days. Let $X_i = \begin{cases} 1 & \text{if performance occurs on day $i$}\\ 0 & \text{else} \end{cases}$ for $1 \leq i \leq n$.
Then the profit is $M = \left (\frac{3}{4} + x \right )\left (X_1 + \dots + X_n\right ) - nx$ (in thousands of pounds).
We have transition matrix
$$P = \begin{bmatrix} 
1 - \sqrt{x} & \sqrt{x}\\
\frac{1}{2} & \frac{1}{2}
\end{bmatrix} = \begin{bmatrix} 
1 & -2\sqrt{x}\\
1 & 1
\end{bmatrix} \begin{bmatrix} 
1 & 0\\
0 & \frac{1}{2}-\sqrt{x}
\end{bmatrix} \begin{bmatrix} 
\frac{1}{1 + 2\sqrt{x}} & \frac{2\sqrt{x}}{1 + 2\sqrt{x}}\\
-\frac{1}{1 + 2\sqrt{x}} & \frac{1}{1 + 2\sqrt{x}}
\end{bmatrix},$$
so
\begin{align*}
X_1 &= \begin{bmatrix}
\frac{1}{2}\\
\frac{1}{2}
\end{bmatrix}\\
\implies X_i = X_1^TP^{i-1} &= \begin{bmatrix}
\frac{1}{2}\\
\frac{1}{2}
\end{bmatrix}^T \begin{bmatrix} 
1 & -2\sqrt{x}\\
1 & 1
\end{bmatrix} \begin{bmatrix} 
1 & 0\\
0 & \left (\frac{1}{2}-\sqrt{x}\right )^{i-1}
\end{bmatrix} \begin{bmatrix} 
\frac{1}{1 + 2\sqrt{x}} & \frac{2\sqrt{x}}{1 + 2\sqrt{x}}\\
-\frac{1}{1 + 2\sqrt{x}} & \frac{1}{1 + 2\sqrt{x}}
\end{bmatrix}\\
&= \begin{bmatrix}
\frac{1 - \left (\frac{1}{2} - \sqrt{x} \right )^i}{1 + 2\sqrt{x}}\\
\frac{2\sqrt{x} + \left (\frac{1}{2} - \sqrt{x} \right )^i}{1 + 2\sqrt{x}}
\end{bmatrix}
\end{align*}
Thus,
\begin{align*}
\mathbb{E}[X_i] &= \frac{2\sqrt{x} + \left (\frac{1}{2} - \sqrt{x} \right )^i}{1 + 2\sqrt{x}}\\
\implies E_n(x) = \mathbb{E}[M] &= \left ( \frac{3}{4} + x \right ) \left (\sum_{i = 1}^n \frac{2\sqrt{x} + \left (\frac{1}{2} - \sqrt{x} \right )^i}{1 + 2\sqrt{x}}\right ) - nx\\
&= \left ( \frac{3}{4} + x \right ) \left (\frac{(4nx + 1) + 2(n - 1)\sqrt{x} - 2\left (\frac{1}{2} - \sqrt{x}\right )^{n+1}}{\left (1 + 2\sqrt{x}\right )^2}\right ) - nx\\
&= \left ( \frac{3}{4} + x \right ) \left (\frac{1 - 2\sqrt{x} - 2\left (\frac{1}{2} - \sqrt{x}\right )^{n+1}}{\left (1 + 2\sqrt{x}\right )^2}\right ) + \frac{n\left (3\sqrt{x} - 2x \right )}{2 + 4\sqrt{x}}
\end{align*}
Thus as $n \to \infty$, the total profit is infinite as long as $3\sqrt{x} > 2x$, i.e. $x > 0$.
On the other hand, if we wanted to maximise the eventual daily profit then we go back to our distribution for $X_i$ and take $i \to \infty$ to get $X = \begin{bmatrix}
\frac{1}{1 + 2\sqrt{x}}\\
\frac{2\sqrt{x}}{1 + 2\sqrt{x}}
\end{bmatrix}$, so the expected profit made is $\left (\frac{3}{4} + x\right )\mathbb{E}[X] - x = \frac{3\sqrt{x} - 2x}{2 + 4\sqrt{x}}$, which is maximised when $x = \frac{1}{4}$.
Therefore, to maximise daily profit, the club should spend $250$ pounds.
</s>