If $\Bbb EN\in O(1)$ and $\Bbb ET_{i,n}\in O(t_n)$, can we conclude $\Bbb E\sum_{i=1}^N T_{i,n} \in O(t_n)$? Suppose for each $n\in \Bbb N$ that $N_n$ is a random variable with values in $\Bbb N$, and $(T_{i,n})_{i\in\Bbb N}$ is a sequence over the index $i$ of i.i.d. positive random variables.

Question: If $\Bbb EN_n\in O(1)$ and $\Bbb ET_{i,n}\in O(t_n)$, can we conclude $\Bbb E\sum_{i=1}^N T_{i,n} \in O(t_n)$?

(You can think of $n$ as the input size to an algorithm, and we're taking the big-oh as $n\to\infty$. More context on this below). This is a lot like Wald's equation, but without indepence between $N$ and the $T$'s, I don't know if we can do the above.

Context: On an old exam question I had several years back, we were considering a randomized algorithm on input size $n$, with expected running time $\le t_n$ and expected space usage $\le s_n$. We were asked to design an alogrithm with worst case space usage $O(s_n)$ and expected run time $O(t_n)$. The following hint was given:

Hint: Restart the algorithm as neccesary. Note that there are two obvious choices for when to restart that both work, but one is much easier to analyze than the other.

My solution was to restart the algorithm of the space usage ever exceeded $ks_n$ or if the time usage ever exceeded $kt_n$, for some $k>2$. A pretty easy calculation then shows that $\Bbb EN \le \frac 1{1-2/k}\in O(1)$, where $N$ is the number of iterations of the algorithm, from which it follows that the expected total time is $\le kt_n \cdot\Bbb EN \in O(t_n)$.
But looking back, I'm now wondering what the other solution alluded to was. The other obvious choice to me, would be simply restarting the algorithm if the space used exceeds $ks_n$ for some constant $k$. Using a Markov inquality on the probability of restarting now leeds to $\Bbb EN \le \frac 1{1-1/k}\in O(1)$. Now, let $T_n$ be the total time of the algorithm, let $T'_{i,n}$ be the time used on each of iteration, and let $T_{i,n}$ be the time we would have used if we did not restart the algorithm. Then we get
$$
\Bbb ET = \Bbb E\sum_{i=1}^NT'_{i,n} \le \Bbb E\sum_{i=1}^NT_{i,n}.
$$
So the big question is, do we have $\Bbb E\sum_{i=1}^NT_{i,n}\in O(\Bbb ET_{i,n})$ or not? Note that $N$ is a stopping time for the space usage random variable, but not for $T_{i,n}$, so I don't think Wald's equation applies directly. We may use that time usage is always greater than space usage in an algorithm, if that somehow helps. Otherwise, I'm maybe hoping for an inequality version of Wald, something like
$$
\Bbb E\sum_i^N X_i \le C\cdot\Bbb EN \Bbb EX_i?
$$
Also,

Bonus question: If this approach actually doesn't work, what would be the second "obvious" (but hard) solution that the exam givers allude to?

 A: Your question has a bunch of structure beyond the raw $\mathbb{E}[\sum_{i \le n} T_{i,n}]$, since presumably

*

*each time you restart the algorithm, you draw new coins for the new run.

*the expected run time and space are bounded by $(t_n, s_n)$ uniformly over all instances of size $n$ (i.e., the expectation is only over the coins of the algorithm).

If so, then the details of the instance don't matter due to 2., and  all of the $(T_{i,n}, S_{i,n})$ are independent due to 1., which
simplifies things a lot.
Let me first clean up some notation - the $n$ is really not all that important for the problem, and neither is the details about the $S$s. So suppose $\{(U_i, V_i)\}$ is an infinite iid sequence from some law, where $V_i \sim \mathrm{Bern}(p)$. Let $N := \inf\{i: V_i = 1\}$. We are interested in the behaviour of $S_N := \sum U_i \mathbf{1}\{i \le N\}.$
With the above structure, it is straightforward to figure out the law of $(U_1, \dots, U_m)$ given $N = m$ (i'll work with pmfs, but densities work the same way). Indeed, $\{N = m\} = \{V_1^{m-1} = 0, V_m = 1\},$ and so, exploiting independence
$$ P(U_1^m = u_1^m, N = m) = \prod_{i < m} P(U_i = u_i, V_i = 0) \cdot P(U_m = u_m, V_m = 1)\\ P(N = m) = \prod_{i < m} P(V_i = 0) \cdot P(V_m = 1),$$ and thus $$ P(U_1^m = u_1^m|N = m) = \prod_{i < m} P(U_i = u_i|V_i = 0) \cdot P(U_m = u_m|V_m = 1).$$
Let $\mu_0$ and $\mu_1$ be the conditional mean of $U$ given $V = 0$ and $1$ respectively. Then by the above, $$ \mathbb{E}[ \sum_{i  = 1}^N U_i|N = m] = (m-1) \mu_0 + \mu_1,$$ and applying the tower rule $$ \mathbb{E}[S_n] = \mathbb{E}[\sum_{i = 1}^N U_i] = \sum P(N = m) ((m-1)\mu_0 + \mu_1) = (\mathbb{E}[N] -1) \mu_0 + \mu_1.$$
Now let $p = P(V = 1)$. Notice that $\mathbb{E}[N] = \frac{1}{p}$. Further, let $\mu = (1-p)\mu_0 + p\mu_1$ be the mean of $U$. Then we have $$ \mathbb{E}[S_N] = \frac{1-p}{p} \mu_0 + \mu_1 = \frac{1}{p} \mu.$$
Finally lets come back to the algorithm. Let $(T_i, S_i)$ represent an iid sequence of the runtimes on a given instance, where we draw new random coins for each run. Let $V_i$ be $0$ if the algorithm concludes before time $T_i$ due to using too much space, and $1$ otherwise. Let $U_i = T_i',$ the stoppage time of the ith run. Note that since for every $i$, $T_i' \le T_i,$ the mean of the $T'$s is bounded by that of the $T$s. Now running the above gives exactly what you wanted.
