Can you easily prove $G (k) = \alpha \cdot F (k)$?

Question

Can you easily prove $G (k) = \alpha \cdot F (k)$?

Some time ago we did a very cumbersome proof but I am convinced that some good idea can provide a simple proof. This will be an auxiliary result in an investigation related to the Last -Success-Problem.

Let $\alpha \in \mathbb{R}$ and $p_i \in \mathbb{R}$ for all $i \in \mathbb{N}$

$$F(k)=p_{k-1} \left(\prod _{i=0}^{k-2} \left(1-\alpha\cdot p_i\right)\right)+ \left(1-p_{k-1}\right) \cdot F(k-1); F(0)=0$$

$$G(k)=\alpha\cdot p_{k-1} \left(\prod _{i=0}^{k-2} \left(1-p_i\right)\right)+\left(1-\alpha\cdot p_{k-1}\right) \cdot G(k-1) ; G(0)=0$$

Can you easily prove $G (k) = \alpha \cdot F (k)$?

Answer 1

Isolating the product from the $k^{th}$ recurrence relation for $F\,$:

$$ \prod _{i=0}^{k-2} \left(1-\alpha\, p_i\right) = \frac{F_k - \left(1-p_{k-1}\right) \, F_{k-1}}{p_{k-1}} $$

Substituting in the $(k+1)^{th}$ relation:

$$ \begin{align} F_{k+1} &= p_{k} \left(1-\alpha\, p_{k-1}\right) \frac{F_k - \left(1-p_{k-1}\right) \, F_{k-1}}{p_{k-1}}+ \left(1-p_{k}\right) \, F_k \\ &= \frac{p_k\left(1-\alpha\, p_{k-1}\right)+p_{k-1}(1-p_k)}{p_{k-1}}F_k - \frac{p_k\left(1-\alpha\,p_{k-1}\right)\left(1-p_{k-1}\right)}{p_{k-1}}F_{k-1} \\ &= \frac{p_k+p_{k-1}-\left(1+\alpha\right)p_kp_{k-1}}{p_{k-1}}F_k - \frac{p_k\left(1-\alpha\,p_{k-1}\right)\left(1-p_{k-1}\right)}{p_{k-1}}F_{k-1} \tag{1} \end{align} $$

Repeating the same steps for $G\,$:

$$ \prod _{i=0}^{k-2} \left(1-p_i\right) = \frac{G_k-\left(1-\alpha\, p_{k-1}\right) \, G_{k-1}}{\alpha\,p_{k-1}} $$ $$ \require{cancel} \begin{align} G_{k+1} &= \cancel{\alpha}\, p_{k} \left(1-p_{k-1}\right)\frac{G_k-\left(1-\alpha\, p_{k-1}\right) \, G_{k-1}}{\cancel{\alpha}\,p_{k-1}}+\left(1-\alpha\, p_{k}\right) \, G(k) \\ &= \frac{p_{k} \left(1-p_{k-1}\right)+p_{k-1}\left(1-\alpha\, p_{k}\right)}{p_{k-1}} G_k - \frac{p_k\left(1-p_{k-1}\right)\left(1-\alpha\,p_{k-1}\right)}{p_{k-1}}G_{k-1} \\ &= \frac{p_k+p_{k-1}-\left(1+\alpha\right)p_kp_{k-1}}{p_{k-1}}G_k - \frac{p_k\left(1-\alpha\,p_{k-1}\right)\left(1-p_{k-1}\right)}{p_{k-1}}G_{k-1} \tag{2} \end{align} $$

It follows from $(1)$ and $(2)$ that $F$ and $G$ satisfy the same homogeneous recurrence relation, so given $F(0)=G(0)=0$ all that's left to verify is that $G(1) = \alpha\, F(1)\,$.

Answer 2

Not an answer, but a reformulation in terms of probability.

If you can prove it for $p_i,\alpha\in[0,1]$ it would be true for all real values, since, for fixed $k,$ $F(k)$ and $G(k)$ are polynomials.

You are given a red coin and a pile of blue coins.

Each round, you toss the red coin and the next blue coin, with $\alpha$ the probability that your red coin lands heads and $p_i$ is the probability of the $i$th blue coin (used in the $i+1$st round) coming up tails.

Then $F(k)$ is the probability:

I win prize $F$ on round $k$, if either

1. I got heads on the blue coin and never got both red and blue heads in a previous round, or
2. I get a blue tails in round $k,$ and in round $k-1$ I won prize $F.$

And: $G(k)$ is the probability:

I win prize $G$ on round $k$ if either

1. I got both heads round $k,$ and never got a blue heads in a previous round
2. I got a tails this round, blue or red or both, and won prize $G$ In round $k-1.$

These seem very different.

In both cases, however, you cannot win the prize, lose it later, and then win it again. You can lose the prize any number of rounds, win it for a stretch, and then lose for the rest of time.

The first time you win $F$ is the first time you get a blue heads, and you win every round after until the first round you got a blue heads after the first round where you got a blue and red heads.

The first round of $G$ occurs if your first blue heads occurs with a red heads. Otherwise, you can never win $G.$ But after that, you continue to win until you get both blue and red heads again in the same round.

I think this lets us show inductively the relationship $G(k)=\alpha F(k).$ If $F_k’$ and $G_k’$ are the even that $k$ is the first round you win the prizes, and $F_k,G_k$ are the events that you win the prize on round $k,$ then we rasily get:

$$P(F_k’)=\alpha P(G_k’).$$

And it is left to prove that:

$$P(F_{k}\mid F_\ell’)=P(G_k\mid G_\ell)$$

for any $k\geq l.$

Let $M$ be the round of the first blue heads, and $N$ the first round both both a blue and red heads, and $P$ the first round of a blue heads after $N$ and $Q$ the first round of both red and blue heads after $N.$

Then $$\begin{align}F(k)&=P(M\leq k<P)\\G(k)&=P(M=N)P(N\leq k<Q)\\&=\alpha P(N\leq k<Q)\end{align}$$

So you want to prove:

$$P(M\leq k<P)=P(N\leq k<Q).$$

Those don’t seem related.

$$P(N\leq k<Q)=\left(\sum_{n=1}^k \frac{p_i\alpha}{1-p_i\alpha}\right)\prod_{i=1}^{k}(1-\alpha p_i)$$