@Arshdeep Ito's lemma encapsulates the leading order (i.e. $O(dt)$) deterministic increment together with the leading order (i.e. $O(dt^{1/2})$) stochastic increment. Consequently for $W_t^3$ at $t=0$ what it reports is that both of those are zero. There's no contradiction, it's just an incomplete picture.

(You also need to replace $\frac{1}{n}$ with $\frac{1}{n-|s|}$, my bad.)

Now this particular problem has some structure that you can exploit. In particular, you can write a version of the system without self-loops Once you prune the self-loops by replacing that $1$ with $\frac{n}{n-|s|}$ and replacing $x \in U$ with $x \in U \setminus s$. Now the graph that you are moving on is a tree, leaving some more hope of an analytical solution of some kind.

One can treat this process as a Markov chain on the power set of $U$ where at each time you go from $s$ to $s \cup \{ x \}$ where $x$ is chosen uniformly at random. Of course you don't care about duplicates, so in some cases $s \cup \{ x \} = s$. By conditioning on one step, you can calculate $u(s):=E[T \mid S_0=s]=1+\frac{1}{n} \sum_{x \in U} E[T \mid S_0=s \cup \{ x \}]$ if $s$ does not contain a collection, and $u(s)=0$ if $s$ does contain a collection. This is a system of $2^n$ linear equations in $2^n$ unknowns which you can solve.

Computationally speaking, getting the expectation is a fairly straightforward task with renewal theory that ultimately boils down to an inhomogeneous linear system. Doing this on some cases for the vector $(|C_1|,\dots,|C_n|)$ might give you some insight into e.g. scaling relationships.

@fedja Yes, I hang out on MSE a lot and hadn't received a notification on this question, so thanks for pinging me.

@oferzeitouni I see what you mean. It seems then that the approximations to my original problem were not quite good enough for me to use this to solve it. This is because actually $T,b$ in my real problem depend on $x$, and I was attempting to approximate them by simply $T(x^*),b(x^*)$. But the underlying random walk for $T(x^*)$ has mean zero, whereas other $T(x)$'s have positive mean and others have negative mean.

I think in the $\ell^1$ case you are referring to the fact that $T$ can be written as $S D^{-1}$ where $S$ is row stochastic and $D$ is diagonal with $D_{ii}=\sum_k T_{ik}$, so powers of $T$ are more or less controlled by powers of $S$. Is that right? I think I see the idea you are referring to in the $\ell^p$ case (there is some sort of "spreading" that leads to decay in $\ell^p$ even if not in $\ell^1$).

@fedja An affirmative answer to that would answer the question, but a negative answer wouldn't (I'd like a hypothesis on $x^{(0)}$ that works even if it turns out to be restrictive).

In the "for matrices gives..." equation, is it the reciprocal of the trace or the trace of the inverse?

@Alice Proceeding directly, that creates a problem for you indeed. But you can estimate $T(x)$ for small $x$ using some other method (for example, Newton's method, starting from a nonzero initial condition) and then use Robert Israel's suggestion for larger $x$, using that other estimate as your initial condition.

Is there something wrong with Newton's method? The relevant iteration reads $t_{n+1}=t_n-\frac{G(t_n)-x}{H(t_n)}$. It shouldn't take long to converge for an increasing convex function.