Proof. The first equivalence follows directly from (2.2) to (2.8). Now we prove the second equivalence.

Assume that $V(s;\;m)\gt m$ holds a.s. for $s=t,\dots,\theta$ , and suppose, for some s, that $M(s)=m$ holds on a set $A\subset\mathcal F$ of positive measure. Recall from (2.1) that the map $V(s;\cdot\!)$ is continuous; hence the set $\{\tilde m\ge0\colon V(s;\;\tilde m)(\omega)\gt\tilde m\}$ is open, and thus does not contain its supremum, for almost every $\omega\in\Omega$ . It follows from (3.1) that, for almost every $\omega\in A$ , we have

\begin{align*}M(s)(\omega) = m = \sup\{\tilde m\ge0\colon V(s;\;\tilde m)(\omega)\gt\tilde m\} \in \{\tilde m\ge0\colon V(s;\;\tilde m)(\omega)\le\tilde m\}.\end{align*}

Thus $V(s;\;m)(\omega)\le m$ holds on a set of positive measure, contradicting our initial assumption, and so $M(s)\gt m$ holds a.s., for every $s=t,\dots,\theta$ . We now obtain $\underline M(t,\theta)\gt m$ , as desired, from (3.2).

Conversely, $\underline M(t,\theta) \gt m$ gives $M(s)\gt m$ for every $s=t,\dots,\theta$ . We know from (2.2) that $V(s;\;M(s))\ge M(s)$ holds a.s. Now recall from (A.1) that the map $\tilde m\mapsto V(s;\;\tilde m)-\tilde m$ , is strictly decreasing; hence

\begin{align*}V(s;\;m)-m\gt V(s;\;M(s))-M(s)\ge0, \quad \text{a.s.}\end{align*}

holds for each $s=t,\dots,\theta$ .

Proof. The inequalities that follow hold a.s. By (3.6), there exists a sequence $m_n\downarrow\underline M(t,\theta)$ such that $\sigma(t;\;m_n)\le\theta$ holds for each $n\in\mathbb N$ , so the right-continuity of $m\mapsto\sigma(t;\;m)$ yields $\sigma(t;\;\underline M(t,\theta))\le\theta$ .

