Context : After reading answers to my previous post (you don't need to read , this post is self sufficient) , I obtained a strange result which I'm unable to explain .

Problem : An opera singer is due to perform a long series of concerts. Having a bad temper, singer is liable to pull out each night with probability $f(a)\in (0,1]$ . Once this has happened singer will not sing again until the promoter convinces singer of the promoter’s high regard. This the promoter does by sending flowers every day until the singer returns. Flowers costing $b$ thousand GBP , $0 ≤ b ≤ 1$, bring about a reconciliation with probability $g(b) \in (0,1] $ .The promoter stands to make $a$ thousand GBP from each successful concert , $0 ≤ a ≤ 1$ . How much should promoter spend on flowers?

This's equivalent to finding the expected eventual daily profit then maximizing . The later is irrelevant here .

This could be solved by (thanks to user Sharky Kesa):

Suppose the opera singer has $n$ performance days . Let $$ U_i = \left\{ \begin{array}{cc} 1 & \text{ if performance occurs on day } i \\ 0 & \text{ else } \end{array} \right. $$ for $i\in \{1,...,n\} $ . $(U_i)_{i\ge 0}$ is a Markov chain on state space $\{0,1\}$ . The profit is $M = (a + b)(U_1+...+U_n) - nb $ .

We have transition matrix $$ P^n = \begin{bmatrix} 1 - g(b) & g(b) \\ f(a) & 1 - f(a) \end{bmatrix}^n = \begin{bmatrix} 1 & 1 \\ 1 & - \frac{f(a)}{g(b)} \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & (1-f(a)-g(b))^n \end{bmatrix} \begin{bmatrix} \frac{f(a)}{f(a)+g(b)} & \frac{g(b)}{f(a)+g(b)} \\ \frac{g(b)}{f(a)+g(b)} & \frac{-g(b)}{f(a)+g(b)} \end{bmatrix} $$ Let the distribution of $U_i$ be $u_i$ , we have $$ u_1 = \begin{bmatrix}\frac{1}{2} & \frac{1}{2} \end{bmatrix} $$ $$ \implies u_i = u_1 P^{i-1} = \begin{bmatrix} \frac{1}{2}\frac{ 2f(a) - (f(a)-g(b) )( 1 -f(a) - g(b) )^{i-1} }{f(a) + g(b) } & \frac{1}{2}\frac{ 2g(b) + (f(a)-g(b))(1-f(a)-g(b))^{i-1} }{f(a)+g(b)} \end{bmatrix} $$ Let $U = \lim_{i\to\infty} U_i $ and the eventual daily profit $D = (a+b)U - b $ , so $$ ED = \lim_{i\to \infty} (a+b)EU_i - b = \lim_{i\to \infty} (a+b)\left( \frac{1}{2}\frac{ 2g(b) + (f(a)-g(b))(1-f(a)-g(b))^{i-1} }{f(a)+g(b)} \right) - b $$ $f(a) , g(b) \in (0,1] \implies | 1-f(a)-g(b) | < 1$ or $f(a)-g(b) = 0 $ so $$ = (a+b)\left( \frac{1}{2}\frac{ 2g(b) }{f(a)+g(b)} \right) - b $$ $$ = \frac{ ag(b) - bf(a) }{f(a)+g(b)} $$ $$ = \frac{ a\frac{1}{f(a)} - b\frac{1}{g(b)} }{\frac{1}{f(a)}+\frac{1}{g(b)}} $$ $$ = \frac{ aEX - bEY }{EX+EY} $$ with $X\sim Geo(f(a)) , Y \sim Geo(g(b))$ and there's no restriction on their dependency . You could also arrive here by solving for invariant distribution and applying theorem 1.10.2 here . How to explain this result ? e.g. Could it be explained by the 2 approaches I mentioned or does it suggest a third approach to the problem ?

A possible third approach : (thanks to user Jafego)

Instead of viewing $(U_{n})_{n\ge 0}$ as a "straight line" , warp it to form numerous cycles according to some rules (like a spring except size of each cycle is random) .

Each cycle has 2 components : A consecutive number of days $X\sim Geo(f(a)) $ where the promoter makes a profit $a$ thousand GBP per day . A consecutive number of days $Y\sim Geo(g(b))$ where the promoter losses $b$ thousand GBP per day . A cycle is of length $X + Y$ . So the "sample mean" of daily profit in a cycle is $ \frac{aX-bY}{X+Y}$ . I think this "sample mean" is also i.i.d for each cycle . However , it has variable sample size so I'm unable to proceed from here .

This's as close as I could get to explaining the result .

  • $\begingroup$ Writing an answer. It may take some time, because I tend to write long answers, but I thought I'd inform you in case you need to let me know anything more before I finish. Thanks. $\endgroup$ Commented Jul 20, 2022 at 5:28
  • $\begingroup$ @SarveshRavichandranIyer Thanks , I've tried to include everything I know in this post . Maybe another thing is I found that numerically $ E\left[\frac{.75X-bY}{X+Y}\right] = \frac{.75E[X]-bE[Y]}{E[X]+E[Y]} $ is unlikely true . $\endgroup$
    – C.C.
    Commented Jul 20, 2022 at 6:59

1 Answer 1

Setup(Start all over)

For starters, let me get the setup right. You have a Markov chain which is as follows : given some real numbers $a,b$, the Markov chain $U_i$ is on the state space $\{0,1\}$ , and has transition matrix equal to $$ P = \begin{pmatrix} 1-g(b) & g(b) \\ f(a) & 1-f(a) \end{pmatrix} $$ where the process being at $0$ at time $t$ is equivalent to the assertion that the singer did not perform on the $t$th day of the concert. Let $M_n$ be the "profit after $n$ days" defined by $$ M_n = (a+b)(U_0+\ldots+U_n) - nb $$ and we would like to study $M_n$.

Oh, and the singer is Miley Cyrus. And we are organizing the concert. Both of us. For the uninitiated, I will drop some references to some of her songs as I'm part of her free promotion as well. This answer is more about math and less about Miley, though.

For the sake of clarity , let's assume that we start looking at our profits from the first day Miley sings (is "on a roll?"), i.e. let $U_0 = 1$. If Miley is in a bad mood on the day we start looking at our profits, then $U_0=0$. Thankfully, in the limit the analysis is very similar, so it doesn't matter what Miley does on the "zeroth" day (Side Note : I'm starting the Markov Chain $U$ from time $0$ , so that $U_0$ is the beginning and not $U_1$. This is in accordance with Norris' "Markov Chains". Similarly, $M_0 = a$ as per the definition. The book is publicly available, see here. Of course, the change of time barely changes the analysis).

A summary of what's coming

We provide three different ways of looking at the result. Each has their positives and deficiencies, but each illustrates a principle that isn't seen in the other approaches.

  • The first uses convenient stopping times to show that the average profit , in the limit, can be interpreted as a ratio of sums of iid random variables. Therefore, we can use the strong law of large numbers alone to deduce what the average looks like (rather than the stronger Theorem $10.2$). It is a great technique for guessing what the limit can be.

  • The second uses Theorem $10.2$ in conjunction with the fact that the profit has a special structure, to deduce the limit rigorously, as well as provide intuition by borrowing the intuition of Theorem $10.2$.

  • The third approach uses the fact that invariant measures allow us to view the Markov chain and the associated profit as a sum of identically distributed random variables, which allows us to interpret the profit very comfortably.

Note : the short form "iid" refers to "independent and identically distributed" random variables.

Approach 1 : Where does the geometric random variable come from?

The geometric random variable arises from the "holding times" of the Markov chain at the states $0$ and $1$. These two combine to produce a sequence of "first return times" along which the profit functional behaves very regularly.

Note : To clarify (I don't think Norris uses geometric random variables with explicit mention, but I can match my definition with the OP's usage), the random variable $R \sim \mbox{Geo}(p)$ for $0<p\leq 1$ satisfies $\mathbb P(R = k) = (1-p)^k p$ for $k=1,2,3,\ldots$ (in particular, $R=0$ doesn't happen and the counting starts from $1$). We have $\mathbb E[R] = \frac{1}{p}$.

Intuitively, we will look at the "runs" of $0$s and $1$s in $U_i$ (or the "singing/not singing" streaks of Miley Cyrus), using appropriate stopping times. Recall that $U_0 = 1$ by choice.

Now consider the following random variables $X_i,Y_i,R_i$ for $i \geq 1$ and $T_j$ for $j \geq 0$. Define $T_0 = 0$. Now define inductively, for $i \geq 1$, $$ X_i = \min\{k > 0 : U_{k+ T_{i-1}} = 0, U_{k+T_{i-1}-1} = 1\}\\ Y_i = \{k >0 : U_{k+T_{i-1}+X_i} = 1, U_{k+T_{i-1}+X_i-1}= 0\} \\ R_i = X_i+Y_i , T_i = T_{i-1}+R_i $$

Providing intuitive explanations :

  • The Markov chain $U_i$ begins at $U_0 = 1$. $X_1$ is the first time it moves to $1$. This is basically the number of days that Miley sings for (her "first streak"), before she slides away for her first "hissy fit".

  • $Y_1$ is the number of days that Miley hissy fit lasts for, before she returns to the stage for her second streak.

  • Similarly, $X_i$ is the duration of Miley's $i$th singing streak and $Y_i$ is the duration of her $i$th hissy fit.

  • $R_i$ counts the number of days between consecutive returns of Miley to the stage from her hissy fits.

  • $T_i$ is the number of days from the start till the $i+1$th time she returns to the stage (i.e. the day after her $i$th hissy fit ends).

All this demands an example of Miley's schedule and how we calculate the above times (I'm going to delete a comment of mine where I was misleading. I tried hard to "#GetItRight" this time).

Let the sequence $U_0,U_1,U_2,\ldots$ look as follows :

$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline U_0 & U_1 &U_2 & U_3 & U_4 & U_5 & U_6 & U_7&U_8&U_9&U_{10} & U_{11} & U_{12} & U_{13} & U_{14} & U_{15} & U_{16} & U_{17} & U_{18} & U_{19} & U_{20} & \ldots \\ \hline 1&1&0&0&0&1&1&1&1&0&1&0&1&1&1&0&0&0&0&0&1&\ldots \\ \hline \end{array} $$

Then we have :

  • $X_1 = 2, Y_1 = 3, X_2 = 4, Y_2 = 1, X_3 = 1, Y_3 = 1, X_4 = 3, Y_4 = 5,\ldots$

  • $R_1 = 5, R_2 = 5, R_3 = 2, R_4 = 8,\ldots$

  • $T_0 = 0, T_1 = 5, T_2 = 10, T_3 = 12, T_{4} = 20,\ldots$

Now we begin our observations.

We note that $X_i$ and $Y_i$ are independent identically distributed random variables. Why?

That's because each $X_i$ is the time the Markov chain stays at a point before going to the other one, likewise $Y_i$. By time-homogeneity, the holding times don't change based on what time you reach a state. Now, imagine that leaving the point you're currently at is a "success" and that staying at the point you're currently at is a "failure". Then, the random variable $X_i$ is actually counting the time it takes to record the "success" of exiting $1$ on the $i$th occasion, likewise $Y_i$.

However, the "Strong Markov property"(because we're trying to restart at stopping times $T_i$ instead of fixed times, Theorem 1.4.2 here) applies) tells you that each attempt to leave is independent of the previous attempts. When one performs independent trials, the time it takes to record a success is a geometric random variable! (as we defined it)

In this case, the probability of exit from $0$ to $1$ (a success in that direction) is $g(b)$, while an exit from $1$ to $0$ happens with probability $f(a)$. Therefore, the distribution of $X_i$ is $\mbox{Geo}(f(a))$ and the distribution of $Y_i$ is $\mbox{Geo}(g(b))$.

Furthermore, because of the strong Markov property, $X_i$ and $Y_i$ are iid sequences of random variables. By the disjoint blocks theorem, $R_i = X_i+Y_i$ is also a sequence of iid random variables.

(Note: I have not rigorously shown that $X_i$ are geometric with the given distribution, but I leave this as an exercise using the Strong Markov property).

Finally, $T_i$ is a sum of iid random variables.

That's how geometric random variables enter the picture. How do they relate to the $M_i$, however?

Relating $M_i$ to the $X_i,Y_i,T_i$

The relation between the $M_i$ and the $X_i,Y_i$ is captured by fact that $M_i$ is an additive functional of $U_i$. Let's define what an additive functional is in general.

Let $V_i$ be any sequence of random variables taking values in a state space $S$. Then, another sequence of random variables $N_i$ is called an additive functional of $V_i$ if the following is true : there exists a function $W : S \to \mathbb R$ such that $$ N_k = \sum_{i=1}^k W(V_i) $$ for all $i$.

Let me put it this way : an additive functionals of $V_i$ that can be calculated purely by seeing how much time $V_i$ spent at each state, and not necessarily its entire trajectory till a certain time.

See, the trajectory contains a lot more information than just how much time was spent at each point : for example, it contains details of how the random variables $V_i$ transitioned between various states. However, $N_i$ can purely be made out by counting how many times $V_i$ was at some state, and then adding it all up with some weight function $W$ involved. You don't need to know the transitions or any other details to calculate $N_i$.

Now, the special thing about $M_i$ is that $$ M_n = \sum_{i=0}^n W(U_i) $$ where $W(0) = -b$ and $W(1) = a$. This is basically saying that you earn a profit of $a$ each time Miley Cyrus turns up, and incur a loss of $b$ each time she decides to act like a wrecking ball and not turn up. Thus, $M_i$ is an additive functional of $U_i$.

Now, because one doesn't care about the transitions, it is clear that $M_i$ depend only upon the various holding times at each point! That's the reason why we expect $M_i$ to depend only upon the $X_i$ and $Y_i$.

Indeed, we have the following result :

$M_{T_{i+1}} = M_{T_i} + aX_i - bY_i$ for all $i \geq 0$.

I leave you to see this result. Use the additivity, and the definitions of $X_i,Y_i$ to prove this result.

This shows that $M_{T_i}$ is a sum of iid random variables, because $P_i = aX_i - bY_i$ for $i \geq 1$ is a sequence of iid random variables.

This is the key intuition in understanding how $M_i$ interacts with the holding times. It's an additive functional, and in general you expect additive functionals to interact with processes in the same way. Something very similar happens in continuous time as well.

Getting the limit random variable

Now, we use some nice facts. Rather obviously , $T_i \geq i$ for all $i \geq 0$ so $T_i \to \infty$ as $i \to \infty$.

Now, look at the ratio $$ \frac{M_{T_i}}{T_i} = \frac{M_{T_i}}{i} \frac{i}{T_i} $$

Now, both $T_i$ and $M_{T_i}$ are the sums of independent, identically distributed random variables. Thus, by the strong law of large numbers, we have almost surely $$ \lim_{i \to \infty} \frac{M_{T_i}}{T_i} = \lim_{i \to \infty}\frac{M_{T_i}}{i} \lim_{i \to \infty} \frac{1}{\frac{T_i}{i}} = \frac{\mathbb E[aX_i - bY_i]}{E[R_i]} = \frac{aE[X] + bE[Y]}{E[X]+E[Y]} $$

where $X \sim X_1, Y \sim Y_1$ and $E[R_i] = E[X_i+Y_i]= E[X]+E[Y]$. This explains, very clearly, the origin of the ratio , from the strong law of large numbers. It is somewhat incomplete, however.

Why? That's because we have only shown that $\lim_{i \to \infty} \frac{M_{T_i}}{T_i}$ exists, not that $\lim_{i \to \infty} \frac{M_{i}}{i}$ exists, right? It is the latter we desire.

Approach 2 : On why $\lim_{i \to \infty} \frac{M_i}{i}$ exists

To understand this, we go back to the theory of additive functions.

Recall what additive functions are : they depend not upon the trajectory of the process, but about how much time it spends at each point.

Here's the intuition : if we know the average amount of time a process spends at each state, then we obviously know the average amount of any additive functional in the limit, simply because that is the only information we need to determine an additive function!

Now, because Markov chains have a limit theorem for the amount of time spent at a state, we would expect the same to be true of the average profit.

What is that limit theorem? That limit theorem is Theorem $10.2$ cited by the author. The proof of Theorem $10.2$ can be adapted for additive functions in the following manner.

Let $V_i$ be a process on a countable (can take as finite if you need) state space $S$ such that for every $s \in S$, $\lim_{i \to \infty} \frac{\#\{k \leq i : V_k = s\}}{i}$ exists and is independent of the starting distribution $V_0$. Then, for every additive functional $M_i$ of $V_i$ with associated weight function $W$ such that $\sum_{s \in S} |W(s)| < \infty$ (integrability condition), we have $$ \lim_{i \to \infty} \frac{M_i}{i} = \sum_{s \in S} \left[W(s) \lim_{i \to \infty} \frac{\#\{k \leq i : V_k = s\}}{i} \right] $$

Now, using this result in conjunction with Theorem $10.2$ tells us instantly that $\lim_{i \to \infty} \frac{M_i}{i} = \frac{aE[X] - bE[Y]}{E[X]+E[Y]}$.

However, how is this result proved? It's proved by observing that because $M_i$ is additive, $$ M_n = \sum_{s \in S} W(s) \#\{k \leq n : V_k = s\} $$

Now, divide by $n$ like so $$ \frac{M_n}{n} = \sum_{s \in S} W(s) \frac{\#\{k \leq n : V_k = s\}}{n} $$ Observe that $$ \sum_{s \in S} \left|W(s) \frac{\#\{k \leq n : V_k = s\}}{n}\right| \leq \sum_{s \in S} |W(s)| < \infty $$ so by the usual sum-limit interchange theorem, $$ \lim_{n \to \infty} \frac{M_n}{n} = \lim_{n \to \infty} \sum_{s \in S} W(s) \frac{\#\{k \leq n : V_k = s\}}{n} \\ = \sum_{s \in S} W(s) \lim_{n \to \infty} \frac{\#\{k \leq n : V_k = s\}}{n} $$

as desired.

Note that everything done in this section is not restricted to Markov chains! Indeed, even for other kinds of processes, one can consider objects like occupation measures and additive functionals, and similar results can be obtained.

However, this clearly explains, once again, the origin of the fraction.

We must finally come "Full Circle" and look how how invariant measures interact with additive functionals to get a third way of attacking this problem.

Approach $3$ : Invariant measures and additive functionals

What a invariant measure does to a Markov chain is quite brilliant, and the most beautiful part of this exposition. Miley should look to make a song on invariant measures sometime.

I think of stationary measures in our context like this :

Can we reimagine our process in such a way that it appears, despite our flowers and profits and losses, that Miley's decisions are identically distributed across different days?

That is, can we reformat our entire model so that Miley Cyrus' intentions to sing on a certain day look just like an identically distributed sequence of Bernoulli$(p)$ random variables, for some parameter $p$?

What a stationary measure does is exactly that. It actually makes Miley's decisions appear independent of our efforts (sending here flowers and forgiveness and love). As a result, we can use the theory of identically distributed random variables to predict Miley's behavior!

Here's how it works rigorously : we find the stationary distribution by solving the equation $$ \begin{pmatrix} x_0 & x_1\end{pmatrix} = \begin{pmatrix}x_0 & x_1\end{pmatrix} \begin{pmatrix} 1-g(b) & g(b) \\ f(a) & 1-f(a) \end{pmatrix} $$

along with $x_0+x_1 = 1$. Solving this yields $$ x_0 = \frac{g(b)}{g(b)+f(a)} , x_1 = \frac{f(a)}{f(a)+g(b)} $$ which is the desired invariant distribution. The point of a stationary distribution is the following fact which follows by definition of a time-homogenous Markov chain :

If $V_i$ is a Markov chain on $S$ (finite state space) with invariant distribution $\eta$, then assuming that $\mathbb P(V_0= s) = \eta(s)$, the collection $\{V_i : i \geq 0\}$ are identically distributed random variables, all distributed according to $\eta$.

Now, what happens when you have an invariant measure? The intuition is the following : because of identical distribution of the $V_i$ as $\eta$, for any $s\in S$ and $n \in \mathbb N$, we have $$ \frac{\mathbb E[\#\{k \leq n : V_k = s\}]}{n} = \sum_{i=1}^n \frac{\mathbb E[1_{V_k = s}]}{n} = \frac{n \times \mathbb P(V_0 = s)}{n} = \eta(s) $$

and therefore, because it's just a constant sequence, $$ \lim_{n \to \infty}\frac{\mathbb E[\#\{k \leq n : V_k = s\}]}{n} = \eta(s) $$

So, through the looking glass that is the invariant measure, we manage to obtain the quantity $V_i$. However, the same logic can be repeated with an additive functional! As a result, we have the following theorem :

Let $V_i$ be a Markov chain on finite state space $S$ with unique invariant measure $\eta$, and let $N_i$ be an additive functional of $V_i$ with weight function $W$, which satisfies $\sum_{s \in S} |W(s)| <\infty$. Suppose that $V_0 \sim \eta$. Then, we have almost surely $$ \lim_{i \to \infty} \frac{N_i}{i} = \sum_{s \in S} W(s) \eta(s) $$

The proof is very identical to what we did in the previous section. Use the fact that $V_i$ are identically distributed if $V_0 \sim \eta$.

Using the same logic with $U_i$ and $M_i$ here, $$ \lim_{i \to \infty} \frac{M_i}{i} = a\frac{g(b)}{f(a)+g(b)} - b\frac{f(a)}{f(a)+g(b)} = \frac{ag(b) - bf(a)}{f(a)+g(b)} $$ Note that this doesn't explain two things :

  • Where the geometric random variables come from.

  • What happens if $V_0$ isn't distributed like $\eta$?

The first is answered by the other approaches, so don't hold me prisoner for not showing how it comes up here!

For the other question (you can skip the explanation if it's complicated, I'm not going to make it too "clear" because it is a borderline concern for this problem), the uniqueness of the left eigenvector implies that for any $v$ which is not a scalar multiple of the left eigenvector $\pi$, the quantity $v-k\pi$ , for some scalar $k$, lies in a subspace orthogonal to the subspace generated by $\pi$. Hence, $(v-\pi)P^n \leq \lambda^n \|v-\pi\|$ where $\lambda$ is the smallest eigenvalue not equal to $1$, and this goes to $0$ as $n \to \infty$, so that $vP^n - \pi P^n \to 0$. However, $\pi P^n = \pi$, completing the proof.

Therefore, the hypothesis that $V_0 \sim \eta$ is actually unnecessary for technical reasons. Only the existence and uniqueness of $\eta$ is necessary.


We saw the following (and organized Miley's concert, hence multi-tasked) :

  • How we can interpret the profit process as an additive functional of the Markov chain.

  • How additive functions are related to holding times.

  • How the structure of additive functionals, independence of holding times and the strong law of large numbers can be used to prove limit existence along a random subsequence.

  • How the holding times can be used with existing holding limit theorems like Theorem $10.2$ to provide limit theorems for additive functionals in general.

  • How the notion of an invariant measure can instantly provide a holding limit theorem , and therefore provide a limit theorem for additive functionals.

  • We found some good songs for Miley(?).

A brief note on optimization (and TWO Miley Cyruses?)

For optimization, recall that $\lim_{i \to \infty} \frac{M_i}{i} = ax_0+bx_1$ from the invariant measure result, and $x_0+x_1 = 1$. So we need to maximize $ax_0 + b(1-x_0)$ over $0 \leq x_0 \leq 1$. However, this function equals $(a-b)x_0+b$.

Since $a>b$ (otherwise we're loss making all the time, and we need to find someone cheaper than Miley Cyrus. How about Ariana Grande? Shakira? I know I'm not very good at this), the maximum is attained when $x_0$ is as close to $1$ as possible (note : if $x_0$ ever attains a value of $1$ then Miley Cyrus never throws a hissy fit. Can't be true, eh?).

So find $\frac{g(b)}{f(a)+g(b)}$ to be as large as possible, and you've maximized the result. Now, because of the monotonicity of the reward system in $x_0$, it is possible to provide, using stochastic coupling and domination methods, a proof of the fact that increasing $\frac{g(b)}{f(a)+g(b)}$ increases the average profit. However, this will take us into stochastic coupling, where we have TWO (yes, TWO) Miley Cyruses that we treat differently, and we show that one will always give us more profit than the other. Then, we introduce more and more profit methods until Miley is singing "the most" she can.

The definition of stochastic dominance and an elementary usage of it can be found here. Note that our use will be more difficult, but we can still get it to work step-by-step. Such a method will not require us to even calculate the average earnings or use Markov chain theorems. That's why it will be more powerful.

All that, however, "someday" else.

  • $\begingroup$ Thanks for answering . But I'm not convinced that "$T_n$ are the number of days between the $n$th and the $n+1$th time that ..." . To me , $T_n$ is the $n$th passage time to state $1$ , also $U_i = 1$ only if $i \in \{T_0,T_1,...\}$ . Do you see the issue/misunderstanding ? Should I elaborate more ? $\endgroup$
    – C.C.
    Commented Jul 21, 2022 at 9:30
  • 1
    $\begingroup$ @C.C Yes, I have access to Norris' book. I'll keep this answer up because the latter parts of the answer don't use the notation $T_i$, but I'll make sure to correct the $T_i$ using Norris' notation and words. Thanks for letting me know that you use Norris, because I can then adjust this answer. However, I'm at work so I'll correct this once I return. Thanks (If you need to , kindly leave a downvote so that others can know there is some problem with the answer). $\endgroup$ Commented Jul 21, 2022 at 10:31
  • 1
    $\begingroup$ @C.C Thank you for the reference to Norris. I have used my notation, but I used his theorems for reference. I couldn't edit my answer yesterday, but my first priority was to make sure that it gets done today, and I've just done it. I tried to be as comprehensive and correct as possible this time, and I hope that there are no errors. $\endgroup$ Commented Jul 22, 2022 at 6:50
  • 1
    $\begingroup$ @C.C Sure. As $T_i \to \infty$, we know that $M_{T_i} - M_{T_0} = \sum_{k=0}^{i} M_{T_{k+1}} - M_{T_k}$, where $M_{T_{k+1}} - M_{T_k}$ is a sequence of iid random variables because of the result just at the end of the first section. Now, the SLLN tells you that if $Z_1,Z_2,\ldots$ are iid random variables with finite expectation then $\frac{Z_i}{i} \to E[Z_1]$ almost surely. You apply this to $\frac{M_{T_i}}{i}$ carefully (the $M_0/i$ will go to zero). $\endgroup$ Commented Jul 23, 2022 at 12:32
  • 1
    $\begingroup$ @C.C Yes, this is equivalent. You need to prove that $T_i < \infty$ for this, which can be done by induction. $T_0$ is finite, and $T_1 = R_1$ so you show that $R_1$ is finite (which it is because it's the sum of two geometric random variables with positive success probability), and so on. $\endgroup$ Commented Jul 24, 2022 at 5:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .