  We obtain optimal Gaussian concentration bounds (GCBs) for stochastic chains
of unbounded memory (SCUMs) on countable alphabets. These stochastic processes
are also known as "chains with complete connections" or "$g$-measures". We
consider two different conditions on the kernel: (1) when the sum of its
oscillations is less than one, or (2) when the sum of its variations is finite,
i.e., belongs to $\ell^1(\mathbb{N})$. We also obtain explicit constants as
functions of the parameters of the model. The proof is based on maximal
coupling. Our conditions are optimal in the sense that we exhibit examples of
SCUMs that do not have GCB and for which the sum of oscillations is strictly
larger than one, or the variation belongs to $\ell^{1+\epsilon}(\mathbb{N})$
for any $\epsilon > 0$. These examples are based on the existence of phase
transitions. We also extend the validity of GCB to a class of functions which
can depend on infinitely many coordinates.
  We illustrate our results by three applications. First, we derive a
Dvoretzky-Kiefer-Wolfowitz type inequality which gives a uniform control on the
fluctuations of the empirical measure. Second, in the finite-alphabet case, we
obtain an upper bound on the $\bar{d}$-distance between two stationary SCUMs
and, as a by-product, we obtain new (explicit) bounds on the speed of Markovian
approximation in $\bar{d}$. Third, we obtain exponential rate of convergence
for Birkhoff sums of a certain class of observables.