Conversely, there exists a sequence $m'_n\uparrow\underline M(t,\theta)$ , also by (3.6), such that $\sigma(t;\;m'_n)\gt\theta$ holds for each $n\in\mathbb N$ . Since $\sigma(t,\!\cdot)$ takes integer values, we obtain $\sigma(t;\;m'_n)\ge\theta+1$ , which implies $\sigma(t;\;\underline M(t,\theta)-\!)\ge\theta+1\gt\theta$ .

Proof. Fix an integer $\sigma(m)\le\theta \lt \sigma(m-\!)$ . By (3.4), $\sigma(t,m)\le\theta$ implies that $m\ge\underline M(t,\theta)$ holds a.s. Conversely, the decrease of $\sigma(t;\cdot\!)$ implies that $\sigma(t;\;m-\delta)\ge\sigma(t;\;m-\!)\gt\theta$ holds a.s. for every $0\lt\delta\le m$ . Thus, $m-\delta\lt\underline M(t,\theta)$ holds a.s., again by (3.4), and taking $\delta\downarrow0$ yields $m\le\underline M(t,\theta)$ , a.s.

Proof. Right-continuity and increase follow immediately from Lemma 1 and (2.10). By (3.1) and (3.4), we have $M(\theta)\gt0$ ; thus $\sigma(t;\;0)\gt\theta$ for all $\theta\ge t$ . Therefore,

(3.9) \begin{align}\sigma(t;\;0)=+\infty, \quad\text{a.s.},\end{align}

which in conjunction with (2.10) implies ${\partial^+}V(t;\;0)/{\partial m}=0$ . Conversely, if $M(t)\le m$ then (3.5) yields $\sigma(t;\;m)=t$ , and so ${\partial^+}V(t;\;m)/{\partial m}=1$ .

Proof. First notice that (2.7) and (3.9) yield

(3.11) \begin{align}V(t;\;m) - V(t;\;0) = \mathbb E\Bigg[m\beta^{\sigma(t;\;m)-t} - \sum_{\theta=\sigma(t;\;m)}^\infty\beta^{\theta-t}h(\theta+1) \,\Bigg\vert\, \mathcal F(t)\Bigg].\end{align}

Now, for every $\tilde m\le m$ , observe that $\sigma(t;\;\tilde m)\ge\sigma(t;\;m)$ a.s., by Lemma 1. Thus, by applying the equivalence (3.4), we may write $\beta^{\sigma(t;\;\tilde m)-t}$ as

\[\beta^{\sigma(t;\;\tilde m)-t}= (1-\beta)\sum_{\theta=\sigma(t;\;\tilde m)}^\infty \beta^{\theta-t} = (1-\beta)\sum_{\theta=\sigma(t;\;m)}^\infty\beta^{\theta-t} \mathbf{1}\{\underline M(t,\theta)\le \tilde m\}.\]

Substituting this value into (2.10) and integrating yields

\begin{align*}V(t;\;m) - V(t;\;0)&= \int_0^m\frac{\partial^+}{\partial\tilde m}V(t;\;\tilde m)\,\mathrm{d}\tilde m \\&= (1-\beta)\int_0^m \mathbb E\Bigg[\sum_{\theta=\sigma(t;\;m)}^\infty\beta^{\theta-t} \mathbf{1}\{\underline M(t,\theta)\le \tilde m\} \,\Bigg\vert\, \mathcal F(t)\Bigg] \mathrm{d}\tilde m, \quad\text{a.s.}\end{align*}

Note that the fundamental theorem of calculus can be used to establish the first of these equalities, despite the fact that the right-derivative of $V(t;\cdot\!)$ is used; this is due to convexity, established in Lemma 2 (e.g. [Reference Karatzas and Shreve17, Problem 3.6.21]). Since the integrand on the right-hand side is non-negative, Tonelli’s theorem implies

(3.12) \begin{align}V(t;\;m)-V(t;\;0) = (1-\beta)\,\mathbb E\Bigg[\sum_{\theta=\sigma(t;\;m)}^\infty \beta^{\theta-t} (m-\underline M(t,\theta) ) \,\Bigg\vert\, \mathcal F(t)\Bigg], \quad \text{a.s.},\end{align}

where we use the fact that $m-\underline M(t,\theta)\ge0$ when $\theta\ge\sigma(t;\;m)$ , from (3.4).

Finally, we note

(3.13) \begin{align}& (1-\beta) \,\mathbb E\Bigg[\sum_{\theta=\sigma(t;\;m)}^\infty \beta^{\theta-t} (m-\underline M(t,\theta) ) \,\Bigg\vert\, \mathcal F(t)\Bigg] \nonumber \\&\quad = m\,\mathbb E[\beta^{\sigma(t;\;m)-t} \mid \mathcal F(t)] - (1-\beta)\,\mathbb E\Bigg[\sum_{\theta=\sigma(t;\;m)}^\infty \beta^{\theta-t}\underline M(t,\theta) \,\Bigg\vert\, \mathcal F(t)\Bigg].\end{align}

Recalling (3.12), we deduce that the right-hand sides of (3.11) and (3.13) are a.s. equal; hence

(3.14) \begin{align}\begin{split}\mathbb E\Bigg[\sum_{\theta=\sigma(t;\;m)}^\infty\beta^{\theta-t}h(\theta+1) \,\Bigg\vert\, \mathcal F(t)\Bigg] = (1-\beta)\, \mathbb E\Bigg[\sum_{\theta=\sigma(t;\;m)}^\infty \beta^{\theta-t}\underline M(t,\theta) \,\Bigg\vert\, \mathcal F(t)\Bigg],\quad\text{a.s.}\end{split}\end{align}

Once more, (3.4) implies that $\sigma(t;\;m)\to t$ as $m\to\infty$ , so it follows from (2.7) and (3.9) to (3.14) that

(3.15) \begin{align}V(t;\;0) = \mathbb E\left[\sum_{\theta=t}^\infty\beta^{\theta-t}h(\theta+1) \,\middle\vert\, \mathcal F(t)\right] = (1-\beta)\, \mathbb E\left[\sum_{\theta=t}^\infty \beta^{\theta-t}\underline M(t,\theta) \,\middle\vert\, \mathcal F(t)\right]\!,\quad \text{a.s.}\end{align}

By substituting the expression on the right-hand side into (3.12), we obtain the desired representation of $V(t;\;m)$ .

The second equality follows from (3.4), namely

\begin{align*}&(1-\beta)\mathbb E \Bigg[\sum_{\theta=t}^\infty \beta^{\theta-t}(m\vee\underline M(t,\theta))\,\Bigg\vert\,\mathcal F(t)\Bigg] \\&\quad= (1-\beta)\mathbb E\left[\sum_{\theta=t}^\infty \beta^{\theta-t}\left(m + \int_m^\infty\mathbf{1}\{\sigma(t;\;\lambda)\gt\theta\}\,\mathrm{d}\lambda\right)\,\middle\vert\,\mathcal F(t)\right] \\&\quad= m + \mathbb E\left[\int_m^\infty\big(1-\beta^{\sigma(t;\;\lambda)-t}\big)\,\mathrm{d}\lambda\,\middle\vert\,\mathcal F(t)\right]\end{align*}

as desired.

Proof. The following equalities hold a.s.

Fix $\theta\ge t$ . We recall that $(1-\beta)^{-1}=\sum_{u=0}^\infty\beta^u$ ; hence (3.10) implies

(3.16) \begin{align}\beta^\theta [V(\theta;\;m)-m ] = (1-\beta)\,\mathbb E\left[\sum_{u=\theta}^\infty \beta^u (\underline M(\theta,u)-m )^+\,\middle\vert\,\mathcal F(\theta)\right]\!.\end{align}

This holds for every $m\ge0$ , so replacing m with $\underline M(t,\theta)$ , an $\mathcal F(\theta)$ -measurable random variable, yields

(3.17) \begin{align}\beta^\theta [V(\theta;\;\underline M(t,\theta))-\underline M(t,\theta) ] = (1-\beta)\,\mathbb E\left[\sum_{u=\theta}^\infty \beta^u (\underline M(\theta,u)-\underline M(t,\theta) )^+\,\middle\vert\,\mathcal F(\theta)\right]\!. \end{align}

Now fix $m\ge0$ . In the event $\{\theta\lt\sigma(t;\;m)\}=\{m\lt\underline M(t,\theta)\}$ , we easily check that

\begin{align*}(\underline M(\theta,u)-m )^+ - (\underline M(\theta,u)-\underline M(t,\theta) )^+&= (\underline M(t,u)-m )^+\end{align*}

for every $u\ge\theta$ . Thus, by subtracting (3.17) from (3.16), we obtain

(3.18) \begin{align}\beta^\theta D(\theta) = (1-\beta)\,\mathbb E\left[\sum_{u=\theta}^\infty \beta^u (\underline M(t,u)-m )^+\,\middle\vert\,\mathcal F(\theta)\right]\end{align}

on $\{\theta\lt\sigma(t;\;m)\}$ , where

(3.19) \begin{align}D(\theta) \;:\!=\; (V(\theta;\;m)-m ) - (V(\theta;\;\underline M(t,\theta)) - \underline M(t,\theta) ),\quad\theta\ge t.\end{align}

For ease of notation, let $\theta_\sigma(m) \;:\!=\; \theta\wedge\sigma(t;\;m)$ . We claim that the sequence

(3.20) \begin{align}\Bigg\{\beta^{\theta_\sigma(m)} D(\theta_\sigma(m)) + (1-\beta)\sum_{u=t}^{\theta_\sigma(m)-1}\beta^u(\underline M(t,u)-m), \Bigg\}_{\theta=t}^\infty\end{align}

is an $\{\mathcal F(\theta)\}_{\theta=t}^\infty$ -martingale. Indeed, fix $\theta,\theta'\in\mathbb N_0$ such that $t\le\theta\le\theta'$ . Then

\begin{align*}&\mathbb E\Bigg[ \vphantom{\sum_{u=t}^{\theta'_\sigma(m)-1}} \beta^{\theta'_\sigma(m)} D(\theta'_\sigma(m)) + (1-\beta)\sum_{u=t}^{\theta'_\sigma(m)-1} \beta^u (\underline M(t,u)-m )\,\Bigg\vert\, \mathcal F(\theta)\Bigg] \\[3pt]&\quad = (1-\beta)\, \mathbb E\Bigg[\mathbb E\Bigg[\sum_{u=t}^\infty\beta^u (\underline M(t,u)-m )^+ \,\Bigg\vert\,\mathcal F(\theta'_\sigma(m))\Bigg]\,\Bigg\vert\,\mathcal F(\theta)\Bigg] \\[3pt]&\quad = (1-\beta)\, \mathbb E\Bigg[\sum_{u=\theta_\sigma(m)}^\infty \beta^u (\underline M(t,u)-m )^+ + \sum_{u=t}^{\theta_\sigma(m)-1}\beta^u (\underline M(t,u)-m )\,\Bigg\vert\,\mathcal F(\theta_\sigma(m))\Bigg] \\[3pt]&\quad = \beta^{\theta_\sigma(m)}D(\theta_\sigma(m)) + (1-\beta)\sum_{u=t}^{\theta_\sigma(m)-1}\beta^u (\underline M(t,u)-m ),\end{align*}

making use of (3.18), the $\mathcal F(u)$ -measurability of $\underline M(t,u)$ , and the fact that $\underline M(t,u)\gt m$ for every $u\lt\sigma(t;\;m)$ .

Conversely, observe that the left-hand side of the identity

\begin{align*}m\beta^t = m\beta^{\theta_\sigma(m)}+\sum_{u=t}^{\theta_\sigma(m)-1}\beta^u(1-\beta)m\end{align*}

does not depend on $\theta$ , so the sequence

(3.21) \begin{align}\Bigg\{\beta^{\theta_\sigma(m)} [V(\theta_\sigma(m);\;m)-m ] + \sum_{u=t}^{\theta_\sigma(m)-1} \beta^u (h(u+1) - (1-\beta)m )\Bigg\}_{\theta=t}^\infty\end{align}

is an $\{\mathcal F(\theta)\}_{\theta=t}^\infty$ -martingale, by (2.5) and Proposition 1. It follows that the difference between (3.20) and (3.21), namely,

(3.22) \begin{align}\Bigg\{\beta^{\theta_\sigma(m)} [V(\theta_\sigma(m);\; \vphantom{\sum_{u=t}^{\theta_\sigma(m)-1}} \underline M(t;\;\theta_\sigma(m))) - \underline M(t;\;\theta_\sigma(m)) ] + \sum_{u=t}^{\theta_\sigma(m)-1} \beta^u (h(u+1)-(1-\beta)\underline M(t,u) )\Bigg\}_{\theta=t}^\infty,\nonumber \\&\end{align}

is an $\{\mathcal F(\theta)\}_{\theta=t}^\infty$ -martingale, for every $m\ge0$ . By (3.9), $\theta_\sigma(m)\equiv\theta$ when $m=0$ ; taking $m=0$ in (3.22) completes the proof.

Proof. By conditions (ii) and (iii) in Definition 3, we obtain

(4.4) \begin{align} \{\tilde T(t)=\tilde r\} = \bigcup_{j=1}^d\{\tilde T(t+1)=\tilde T(t)+\tilde e_j,\ \tilde T(t)=\tilde r\} \in \mathcal F(\tilde r) \end{align}

for every $t\in\mathbb N_0$ and $\tilde r\in\mathbb N_0^d$ such that $\tilde r\ge\tilde s$ . If $\tilde r\not \ge\tilde s$ then it follows from condition (ii) of Definition 3 that $\{\tilde T(t)=\tilde r\}=\varnothing\in\mathcal F(\tilde r)$ . Thus $\tilde T(t)$ is a stopping point. Next, fix $r\in\mathbb N_0$ . For every $\tilde r\in\mathbb N_0^d$ such that $r_i=r$ , we have $\mathcal F(\tilde r)\subseteq\mathcal F^i(r)$ ; hence

\begin{align*}\{T_i(t)=r\} = \bigcup_{\substack{\tilde r\in\mathbb N_0^d\\r_i=r}}\{\tilde T(t)=\tilde r\} \in \mathcal F^i(r).\end{align*}

Thus $T_i(t)$ is an $\mathbf F^i$ -stopping time.

Condition (ii) also implies that $\tilde T(t+1)\ge\tilde T(t)$ in the partial ordering of $\mathbb N_0^d$ for every $t\in\mathbb N_0$ . Then $\mathcal F(\tilde T(t))\subset\mathcal F(\tilde T(t+1))$ ; thus $\{\mathcal F(\tilde T(t))\}_{t\in\mathbb N_0}$ is a one-parameter filtration.

Finally, let $\nu$ be an $\mathbf F(\tilde T)$ -stopping time. For every $\tilde r\in\mathbb N_0^d$ , we have

\begin{align*}\{\tilde T(\nu)=\tilde r\} = \bigcup_{t=0}^\infty\{\nu=t\}\cap\{\tilde T(t)=\tilde r\}.\end{align*}

Since $\{\nu=t\}\in\mathcal F(\tilde T(t))$ then (4.3) implies $\{\nu=t\}\cap\{\tilde T(t)=\tilde r\}\in\mathcal F(\tilde r)$ . We conclude that $\{\tilde T(\nu)=\tilde r\}\in\mathcal F(\tilde r)$ , which proves that $\tilde T(\nu)$ is an $\mathbf F$ -stopping point.

Proof of Theorem 3. We will proceed by proving (a) $\implies$ (b) $\implies$ (c) $\implies$ (a), then show (a) $\implies$ (d) $\implies$ (b), and finally (a) $\iff$ (e). Throughout the proof, we assume for ease of notation that $\tilde s=\tilde 0$ , as the general case follows by translation.

1. (a) $\implies$ (b). Taking $t=\tau(m)$ in (4.19) yields $\sum_{i=1}^d(T_i(\tau(m)) \wedge\sigma_i(m))=\tau(m)$ ; hence $T_i(\tau(m))=\sigma_i(m)$ for each $i=1,\dots,d$ and every $m\ge0$ , by condition (ii) of Definition 3.

2. (b) $\implies$ (c). It follows from (4.12), (5.3), and the increase of $T_i(\!\cdot\!)$ that, for each $i=1,\dots,d$ ,

   \begin{align*}\sigma_i(N(t))=(T_i\circ\tau)(N(t))\le T_i(t)\le(T_i\circ\tau)(N(t)-\!)=\sigma_i(N(t)-\!).\end{align*}

3. (c) $\implies$ (a). Fix $t\in\mathbb N_0$ and $m\ge0$ . If $m\gt N(t)$ then (5.4) and the decrease of $\sigma_i(\!\cdot\!)$ yield

   \begin{align*}T_i(t)\ge\sigma_i(N(t))\ge\sigma_i(m)\end{align*}

Now (4.12) and the decrease of $\tau(\!\cdot\!)$ imply

(5.7^′) \begin{align} t\ge\tau(N(t))\ge\tau(m), \end{align}

yielding (4.19).

Conversely, if $m\le N(t)$ , we have analogously that

(5.7^′′) \begin{align} T_i(t)\le\sigma(N(t)-\!)\le\sigma_i(m-\!)\quad\text{and}\quad t\lt\tau(N(t)-\!)\le\tau(m-\!), \end{align}

yielding (5.7). But (5.7) is equivalent to (4.19).

(a) $\implies$ (d). Let $\tilde T$ be an arbitrary allocation strategy and let $t\in\mathbb N_0$ and $m\ge0$ be given. It holds that $\underline{\mathcal M}(\tilde T(t))\le m$ if and only if $\underline M_i(T_i(t))\le m$ for each $i=1,\dots,d$ , which in turn holds if and only if $\sigma_i(m)\le T_i(t)$ for each $i=1,\dots,d$ , by (3.4). Summing over each i yields $\tau(m)\le t$ , which is equivalent to the inequality $N(t)\le m$ by (4.10). Thus

(5.8) \begin{align} \underline{\mathcal M}(\tilde T(t))\le m\ \implies\ N(t)\le m,\quad \text{for all}\ t\in\mathbb N_0,\,m\ge0, \end{align}

from which (5.5ʹ) follows. Now the reverse inequality holds if and only if the converse of (5.8) also holds, which requires the implication

(5.9) \begin{align} \tau(m)\le t\ \implies\ \sigma_i(m)\le T_i(t),\quad \text{for all}\ i=1,\dots,d,\, t\in\mathbb N_0,\,m\ge0. \end{align}

But this holds immediately for every $\tilde T$ that satisfies (4.19).

(d) $\implies$ (b). If (5.5) holds then (5.9) must also hold. By taking $t=\tau(m)$ , we obtain $\sigma_i(m)\le T_i(\tau(m))$ for each $i=1,\dots,d$ and every $m\ge0$ . But summing over i yields

\begin{align*} \tau(m)=\sum_{i=1}^d\sigma_i(m)\le\sum_{i=1}^dT_i(\tau(m))=\tau(m); \end{align*}

hence $\sigma_i(m)=T_i(\tau(m))$ for each $i=1,\dots,d$ .

(a) $\implies$ (e). It suffices to show that, for each $i=1,\dots,d$ and $t\in\mathbb N_0$ , we have

\begin{align*}\underline M_i(T_i(t)) \lt \underline{\mathcal M}(\tilde T(t))\ \implies\ T_i(t) = T_i(t+1).\end{align*}

We have by property (d) that $\underline{\mathcal M}(\tilde T(t))=N(t)$ , so we assume $\underline M_i(T_i(t)) \lt N(t)$ for given $i=1,\dots,d$ and $t\in\mathbb N_0$ .

Suppose $\sigma_i(\!\cdot\!)$ has a jump at N(t). Then $T_i(t)\in\{\sigma_i(N(t)),\dots, \sigma_i(N(t)-\!)\}$ , by (5.4). If $T_i(t)\neq\sigma_i(N(t)-\!)$ then (3.8) implies that $\underline M_i(T_i(t)) = N(t)$ , contradicting our initial assumption. Thus, $T_i(t)=\sigma_i(N(t)-\!)$ holds. In particular, we have by (5.3) that $T_i(t) = T_i(\tau(N(t)-\!))$ , where $t\lt\tau(N(t)-\!)$ by (4.12). The increase of $T_i(\!\cdot\!)$ thus implies that $T_i(t)=T_i(t+1)$ , as desired.

Conversely, suppose $\sigma_i(\!\cdot\!)$ is continuous at N(t). Then (5.4) implies that $T_i(t)=\sigma_i(N(t))=\sigma_i(N(t)-\!)$ . Notice that, by (5.3), we have

\begin{align*} T_i(\tau(N(t)-\!)) = \sigma_i(N(t)-\!) = T_i(t), \end{align*}

whereas $\tau(N(t)-\!)\gt t$ by (4.12). The increase of $T_i(\!\cdot\!)$ again implies that $T_i(t)=T_i(t+1)$ .

(e) $\implies$ (a). Fix $m\gt0$ and proceed by induction on $t\in\mathbb N_0$ . For $t=0$ , we have $T_i(0)=0$ for each $i=1,\dots,d$ , and synchronization is trivially satisfied. Now suppose synchronization is satisfied for some $t\in\mathbb N_0$ . We consider two cases.

Case 1. $\sum_{i=1}^d(T_i(t)\wedge\sigma_i(m))=\tau(m)\le t$ . This holds if and only if $\sigma_i(m)\le T_i(t)$ holds for each $i=1,\dots,d$ . The increase of $T_i(\!\cdot\!)$ then implies $\sum_{i=1}^d(T_i(t+1)\wedge\sigma_i(m))=\tau(m)\le t+1$ , as desired.

Case 2. $\sum_{i=1}^d(T_i(t)\wedge\sigma_i(m))=t\le\tau(m)$ . This holds if and only if $\sigma_i(m)\ge T_i(t)$ holds for each $i=1,\dots,d$ . If equality holds for each i then we fall into Case 1. Therefore, suppose there exists a non-empty set $J\subseteq\{1,\dots,d\}$ such that $\sigma_j(m)\gt T_j(t)$ holds if $j\in J$ and $\sigma_j(m)=T_j(t)$ holds if $j\notin J$ . By (3.4), $\underline M_j(T_j(t))\gt m$ holds if $j\in J$ , whereas $\underline M_j(T_j(t))\le m$ holds if $j\notin J$ . It follows from the lower envelope index-type property (5.6) that $\tilde T(t+1) = \tilde T(t)+e_{j^*}$ for some $j^*\in J$ . Then $\sigma_i(m)\ge T_i(t)=T_i(t+1)$ for each $i\neq j^*$ while $\sigma_{j^*}(m)\gt T_{j^*}(t)$ implies $\sigma_{j^*}(m)\ge T_{j^*}(t)+1=T_{j^*}(t+1)$ . As a result, $\sigma_i(m)\ge T_i(t+1)$ holds for each $i=1,\dots,d$ , and synchronization is satisfied for $t+1$ .

Proof. It suffices to show, for every $s,t\in\mathbb N_0$ , $s\le t$ , and every bounded $\mathcal F_i(t)$ -measurable random variable $\xi$ , that $\mathbb E[\xi\mid\mathcal F_i(s)] = \mathbb E[\xi\mid\mathcal F^i(s)]$ . Notice by (6.4) that $\mathcal F_i(t)\cap\mathcal F^i(s)=\mathcal F_i(s)$ , so (6.2) yields

\begin{align*} \mathbb E[\xi\mid\mathcal F_i(s)] = \mathbb E[\xi\mid\mathcal F_i(t)\cap\mathcal F^i(s)] = \mathbb E[\xi\mid\mathcal F^i(s)], \end{align*}

as desired.

Proof. Fix arbitrary $t\in\mathbb N_0$ , $\tilde r\in\mathbb N_0^d$ , and $\Lambda\in\mathcal F(\tilde T(t))$ . Since $\mathbf F(\tilde T)$ is a filtration by Proposition 7, it suffices to show $\mathbb E[X(\tilde T(t+1))\mathbf{1}_{\Lambda\cap\{\tilde T(t)=\tilde r\}}]\le\mathbb E[X(\tilde T(t))\mathbf{1}_{\Lambda\cap\{\tilde T(t)=\tilde r\}}]$ by definition of conditional expectation. We have

\begin{align*}\mathbb E\big[X(\tilde T(t+1))\mathbf{1}_{\Lambda\cap\{\tilde T(t)=\tilde r\}}\big]&= \sum_{i=1}^d \mathbb E\big[X(\tilde r+\tilde e_i)\mathbf{1}_{\Lambda\cap\{\tilde T(t)=\tilde r,\,\tilde T(t+1)=\tilde T(t)+\tilde e_i\}}\big] \\&\le \sum_{i=1}^d \mathbb E\big[X(\tilde r)\mathbf{1}_{\Lambda\cap\{\tilde T(t)=\tilde r,\,\tilde T(t+1)=\tilde T(t)+\tilde e_i\}}\big]\le \mathbb E\big[X(\tilde T(t))\mathbf{1}_{\Lambda\cap\{\tilde T(t)=\tilde r\}}\big],\end{align*}

where the inequality follows from the supermartingality of $\mathbf X$ with the fact that $\Lambda\cap\{\tilde T(t)=\tilde r,\,\tilde T(t+1)=\tilde T(t)+\tilde e_i\}\in\mathcal F(\tilde r)$ by definition of allocation strategies.

Proof. We prove the lemma for supermartingales; the same arguments hold for the martingale case. We may assume $\tilde s=\tilde 0$ . For each $i=1,\dots,d$ , the process

\begin{align*} U_i(t) \;:\!=\; \sum_{u=0}^{t-1}\beta^{-u} (Q_i(u+1)-Q_i(u) ),\quad t\in\mathbb N_0 \end{align*}

is an $\mathbf F_i$ -supermartingale because it is an integrable martingale transform of $Q_i$ by the deterministic process $\{\beta^{-u}\}_{u\in\mathbb N_0}$ . In particular, it is an $\mathbf F^i$ -supermartingale by the enlargement of filtrations property, Proposition 13. We obtain then from Proposition 14 (the (c) $\implies$ (a) implication) that the random field

\begin{align*}U(\tilde r)\;:\!=\;\sum_{i=1}^dU_i(r_i),\quad \tilde r\in\mathbb N_0^d,\end{align*}

is an $\mathbf F$ -supermartingale. Now Proposition 15 implies that

\begin{align*} U(\tilde T(t)) &= \sum_{i=1}^d\sum_{u=0}^{t-1}\beta^{-T_i(u)} (Q_i(T_i(u+1))-Q_i(T_i(u)) ), \quad t\in\mathbb N_0 \end{align*}

is an $\mathbf F(\tilde T)$ -supermartingale. Taking the martingale transform of $U(\tilde T)$ by $\{\beta^u\}_{u\in\mathbb N_0}$ yields the desired $\mathbf F(\tilde T)$ -supermartingale.

Proof of (T2). For each $i=1,\dots,d$ , let

(7.8) \begin{align} Y_i(t) \;:\!=\; V_i\big(t;\;\underline M_i\big(T_i^*(t)\big)\big) - \underline M_i\big(T_i^*(t)\big), \quad t\in\mathbb N_0. \end{align}

In the notation of Proposition 6, we may write

\begin{align*} K(t) &= \sum_{i=1}^d \sum_{u=0}^{t-1} \beta^{u-T_i^*(u)} \big[\beta^{T_i^*(u+1)}Y_i(u+1) - \beta^{T_i^*(u)}Y_i(u) \\ &\quad + \beta^{T_i^*(u)}\big(h_i\big(T_i^*(u+1)\big) - (1-\beta)\underline M_i\big(s_i,T_i^*(u)\big)\big)\big] \big(T_i^*(u+1)-T_i^*(u)\big), \end{align*}

yielding

(7.9) \begin{align} W(t) \;:\!=\; K(t)-\Lambda(t) = \sum_{i=1}^d\sum_{u=0}^{t-1}\beta^{u-T_i^*(u)} \big(\beta^{T_i^*(u+1)}Y_i(u+1)-\beta^{T_i^*(u)}Y_i(u)\big). \end{align}

Observe that $Y_i(t)=0$ whenever $M_i(T_i^*(t)) = \underline M_i(T_i^*(t))$ , by virtue of (3.1). Then by (5.14), (5.16), and Lemma 6, the summand in (7.9) is non-zero for exactly a single project at each time u, and consequently, the almost sure limit $W(\infty) \;:\!=\; \lim_{t\to\infty}W(t)$ exists and equals the sum

(7.10) \begin{align} W(\infty) = \sum_{i=1}^d \sum_{k=0}^\infty \sum_{u=\rho(k;\;\tilde T^*)}^{\rho(k+1;\;\tilde T^*)-1} \beta^{u-T_i^*(u)}\big(\beta^{T_i^*(u+1)}Y_i(u+1) - \beta^{T_i^*(u)}Y_i(u)\big), \end{align}

in the notation of (4.14) and (5.16). Note that the sum converges absolutely since $|\beta^{-T_i^*(u)}(\beta^{T_i^*(u+1)}Y_i(u+1) - \beta^{T_i^*(u)}Y_i(u))|$ is bounded by 2K.

In light of Lemma 6, let $j\equiv j(k)$ be the exclusive project engaged between times $\rho(k;\;\tilde T^*)$ and $\rho(k+1;\;\tilde T^*)$ . The summand in (7.10) is zero for every $i\neq j$ , and

(7.11) \begin{align} & \sum_{u=\rho(k;\;\tilde T^*)}^{\rho(k+1;\;\tilde T^*)-1} \beta^{u-T_j^*(u)} \big(\beta^{T_j^*(u+1)}Y_j(u+1)-\beta^{T_j^*(u)}Y_j(u)\big)\nonumber \\ &\quad = \beta^{\rho(k+1;\;\tilde T^*)}Y_j(\rho(k+1;\;\tilde T^*)) - \beta^{\rho(k;\;\tilde T^*)}Y_j(\rho(k;\;\tilde T^*)). \end{align}

Both terms on the right-hand side are zero since $\rho(k;\;\tilde T^*)$ and $\rho(k+1;\;\tilde T^*)$ are by definition times where the Gittins indices of every project coincides with their lower envelopes, so we obtain from (7.10) that $W(\infty)=0$ . Assuming that (T1) holds, we have the existence of $K(\infty)$ , since uniformly integrable martingales converge a.s. It follows that $\Lambda(\infty)$ exists and $K(\infty)=\Lambda(\infty)$ . Moreover, it is clear from the definition that $\Lambda(\!\cdot\!)$ is uniformly bounded from above by the random variable

\begin{align*}\sum_{i=1}^d\left[\sum_{u=0}^\infty\beta^uh_i(u) + \sum_{u=0}^\infty\beta^u(1-\beta)\underline M_i(u)\right]\!,\end{align*}

which is integrable thanks to the boundedness of the sequences $h_i(\!\cdot\!)$ and $\underline M_i(\!\cdot\!)$ . Therefore, $\Lambda(\infty)$ is a.s. absolutely convergent, and the process $\{\Lambda(t)\}_{t\in\mathbb N_0}$ is uniformly integrable.

Proof of ( T1 ). Each process $U_i(\!\cdot\!)$ of Proposition 6 is an $\mathbf F_i$ -martingale, so the process $K(\!\cdot\!)$ of (7.5) is an $\mathbf F(\tilde T^*)$ -martingale, by Lemma 7. In the notation of (7.9), we may write $K(\!\cdot\!)=$ $\Lambda(\!\cdot\!)+W(\!\cdot\!)$ , so it suffices to show that the families $\{\Lambda(t)\}_{t\in\mathbb N_0}$ and $\{W(t)\}_{t\in\mathbb N_0}$ are each uniformly integrable; we have already shown that $\{\Lambda(t)\}_{t\in\mathbb N_0}$ is uniformly integrable in the proof of (T2).

Fix $t\in\mathbb N_0$ and observe, by an argument analogous to that of (7.10) and (7.11), that

\begin{align*}W(t) = \sum_{u=\rho(k;\;\tilde T^*)}^{t-1}\beta^{u-T_j^*(u)} \big(\beta^{T_j^*(u+1)}Y_j(u+1) - \beta^{T_j^*(u)}Y_j(u)\big) = \beta^tY_j(t),\end{align*}

where k is the largest integer for which $t\gt\rho(k;\;\tilde T^*)$ , and $j\equiv j(t)$ is the unique project engaged at time t.

Thus, we wish to show the uniform integrability of $\{\beta^tY_{j(t)}(t)\}_{t\in\mathbb N_0}$ . For every $s\in\mathbb N_0$ and $m\ge0$ , we have by (3.15), (3.16), and Remark 6 that

\begin{align*} \beta^t[V_i(s;\;m)-m] &\le (1-\beta)\,\mathbb E\left[\sum_{\theta=s}^\infty\beta^\theta \underline M_i(s,\theta)\,\middle\vert\,\mathcal F^i(s)\right] \le \mathbb E\left[\sum_{\theta=0}^\infty\beta^\theta h_i(\theta+1)\,\middle\vert\,\mathcal F^i(s)\right]\!, \quad\text{a.s.} \end{align*}

for each $i=1,\dots,d$ . Since $Y_{j(t)}(t)$ is $\mathcal F(\tilde T^*(t))$ -measurable, the tower rule yields

\begin{align*} \beta^tY_{j(t)}(t) \le \mathbb E\left[\sum_{\theta=0}^\infty \beta^\theta h_{j(t)}(\theta+1)\,\middle\vert\,\mathcal F(\tilde T^*(t))\right]\!, \quad\text{a.s.} \end{align*}

As a consequence of the uniform boundedness of $\{h_i(\theta)\}_{\theta\in\mathbb N_0}$ over every $i=1,\dots,d$ , the family

\begin{align*}\left\{\mathbb E\left[\sum_{\theta=0}^\infty\beta^\theta h_{j(t)}(\theta+1) \,\middle\vert\, \mathcal F(\tilde T^*(t))\right]\right\}_{t\in\mathbb N_0}\end{align*}

is uniformly integrable [Reference Durrett7, Theorem 4.6.1]; hence the same holds for $\{W(t)\}_{t\in\mathbb N_0}$ .

Proof. For ease of notation, set $F_i(t)=f_i(T_i(t))$ , and define the finite difference operator $\Delta f(t) \;:\!=\; f(t+1)-f(t)$ . The inner sum, via summation by parts, equals

\begin{align*} \beta^{F(t-1)+\Delta F_i(t-1)} - \beta^{F(\theta)} + \sum_{u=\theta}^{t-2} \beta^{F(u)}\big(\beta^{\Delta F_i(u)} - \beta^{\Delta F(u)}\big). \end{align*}

Since allocation strategies can engage in only one project at a time, then for each $u=\theta,\dots,t-1$ , either we must have $\Delta F(u)=\Delta F_i(u)=0$ for all $i=1,\dots,d$ , or there exists a unique $j\equiv j(u)$ for which $\Delta F(u) = \Delta F_j(u)\gt0$ while $\Delta F_i(u)=0$ for $i\neq j$ . Thus, letting $\theta\le u_0\lt\dots\lt u_n\lt t-1$ be the points at which $\Delta F(u)\gt0$ , we obtain

\begin{align*} \sum_{i=1}^d\sum_{u=\theta}^{t-2} \beta^{F(u)}\big(\beta^{\Delta F_i(u)} - \beta^{\Delta F(u)}\big) &= \sum_{u=\theta}^{t-2} \sum_{\substack{i=1\\i\neq j(u)}}^d \beta^{F(u)}\big(1-\beta^{\Delta F(u)}\big) \\ &= (d-1)\sum_{k=0}^n \beta^{F(u_k)}\big(1-\beta^{\Delta F(u_k)}\big). \end{align*}

Similarly, we find $\sum_{i=1}^d \beta^{F(t-1)+\Delta F_i(t-1)} = (d-1)\beta^{F(t-1)} + \beta^{F(t)}$ . Consequently, the left-hand side of (7.12) is given by

\begin{align*} \beta^{F(t)}-\beta^{F(\theta)} + (d-1)\Bigg[\beta^{F(t-1)} - \beta^{F(\theta)} + \sum_{k=0}^n\big(\beta^{F(u_k)}-\beta^{F(u_{k+1})}\big)\Bigg], \end{align*}

using the fact that $F(u_k)+\Delta F(u_k) = F(u_k+1) = F(u_{k+1}) $ , with the convention that $F(u_{n+1}) = F(t-1)$ . Now the summation telescopes and equals $\beta^{F(u_0)}-\beta^{F(u_{n+1})}$ but, by definition, $F(u_0)=F(\theta)$ and $F(u_{n+1})=F(t-1)$ . Thus the term inside the square brackets is zero, completing the proof.

Proof of ( T3 ). For each project $i=1,\dots,d$ , let $\{V_i(t)\}_{t=s_i}^\infty$ and $\{Z_i(t)\}_{t=s_i}^\infty$ be the corresponding value processes and Snell envelopes, respectively, in the notation of (2.1) and (2.4) with $m=0$ . Set

(7.13) \begin{align} X_1(t;\;\tilde T) \;:\!=\; \sum_{i=1}^d\sum_{u=0}^{t-1} \beta^{u-T_i(u)} (Z_i(T_i(u+1)) - Z_i(T_i(u)) ), \end{align}

as well as

(7.14) \begin{align} X_2(t;\;\tilde T) \;:\!=\; \beta^t\widehat\Phi(\tilde T(t)) - \sum_{i=1}^d\sum_{u=0}^{t-1} \beta^{u-T_i(u)}\big(\beta^{T_i(u+1)}V_i(T_i(u+1)) - \beta^{T_i(u)}V_i(T_i(u))\big). \end{align}

It follows from (2.5) that $Q(t;\;\tilde T) = X_1(t;\;\tilde T)+X_2(t;\;\tilde T)$ , so it suffices to show that $\{X_1(t;\;\tilde T)\}_{t\in\mathbb N_0}$ and $\{X_2(t;\;\tilde T)\}_{t\in\mathbb N_0}$ are non-negative, bounded $\mathbf F(\tilde T)$ -supermartingales. Since Snell envelopes are non-negative $\mathbf F_i$ -supermartingales, the former follows from Lemma 7. For the latter, observe that (4.20) and (4.8) imply

\begin{align*}\beta^t\widehat\Phi(\tilde T(t)) = \mathbb E\left[\int_0^\infty\big(\beta^t-\beta^{\sum_{i=1}^d\sigma_i(T_i(t);\;m)}\big)\mathrm{d} m\,\middle\vert\,\mathcal F(\tilde T(t))\right]\end{align*}

while (3.10), in conjunction with Proposition 13 yields, for each $i=1,\dots,d$ ,

\begin{align*}\beta^{T_i(t)}V_i(T_i(t)) = \mathbb E\left[\int_0^\infty\left(\beta^{T_i(t)} - \beta^{\sigma_i(T_i(t);\;m)}\right)\mathrm{d} m\,\middle\vert\,\mathcal F^i(T_i(t))\right]\!.\end{align*}

We aim to show, for every $\theta\lt t$ , that $\mathbb E[X_2(t;\;\tilde T)\mid\mathcal F(\tilde T(\theta))] \le X_2(\theta;\;\tilde T)$ . This is equivalent, on rearranging terms in (7.14), to showing

(7.15) \begin{multline} \mathbb E\left[\int_0^\infty \left(\beta^{\sum_{i=1}^d\sigma_i(T_i(t);\;m)} - \beta^{\sum_{i=1}^d\sigma_i(T_i(\theta);\;m)} \phantom{\sum_{i=1}^d} \right.\right. \\[3pt] \left.\left. + \sum_{i=1}^d\sum_{u=\theta}^{t-1} \beta^{u-T_i(u)} \big(\beta^{\sigma_i(T_i(u);\;m)} - \beta^{\sigma_i(T_i(u+1);\;m)}\big)\right)\mathrm{d} m\,\middle\vert\,\mathcal F(\tilde T(\theta))\right] \\[3pt] \ge \mathbb E\left[\int_0^\infty\left(\beta^t - \beta^\theta + \sum_{i=1}^d\sum_{u=\theta}^{t-1} \beta^{u-T_i(u)}\big(\beta^{T_i(u)} - \beta^{T_i(u+1)}\big)\right)\mathrm{d} m\,\middle\vert\,\mathcal F(\tilde T(\theta))\right]\!. \end{multline}

The integrand on the right-hand side is identical to zero by Lemma 8, setting each $f_i$ to be the identity. Conversely, observe that $u-T_i(u) = \sum_{j\neq i} T_j(u) \le \sum_{j\neq i}\sigma_j(T_j(u);\;m)$ a.s., so the integrand on the left-hand side dominates:

\begin{align*} \beta^{\sum_{i=1}^d\sigma_i(T_i(t);\;m)} - \beta^{\sum_{i=1}^d\sigma_i(T_i(\theta);\;m)} + \sum_{i=1}^d\sum_{u=\theta}^{t-1} \beta^{\sum_{j\neq i}\sigma_j(T_j(u);\;m)} \big(\beta^{\sigma_i(T_i(u);\;m)} - \beta^{\sigma_i(T_i(u+1);\;m)}\big). \end{align*}

This is non-negative, again by Lemma 8 with $f_i(t) \;:\!=\; \sigma_i(t;\;m)$ . This completes the proof of (T3) and thus that of Theorem 4 as well.

Proof. By Lemma 4, $0\le {\partial^+}V_i(s_i;\;m)/{\partial m} \le1$ holds for each $i=1,\dots,d$ ; hence $F(\tilde s;\;M)\ge M$ when $M\lt K$ , which proves (8.3). Also, by Lemma 4, ${\partial^+}V_i(s_i;\;m)/{\partial m}=1$ holds if $m\ge M_i(s_i)$ ; hence $\prod_{i=1}^d({\partial^+}V_i(s_i;\;m)/{\partial m})=1$ if $m\ge\mathcal M(\tilde s)$ . Then the integrand in (8.2) is identical to one when $M\ge\mathcal M(\tilde s)$ , which proves (8.5).

To prove (8.4), first consider the case where $M\ge K$ . From the bound $0\le h_i\le K(1-\beta)$ , we easily obtain

\begin{align*}h_i(s_i+1)+\beta\,\mathbb E[F(\tilde s+\tilde e_i;\;M)\mid\mathcal F(\tilde s)] \le K(1-\beta)+\beta M \le M = F(\tilde s;\;M).\end{align*}

Now suppose that $0\le M\lt K$ . Fix $i\in\{1,\dots,d\}$ and denote the vector given by removing the ith coordinate of $\tilde s$ by $\tilde s^{(i)}\;:\!=\;(s_1,\dots,s_{i-1},s_{i+1},\dots,s_d) \in\mathbb N_0^{d-1}$ . Consider the mapping

\begin{align*}m\mapsto P_i\big(\tilde s^{(i)};\;m\big) \;:\!=\; \prod_{\substack{j=1\\j\neq i}}^d \frac{\partial^+}{\partial m} V_j(s_j;\;m), \quad m\ge0.\end{align*}

Observe that, by Lemma 4 and (4.7), we have $P_i(\tilde s^{(i)};\;K)=1$ . Additionally, (2.9), (3.4), and (4.7) imply that $V_i(s_i;\;K)=K$ . Integrating by parts then yields

(8.7) \begin{align} F(\tilde s;\;M) &= K - \int_M^K P_i \big(\tilde s^{(i)};\;m \big) \cdot \frac{\partial^+}{\partial m}V_i(s_i;\;m)\,\mathrm{d} m \nonumber \\ &= V_i(s_i;\;M)P_i \big(\tilde s^{(i)};\;M \big) + \int_M^K V_i(s_i;\;m)\,\mathrm{d}_mP_i \big(\tilde s^{(i)};\;m \big). \end{align}

Therefore,

\begin{align*}F(\tilde s+\tilde e_i;\;M) = V_i(s_i+1;\;M)P_i \big(\tilde s^{(i)};\;M \big) + \int_M^K V_i(s_i+1;\;m)\,\mathrm{d}_mP_i \big(\tilde s^{(i)};\;m \big).\end{align*}

Since $V_i(s_i+1;,\!)\in\mathcal F_i(s_i+1)$ , the (F4) condition in the form (6.2) yields $\mathbb E[V_i(s_i+1;\;m)\mid \mathcal F(\tilde s)] = \mathbb E[V_i(s_i+1;\;m)\mid\mathcal F_i(s_i)]$ for all $m\ge0$ . Since $P_i(\tilde s^{(i)};\;M)$ is $\mathcal F(\tilde s)$ -measurable, taking conditional expectations and applying Fubini’s theorem yields

(8.8) \begin{align} &\mathbb E[F(\tilde s+\tilde e_i;\;M)\mid\mathcal F(\tilde s)] \notag \\ & \quad = P_i\big(\tilde s^{(i)};\;M\big)\mathbb E[V_i(s_i+1;\;M)\mid\mathcal F_i(s_i)] + \int_M^K \mathbb E[V_i(s_i+1;\;m)\mid\mathcal F_i(s_i)]\,\mathrm{d}_m P_i \big (\tilde s^{(i)};\;m \big ). \end{align}

Now define

\begin{align*}\phi_i(t;\;m) \;:\!=\; V_i(t;\;m) - h_i(t+1) - \beta\,\mathbb E[V_i(t+1;\;m)\mid\mathcal F_i(t)].\end{align*}

By (8.7), (8.8), and the fact that $P_i(\tilde s^{(i)};\;K)=1$ , we obtain the identity

(8.9) \begin{align} & \phi_i(s_i;\;M)P_i \big(\tilde s^{(i)};\; M\big) + \int_M^K \phi_i(s_i;\;m)\,\mathrm{d}_mP_i\big(\tilde s^{(i)};\;m\big) \notag \\ &\quad = F(\tilde s;\;M)-h_i(s_i+1)-\beta\,\mathbb E[F(\tilde s+\tilde e_i;\;M)\mid\mathcal F(\tilde s)]. \end{align}

The left-hand side of (8.9) is non-negative by (2.9), so the right-hand side is non-negative as well, proving (8.4).

It remains to show (8.6). On $\{M\lt M_i(s_i)\;:\!=\;\mathcal M(\tilde s)\}$ , we have $M\lt K$ by (4.7), so it suffices to show that the left-hand side of (8.9) is zero in this event.

Let $m\in[M,K]$ be given. On $\{m\lt M_i(s_i)\}$ , we have by (3.4) that $V_i(s_i;\;m)\gt m$ ; hence (2.9) implies $\phi_i(s_i;\;m)=0$ . In particular, $\phi_i(s_i;\;M)=0$ . Conversely, we have by definition that $m\ge M_j(s_j)$ holds for each $j=1,\dots,d$ on $\{m\ge M_i(s_i)\}$ . Lemma 4 then implies $P_i(\tilde s^{(i)};\;m)=1$ ; hence

\begin{align*}\int_M^K\phi_i(s_i;\;m)\,\mathrm{d}_mP_i\big(\tilde s^{(i)};\;m\big) = \int_M^{M_i(s_i)}0\,\mathrm{d}_mP_i\big(\tilde s^{(i)};\;m\big) + \int_{M_i(s_i)}^K \phi_i(s_i;\;m)\,\mathrm{d}_m(1) = 0,\end{align*}

which proves (8.6).