\documentclass[finalversion]{FPSAC2020}
\articlenumber{86}
\addbibresource{fpsac.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\usepackage{forest}
\forestset{
  decor/.style = {
    label/.expanded = {[inner sep = 0.1ex, font=\unexpanded{\tiny}]right:{$#1$}}
  },
  root/.style = {minimum size = 0.5ex},
  decorated/.style = {
    for tree = {
      circle, fill, inner sep = 0ex, minimum size = 0.5ex,
      grow' = north, l = 0, l sep = 0.8ex, s sep = 0.5em,
      fit = tight, parent anchor = center, child anchor = center,
      delay = {decor/.option = content, content =}
    }
  },
  default preamble = {decorated, root},
  begin draw/.code={\begin{tikzpicture}[baseline={([yshift=-0.5ex]current bounding box.center)}]},
}


%% note that the class file already loads {amsmath, amsthm, amssymb}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{rem}[thm]{Remark}
\newtheorem{defn}[thm]{Definition}


\usepackage[linecolor=white,backgroundcolor=white,bordercolor=white,textsize=tiny]{todonotes}
\let\todon\todo
\renewcommand{\todo}[1]{\todon{\color{red}#1}}

\makeatletter
\newcommand{\ostar}{\mathbin{\mathpalette\make@circled\star}}
\newcommand{\make@circled}[2]{%
  \ooalign{$\m@th#1\smallbigcirc{#1}$\cr\hidewidth$\m@th#1#2$\hidewidth\cr}%
}
\newcommand{\smallbigcirc}[1]{%
  \vcenter{\hbox{\scalebox{0.77778}{$\m@th#1\bigcirc$}}}%
}
\makeatother
\usepackage{mathtools, microtype, shuffle, mleftright}
\usepackage{tikz-cd}

%% define your title in the usual way
\title{Iterated-sums signature, quasisymmetric functions and time series analysis}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Joscha Diehl, Kurusch Ebrahimi-Fard, and Nikolas Tapia]
{Joscha Diehl\thanks{\href{mailto:joscha.diehl@gmail.com}{joscha.diehl@gmail.com}.}\addressmark{1},
  Kurusch Ebrahimi-Fard\thanks{\href{mailto:kurusch.ebrahimi-fard@ntnu.no}{kurusch.ebrahimi-fard@ntnu.no}.}\addressmark{2},
  \and Nikolas Tapia\thanks{\href{mailto:tapia@wias-berlin.de}{tapia@wias-berlin.de}. Supported by the BMS MATH+ EF1-5 project ``On robustness of deep neural networks''.}\addressmark{3,4}
}
%{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{
\addressmark{1} Universit\"at Greifswald, Institut f\"ur Mathematik und Informatik,  Greifswald, Germany.\\
\addressmark{2} Department of Mathematical Sciences, Trondheim, Norway.\\
\addressmark{3} Weierstra{\ss}-Institut Berlin, Berlin, Germany.\\
\addressmark{4} Technische Universit\"at Berlin, Berlin, Germany.
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract
{
We survey and extend results on a recently defined character on the quasi-shuffle algebra.
This character, termed iterated-sums signature, appears in the context of
time series analysis and originates from a problem in dynamic time warping.
Algebraically, it relates to (multidimensional) quasisymmetric functions
as well as (deformed) quasi-shuffle algebras.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Shuffle and quasi-shuffle Hopf algebras, half-shuffles, iterated integral- and sum-signatures, quasisymmetric functions, Hoffman's exponential.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\S{\mathsf{DS}}
\newcommand\field{\mathbb F}

\mleftright

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Introduction}
\label{sec:signatures}

In his seminal 1954 paper \cite{Chen1954}, K.-T.~Chen introduced the iterated-integral signature of a smooth path taking values in a finite-dimensional smooth manifold. We recall the definition for the special case of curves on $d$-dimensional Euclidean space using the shuffle product introduced by Ree \cite{Ree1958}.
%
Let $A=\{1,\dotsc,d\}$ be a finite alphabet, and let $A^*$ denote the free monoid, which consists of all words with letters from $A$; the unit element, the \emph{empty word} is denoted by $e$. A noncommutative product is \emph{concatenation} of words, denoted by juxtaposition.
The linear space $H$ spanned%
\footnote{ In the following all algebraic structures are defined over a base field $\field$ of characteristic zero.}
by $A^*$ has an algebra structure given by the \emph{shuffle product} ${\shuffle}\colon H\otimes H\to H$, recursively defined by $e\shuffle u\coloneqq u\eqqcolon u\shuffle e$ for all $u\in H$, and
\[
  ua\shuffle vb\coloneqq(u\shuffle vb)a+(ua\shuffle v)b
\]
for $u,v\in H$ and $a,b\in A$. It is a standard result that $(H,\shuffle,e)$ is a commutative algebra \cite{Reutenauer93}.

Given a smooth path $x\colon[0,1]\to\R^d$, $t\mapsto x(t)=(x^1(t),\dotsc,x^d(t))$ and a word $w=i_1\dotsm i_n\in A^*$ define the iterated integral
\[
  S(x)^w\coloneqq\idotsint\limits_{0<s_1<\dotsb<s_n<1}\dot x^{i_1}(s_1)\dotsm
  \dot x^{i_n}(s_n)\,\mathrm ds_1\dotsm\mathrm ds_n.
\]
This can be linearly extended to all of $H$ in a unique way. In the literature either the collection $(S(x)^w:w\in A^*)$ or its linear extension $S(x)\colon w\mapsto S(x)^w\in H^*$ are known as the \emph{iterated-integral signature} of $x$.

Chen showed that the signature satisfies the so-called \emph{shuffle relations}, generalizing integration-by-parts to iterated integrals: for any $v,w\in H$,
\begin{equation}
  S(x)^{v\shuffle w}=S(x)^vS(x)^w.
  \label{eqn:shuffleSig}
\end{equation}
In other words, if we regard the map $S(x)$ as a formal word series $S(x)=\sum_{w\in A^*}S(x)^ww$, then it is a group-like element.
One could also say that $S(x)$ is a character over the shuffle algebra. In any case, its \emph{logarithm} $\Lambda(x)\coloneqq\log S(x)$ is well defined as an element of the free Lie algebra on $d$ generators.

In control theory, the coefficients of the signature actually provide a universal description of solutions to affinely controlled ODEs. For a fixed path $x\colon[0,1]\mapsto\mathbb R^d$ as before, and smooth vector fields $f_1,\dotsc,f_d$ on $\R^q$, consider the initial value problem
\begin{equation}
  \dot y(t)=\sum_{i=1}^df_i(y(t))\dot x^i(t),\quad y(0)=\xi\in\R^q.
\label{eqn:cODE}
\end{equation}
Using Picard iteration, the final value $y(1)$ can be expressed as a series:
\begin{equation}
  y(1)=\sum_{w\in A^*}f_w(\xi)S(x)^w
\label{eqn:picard}
\end{equation}
where the functions $f_w$ are defined recursively via the relation $f_e(y)=y$ and $f_{iw}(y)=Df_w(y)f_i(y).$ T.~Lyons' insight was, that this expansion generalizes to control systems with irregular (in particular: non-differentiable) drivers, in what is now known as \emph{rough paths theory} \cite{Lyons1998}. The main philosophy of the theory is that \cref{eqn:cODE} should be interpreted as an integral equation, and the iterated integrals appearing in \cref{eqn:picard}, which may not exist, should be replaced by an object --a geometric rough path-- satisfying properties similar to those of the signature, that has to be supplied as an input to the problem.

Numerical schemes for \cref{eqn:cODE} are obtained by integrating the equation over small interval of size $h>0$, so that for a fixed $t\in(0,1)$
\[
  y(t+h)-y(t)=\sum_{i=1}^d\int_t^{t+h}f_i(y(u))\dot x^i(u)\,\mathrm du=\sum_{i=1}^df_i(y(t))(x^i(t+h)-x^i(t))+\mathrm o(h).
\]
Setting $y_k\coloneqq y(kh)$ and $x_k\coloneqq x(kh)$ for $k=0,\dotsc,N$ we are led to consider the associated finite difference equation
\[
  y_{k+1}-y_k=\sum_{i=1}^df_i(y_k)(x^i_{k+1}-x^i_k).
\]
Similar to the continuous case, it can be shown that $y_N$ can be expressed as a series:
\[
  y_N=\sum_{w\in A^*}f_w(\xi)\S(x)^w
\]
where now the coefficient $\S(x)^w$ is defined using \emph{iterated sums} instead of integrals, that is, if $w=i_1\dotsm i_n$ then
\begin{equation}
  \S(x)^w\coloneqq\underset{0<k_1<\cdots <k_n<N}{\sum \dotsm \sum}\delta x_{k_1}^{i_1}\dotsm\delta x_{k_n}^{i_n}
  \label{eqn:issig}
\end{equation}
and we have defined increments $\delta x_j\coloneqq x_{j+1}-x_j$ for convenience. As before, we extend this definition linearly to $H$.

We observe that $\S(x)$ \emph{does not} satisfy the shuffle relations \eqref{eqn:shuffleSig}. For example,
\[
  \S(x)^{i\shuffle j}=\S(x)^{ij}+\S(x)^{ji}=\S(x)^i\S(x)^j-\sum_{0<k<N}\delta x_k^i\delta x_k^j.
\]
The last term on the right-hand side cannot be expressed as a linear combination of the coefficients in \cref{eqn:issig}. The correct way to describe the product rule satisfied by the iterated sums requires another product on words, generalizing the shuffle product, $\shuffle$, over a larger alphabet. This product is known as \emph{quasi-shuffle}. See, e.g.-\cite{Gaines1994,Hoffman2000}.

To describe the quasi-shuffle product, we first need to extend the alphabet $A$ to a commutative semigroup $\mathsf A$.
The internal law on $\mathsf A$, which is associative and commutative, will be denoted by using square brackets. By construction, every element of $\mathsf A$ can be written uniquely (up to commutativity) as an iteration of brackets
\[
  [i_1[i_2[\dotsm i_n]]]\coloneqq [i_1i_2\dotsm i_n],\quad i_1,\dotsc,i_n\in A
\]
where the definition on the right is consistent by associativity. We now denote by $\mathsf A^*$ the free monoid, with empty word $e$.
The linear space $\mathsf H$ spanned by $\mathsf A^*$ has an algebra structure through the quasi-shuffle product ${\star}\colon\mathsf H\otimes\mathsf H\to\mathsf H$, recursively defined by
\[
  e \star u = u \star e
  \quad \mathrm{and} \quad
  ua\star vb\coloneqq(u\star vb)a+(ua\star v)b+(u\star v)[ab]
\]
for $u,v\in\mathsf A^*$ and $a,b\in\mathsf A$.

We now extend the definition of $\S$ in \eqref{eqn:issig} to include letters from $\mathsf A$ by setting
\[
  \delta x^{[i_1\dotsm i_n]}_j\coloneqq\prod_{k=1}^n\delta x^{i_k}_j.
\]
With this notation, the previous example rewrites
\[
  \S(x)^{i\star j}=\S(x)^{ij+ji+[ij]}=\S(x)^i\S(x)^j.
\]

\begin{defn}[\cite{DET2019}]
The \emph{iterated-sums signature} of the discrete sequence $x=(x_0,\dotsc,x_N)$ is the collection $\S(x)\coloneqq(\S(x)^w:w\in\mathsf A)$ defined by \cref{eqn:issig}.
\end{defn}

As before, we will not distinguish between the collection $\S(x)$ and its unique linear extension to $\mathsf H$.

\begin{thm}[\cite{DET2019}]\label{thm:qshomo}
The iterated-sums signature satisfies the \emph{quasi-shuffle relations} 
\[
\S(x)^{v\star w}=\S(x)^{v}\S(x)^w,
\] 
for all $v,w\in\mathsf H$.
\end{thm}

Using strict inequalities in \eqref{eqn:issig} seems to be arbitrary. In fact, another signature is defined as follows
\begin{align*}
  \S_{-1}(x)^w := \sum_{0 < k_1 \le k_2 \le \cdots \le k_{n-1} \le k_n \le N} \delta x^{i_1}_{k_1} \cdots \delta x^{i_n}_{k_n}.
\end{align*}
This is a character on another algebra. To formulate this we immediately introduce the general notation. On $\mathsf H$ define for $\theta \in \R$ the \emph{$\theta$-weight quasi-shuffle} $\star_{\scriptscriptstyle{\theta}}$ recursively as
\begin{align*}
  e \star_{\scriptscriptstyle{\theta}} w = w = w \star_{\scriptscriptstyle{\theta}} e \quad \mathrm{and} \quad
  wa \star_{\scriptscriptstyle{\theta}} vb
  =
  (w \star_{\scriptscriptstyle{\theta}} vb) a
  +
  (wa \star_{\scriptscriptstyle{\theta}} v) b
  +
  \theta (w \star_{\scriptscriptstyle{\theta}} v) [a b].
\end{align*}
For $\theta = 0$ this is the (classical) shuffle, for $\theta = 1$ this is the quasi-shuffle $\star = \star_{\scriptscriptstyle{1}}$ defined earlier, and we shall keep using the former symbol when convenient.
Now: $\S_{-1}(x)$ is a character on $(\mathsf H, \star_{\scriptscriptstyle{-1}})$. In the next Section, we will see how to translate between $\S_{-1}(x)$, $\S(x)$ and more general ``signatures''.

Regarding \cref{thm:qshomo}, we mention here that for the case $d=1$ there is an immediate interpretation in terms of quasisymmetric functions \cite{MalReu1995}, \cite{Luoto2013}. In the multidimensional case, Novelli and Thibon's quasisymmetric functions of level $d$ \cite{NovThi2004} are the right object.

Lastly, we briefly mention the connection to time series analysis:
in \cite{DET2019}, we set out to find polynomial
functions of a time series $x = (x_0, x_1, \dots, x_N) \in (\R^d)^{N+1}$
that are invariant to \emph{time warping}.
We skip the precise definition,
but morally these are functions that do not change when the time series
is run at a different speed.
It turns out for $d=1$ these are \emph{exactly}
the quasisymmetric functions in the variables $x_0, x_1, \dots, x_N, x_{N+1}, \dots$
where we extend the time series constantly as $x_n = x_N$ for $n > N$.
%
For $d \ge 2$ these invariants should correspond to ``$d$-dimensional quasisymmetric functions''.
These are Novelli--Thibon's quasisymmetric function of level $d$ \cite{NovThi2004}.
%
In all cases $d\ge 1$ the iterated-sums signature, introduced in \cite{DET2019}, stores these quasisymmetric
functions, evaluated on some time series, as the character on the quasi-shuffle Hopf algebra.
This signature can be seen as the (polynomial) \emph{feature map}
corresponding to the \emph{dynamic time warping (DTW)} distance \cite{Berndt1994},
a heavily used distance in the realm of time series analysis.


In the next section we will look at the algebras $(\mathsf H, \star_{\scriptscriptstyle{\theta}})$
and maps between them. In the last section we present some observations and
open questions.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{(Quasi)-shuffle morphisms}
\label{sec:hoffman}

The rather elegant algebraic description by Hoffman and Ihara of quasi-shuffle
homomorphisms \cite{Hoffman2000,HI2017} will be used now. We first recall their
notation.
For a power series $f$ in $t$, with zero constant coefficient,
$f(t) = \sum_{n=1}^\infty c_n t^n$, define the linear map $\Psi_f : H \to H $
$$
  w \mapsto \Psi_f(w)=\sum_{I = (i_1, \dots, i_m) \in C(\ell(w))} c_{i_1} \cdots c_{i_m} I[ w ].
$$
Here $C(n)$  is the set of all compositions of the integer $p$, i.e., tuples $(i_1, \dots, i_p)$ of positive integers such that
$i_1 + \dots + i_p = n$.
Given $I=(i_1,\dotsc,i_p) \in C(n)$ and a word $w=w_1\dotsm w_n
\in \mathsf A^*$ of length $\ell(w)=n>0$, we define a new word
$I[w]\in \mathsf A^*$ by \begin{equation*}
  I[w]\coloneqq[w_1\dotsm w_{i_1}][w_{i_1+1} \dotsm w_{i_1+i_2}]\dotsm
[w_{i_1+\dotsb+i_{p-1}+1}\dotsm w_n].  \end{equation*} Here (as well as later) we are using the suitable 
convention that $[a]:=a$ for all $a \in \mathsf A$.


In \cite{HI2017} an isomorphism from $(H, \star_{\scriptscriptstyle{+1}}) \to (H,\star_{\scriptscriptstyle{-1}})$ is given. We generalize this and let for $\theta \in \R$
$$
  f_\theta(t)
  := \frac{1}{\theta} (e^{\theta t} - 1)
  = \sum_{n \ge 1} \frac{\theta^{n-1}}{n!} t^n,
$$
where the last line makes also sense for $\theta=0$.
Define
$$
  f^{-1}_\theta(t)
  = \frac{1}{\theta} \log( 1 + \theta t ) \\
  = \sum_{n \ge 1} \frac{\theta^{n-1}}{n} t^n,
$$
which, again, makes also sense for $\theta = 0$.

\begin{lem}
$\exp_\theta: (H, \star_{\scriptscriptstyle{0}}) \to (H, \star_{\scriptscriptstyle{\theta}})$, $\exp_\theta := \Psi_{f_\theta}$, is a Hopf algebra isomorphism, with inverse $\log_\theta := \Psi_{f^{-1}_\theta}$.
\end{lem}

\newcommand{\Hoff}{E} % the map
\newcommand{\hoff}{e} % the power series
\begin{cor}
For $\theta, \theta' \in \R$, the map $\Hoff_{\theta \to \theta'} := \exp_{\theta'} \circ \log_{\theta}: (H, \star_{\scriptscriptstyle{\theta}} ) \to (H, \star_{\scriptscriptstyle{\theta'}})$, is a Hopf isomorphism and $\Hoff_{\theta \to \theta'} = \Psi_{\hoff_{\theta\to\theta'}}$, where
  \begin{align*}
    \hoff_{\theta\to\theta'}(t)
    &= \frac{1}{\theta'} ( e^{\frac{\theta'}{\theta} \log( 1 + \theta t) } - 1 ) \\
    &=
    t
    - \frac{\theta-\theta'}{2!} t^2
    + \frac{(\theta-\theta')(2\theta-\theta')}{3!} t^3
    - \frac{(\theta-\theta')(2\theta-\theta')(3\theta-\theta')}{4!} t^4 \\
    &\quad
    + \frac{(\theta-\theta')(2\theta-\theta')(3\theta-\theta')(4\theta-\theta')}{5!} t^5
    - \dots
  \end{align*}
\end{cor}

\begin{rem}
Using this map $E$ and starting from the character $\S(x)$ on $(H, \star_{\scriptscriptstyle{+1}})$ we can construct characters $\S_\theta(x)$ on $(H, \star_{\scriptscriptstyle{\theta}})$ by defining
$$
      \Big\langle w, \S_\theta(x) \Big\rangle
      :=
      \Big\langle \Hoff_{\theta \to 1} w, \S(x) \Big\rangle.
$$

  We note that $\S_{+1}(x) = \S(x)$ and one can show that
$$
  \Big\langle [a_1] \cdots [a_p], \S_{-1}(x) \Big\rangle
      =
      \sum_{0 \le i_1 \le \cdots \le i_p } \delta x^{[a_1]}_{i_1}  \cdots \delta x^{[a_p]}_{i_p}.
$$
In other words, $\S_{-1}(x)$ is defined like $\S(x)$ but with all strict inequalities (in the sum over timepoints) replaced by weak inequalities.

  We also note that $\S_0(x)$ is the iterated-integrals signature of the piecewise linear interpolation of the (infinite dimensional) time series $X^a$  indexed by $a = [1^{k_1} \cdots d^{k_d}] \in \mathsf A$ and given by
$$
    n \mapsto X^a_n = \sum_{j=1}^n \delta x_j^a = \sum_{j=1}^n (\delta x^{[1]}_j)^{k_1} \cdots (\delta x^{[d] }_j)^{k_d}.
$$
For $\theta \not\in \{ -1, 0, +1 \}$ we currently do not have a satisfying alternative characterization of $\S_\theta(x)$.
\end{rem}

\begin{ex}
$$
    \hoff_{1/2 \to 1}(t)
    =
    ( e^{2 \log(1+t/2)} - 1)
    =
    ( (1+t/2)^{2} - 1 )
    =
    t + \frac{1}{4} t^2.
$$

  We get for example $\langle [1], \S_{1/2}(x) \rangle = \langle [1], \S(x) \rangle$ and
$$
    \Big\langle [1][1], \S_{1/2}(x) \Big\rangle = \Big\langle [1][1] + \frac{1}{4} [1^2], \S(x) \Big\rangle
    \quad
    \Big\langle [1^2], \S_{1/2}(x) \Big\rangle = \Big\langle [1^2], \S(x) \Big\rangle,
$$
  and hence
  \begin{align*}
    \Big\langle [1], \S_{1/2}(x) \Big\rangle^2
    &=
    \Big\langle [1], \S(x) \Big\rangle^2
    =
    \Big\langle [1] \star_{\scriptscriptstyle{1}} [1], \S(x) \Big\rangle
    =
    \Big\langle 2 [1][1] + [1^2], \S(x) \Big\rangle \\
    &=
    \Big\langle 2 [1][1] + 1/2 [1^2], \S_{1/2}(x) \Big\rangle
    =
    \Big\langle [1] \star_{\scriptscriptstyle{1/2}} [1], \S_{1/2}(x) \Big\rangle,
  \end{align*}
  as expected.

  %{\color{orange} This is wrong. Why does it work?
  %\begin{align*}
  %  \hoff_{1/2 \to 1}(t)
  %  &=
  %  ( e^{\frac{1/2}{1} \log(1+t/2)} - 1) \\
  %  &=
  %  ( (1+t/2)^{1/2} - 1 ) \\
  %  &=
  %  \sum_{n\ge 1} \frac{(-1)^n (2n)!}{(1-2n)(n!)^2 (8^n)} t^n \\
  %  &=
  %  \frac{1}{4} t - \frac{1}{32} t^2 + \frac{1}{128} t^3 - \dots
  %\end{align*}

  %We get for example
  %\begin{align*}
  %  \Big\langle [1], \S_{1/2}(x) \Big\rangle &= \Big\langle \frac{1}{4} [1], \S(x) \Big\rangle \\
  %  \Big\langle [1][1], \S_{1/2}(x) \Big\rangle &= \Big\langle \frac{1}{16} [1][1] -\frac{1}{32} [1^2], \S(x) \Big\rangle \\
  %  \Big\langle [1^2], \S_{1/2}(x) \Big\rangle &= \Big\langle \frac{1}{4} [1^2], \S(x) \Big\rangle,
  %\end{align*}
  %and hence
  %\begin{align*}
  %  \Big\langle [1], \S_{1/2}(x) \Big\rangle^2
  %  &=
  %  \Big\langle \frac{1}{4} [1], \S(x) \Big\rangle^2 \\
  %  &=
  %  \Big\langle \frac{1}{16} [1] \star_1 [1], \S(x) \Big\rangle \\
  %  &=
  %  \Big\langle 2/16 [1][1] + 1/16 [1^2], \S(x) \Big\rangle \\
  %  &=
  %  \Big\langle 2 [1][1] + 1/2 [1^2], \S_{1/2}(x) \Big\rangle \\
  %  &=
  %  \Big\langle [1] *_{1/2} [1], \S_{1/2}(x) \Big\rangle. \checkmark
  %\end{align*}}
\end{ex}

We finally note that these different concepts of summation / integration
appear naturally in the field of \emph{stochastic analysis}.
Stochastic integration theory starts from Riemann-type sums over stochastic processes\footnote{We recall that a stochastic process is a collection of random variables $(X_t:t\in[0,1])$ \cite{RY1999}.} $X,Y$, namely
\[
  I(X,Y)=\int_0^1X\,\mathrm dY\approx\sum_{i=0}^nX_{t_i}(Y_{t+i}-Y_{t_i}).
\]
The approximation here is in a probabilistic sense, meaning that the limiting procedure should also take into account the stochastic nature of the setting. Due to the particular analytic properties of these processes, the choice of the evaluation point $t_i$ in the above discrete approximation is a subtle matter. In a nutshell, different choices of this value lead to very different notions
of stochastic integrals.
The choices $X_{t_i}$, $X_{t_{i+1}}$ and $\tfrac12(X_{t_i}+X_{t_{i+1}})$ corresponds to the main three stochastic integrals, i.e. It\=o, backward It\=o and Stratonovich, respectively.
Each of these integrals has its own integration by parts rule, and they are tightly related analytically, as well as algebraically. Quasi-shuffles enter the picture when one considers these integrals at the level of the discrete approximations, since the multiplication of iterated sums follows summation-by-parts.
For example, for It\=o integration,
\begin{align*}
  \lefteqn{(X_1-X_0)(Y_1-Y_0)=\big( \sum_i(X_{t_{i+1}}-X_{t_i}) \big)\big( \sum_j(Y_{t_{j+1}}-Y_{t_j}) \big)}\\
  &= \sum_{i<j}(X_{t_{i}}-X_0)(Y_{t_{j+1}}-Y_{t_j})+\sum_{j<i}(Y_{t_j}-Y_0)(X_{t_{i+1}}-X_{t_i})+\sum_{i}(X_{t_{i+1}}-X_{t_i})(Y_{t_{i+1}}-Y_{t_i})\\
  &\approx \int_0^1(X_t-X_0)\,\mathrm dY_t+\int_0^1(Y_t-Y_0)\,\mathrm dX_t+\langle X,Y\rangle_t\qquad\text{(It\=o)}\\
  &\approx \int_0^1(X_t-X_0)\circ\mathrm dY_t+\int_0^1(Y_t-Y_0)\circ\mathrm dX_t\qquad\text{(Stratonovich)}\\
  &\approx \int_0^1(X_t-X_0)\,\hat{\mathrm d}Y_t+\int_0^1(Y_t-Y_0)\,\hat{\mathrm d}X_t-\langle X,Y\rangle_t\qquad\text{(backward It\=o)}
\end{align*}
The term $\langle X, Y \rangle$, known as stochastic \emph{bracket}, is an
artifact of the diagonal term that appears when multiplying iterated sums.
%which leads to the different nature of the It\=o integral.

%{\color{green}
%We slightly generalize this framework by introducing a quasi-shuffle product of weight $\theta\in[-1,1]$, where the aforementioned stochastic integrals correspond to the cases $\theta=1$, $\theta=0$ and $\theta=-1$, respectively.
%We then study weighted Riemann sums of the form
%\[ \sum_i(\lambda X_{t_i}+(1-\lambda)X_{t_{i+1}})(Y_{t_{i+1}}-Y_{t_i}) \]
%for $\lambda := \frac12 \theta + \frac12 \in[0,1]$.
%%In summary, this can be described through a parameter $\theta\coloneqq(2\lambda-1)\in[-1,1]$ for which
%This leads to a stochastic integral satisfying
%\[ (X_1-X_0)(Y_1-Y_0)=\int_0^1(X_t-X_0)\,\mathrm d_\theta Y_t+\int_0^1(Y_t-Y_0)\,\mathrm d_\theta X_t+\theta\langle X,Y\rangle_t. \]
%
%The true motivation for our work comes from time-series analysis and the study of what can be called a discrete analogue of the well-known Chen iterated-integrals signature \cite{Chen1954}.
%We introduce isomorphisms between the $\theta$-quasi-shuffle algebras:
%\begin{align*}
%  \exp_\theta&\coloneqq\Psi_{\frac1\theta(\exp({\theta t})-1)}\\
%  \log_\theta&\coloneqq\Psi_{\frac1\theta\log(1+t\theta)}=\exp_\theta^{-1}\\
%  T&\coloneqq\Psi_{-t}\\
%  \Sigma_\theta&\coloneqq\Psi_{\frac{t}{1-\theta t}}=\exp_\theta T\log_\theta T\\
%\end{align*}
%in the notation of Hoffman and Ihara \cite{HI2017}, where, for a power series $f=c_1t+c_2t^2+\dotsb$
%\[ \Psi_f(w)\coloneqq\sum_{I=(i_1,\dotsc,i_m)\in\mathcal C(\ell(w))}c_{i_1}\dotsm c_{i_m}I[w]. \]
%
%\begin{figure}[!ht]
%  \centering
%  \begin{tikzcd}
%    &(T(A),{*_\theta})\\
%    (T(A),{\shuffle})\urar["\exp_\theta"]&\\
%    &(T(A),{*_{-\theta}})\ular["T\log_\theta T"]\arrow[uu,"\Sigma_\theta"']
%  \end{tikzcd}
%  \caption{Isomorphisms between $\theta$-quasi-shuffle algebras}
%  \label{fig:iso}
%\end{figure}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Observations}
\label{sec:observations}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Expectation values of discrete signatures}
\label{secc:expectation}
\newcommand\E{\mathbb E}

We have seen that $\S(x)$ is a character over the quasi-shuffle Hopf algebra $(H,\star)$. That means it is an element in the group of algebra morphisms, $\tilde{G} \subset G$, where $G$ is the larger group of invertible linear maps sending the empty word to one. Both groups have corresponding Lie algebras, $\tilde{\mathfrak g} \subset \mathfrak g$, with $\tilde{\mathfrak g}$ containing the infinitesimal characters, whereas $\mathfrak g$ consists of linear maps that send the empty word to zero. It is clear that for any $\Phi \in \tilde{G}$ we can find a unique $\alpha \in \tilde{\mathfrak g}$, such that $\Phi=\exp^{\ostar}(\alpha)$. Analogously, the group $G$ is in bijection with $\mathfrak g$. Recall that the convolution product of linear maps
$$
  \alpha \ostar \beta := m_\field(\alpha \otimes \beta) \Delta
$$
is defined in terms of the deconcatenation coproduct on words
$$
  \Delta(w) = w \otimes e + e \otimes w + \sum_{i=1}^{n-1} w_1 \cdots w_i \otimes w_{i+1} \cdots w_n.
$$

Let $x$ be a random sequence, i.e. it has random variables as entries and hence $\S(x)$ is itself a random variable.
The expectation of the iterated-sums signature is defined as the liner map given by
\[
  \mu_x^w \coloneqq \E[\S(x)^w] = \E\left[\ \underset{0<k_1<\cdots<k_n<N}{\sum\dotsm\sum} \delta x_{k_1}^{i_1}\dotsm\delta x_{k_n}^{i_n}\right]\in\mathbb R.
\]
Note that $\mu_x \in G$.
Hence
$$
  \kappa_x := \log^{\ostar}\mu_x
$$
is a well-defined linear map in the Lie algebra $\mathfrak g$, sending the empty word to zero. Defining $\mu'_x:= \mu_x  - \epsilon$, where $\epsilon$ is the counit in $(H,\star)$, we have
\allowdisplaybreaks
\begin{align*}
  \kappa_x
&=-\sum_{n>0} \frac{(-1)^n}{n}(\mu'_x)^{{\ostar}n}\\
&=\mu'_x - \frac{1}{2} (\mu'_x)^{{\ostar} 2}  + \frac{1}{3} (\mu'_x)^{{\ostar} 3}   - \frac{1}{4} (\mu'_x)^{{\ostar} 4}+ \cdots.
\end{align*}
It is then easy to see that for any word
$$
  \mu_x^w=\sum^{|w|}_{m>0} \frac{1}{m!}\sum_{v_1 \cdots v_m=w}
  \kappa^{v_1}_x \cdots \kappa^{v_m}_x
$$
and
$$
  \kappa^{w}_x=-\sum^{|w|}_{m>0} \frac{(-1)^m}{m}\sum_{v_1 \cdots v_m=w \atop v_i \neq \mathbf{1}}
  \mu_x^{v_1} \cdots \mu_x^{v_m}.
$$
Following the terminology for random variables in probability theory and call $\kappa_x$ the \emph{cumulant map} and $\mu_x$ the \emph{moment map}. Motivated by \cite{BonOber2019}, which compute so-called signature moments and cumulants, we address the more interesting problem of calculating expressions like $\kappa_x^{[1][2] \star [3]}$ without expanding the quasi-shuffle product.
\begin{align*}
  \lefteqn{\kappa_x^{[1][2] \star [3]}
  = -\sum_{n>0} \frac{(-1)^n}{n}(\mu_x')^{{\ostar}n}([1][2] \star [3])}\\
  &=\mu_x^{[1][2] \star [3]}
      - \mu_x^{[1][2]}\mu_x^{[3]}-\frac{1}{2} \mu_x^{[1] \star [3]}\mu_x^{[2]}
        -\frac{1}{2} \mu_x^{[1]}\mu_x^{[2] \star [3]}\\
  &\quad + \frac{1}{3} (\mu_x' \otimes \mu_x' \otimes \mu_x') (\Delta \otimes \mathrm{id})\Delta([1][2] \star [3])\\
  &=\E\left[ \S(x)^{[1][2]}\S(x)^{[3]} \right]
  - \E\left[ \S(x)^{[1][2]}\right] \E\left[ \S(x)^{[3]} \right]\\
  &\quad    -\frac{1}{2}\E\left[ \S(x)^{[1]}\S(x)^{[3]}\right] \E\left[ \S(x)^{[2]} \right]
  -\frac{1}{2}\E\left[ \S(x)^{[1]} \right] \E\left[ \S(x)^{[2]}\S(x)^{[3]} \right]\\
  &\quad    +\E\left[ \S(x)^{[1]} \right] \E\left[ \S(x)^{[2]} \right] \E\left[ \S(x)^{[3]} \right].
\end{align*}
Here we used the fact that $\S(x)$ is an algebra morphism for the quasi-shuffle product $\star$. Using that $\kappa_x^{\mathbf{1}}=0$, we can invert this expansion and express $\mu_x$ in terms of $\kappa_x$
\begin{align*}
  \mu_x^{[1][2] \star [3]}
  &=\kappa_x^{[1][2] \star [3]}
      + \kappa_x^{[1][2]} \kappa_x^{[3]}
      + \frac{1}{2} \kappa_x^{[1] \star [3]} \kappa_x^{[2]}
      + \frac{1}{2} \kappa_x^{[1]} \kappa_x^{[2] \star [3]}
      + \frac{1}{2} \kappa_x^{[1]} \kappa_x^{[2]} \kappa_x^{[3]}.
\end{align*}

The general formula for expressing cumulants and moments, $\kappa_x$ resp.~$\mu_x$, in terms of each other is obtained by recalling the Hopf algebra isomorphism $F$ from the Hopf subalgebra of rooted ladder trees with decorations in the Butcher--Connes--Kreimer Hopf algebra of rooted trees to the quasi-shuffle Hopf algebra $(H,\star)$. Quasi-shuffle products of words are identified with forests of decorated ladder trees. Hence, iterated (reduced) deconcatenation coproducts on ${w_1 \star \cdots \star w_n}$ can be computed in terms of iterated (reduced) coproducts on forests of ladders. For the above example we obtain
$$
  F([1][2] \star [3])=F([1][2] )F([3])=\Forest{[1[2]]}\Forest{[3]}
$$
and compute the reduced Connes--Kreimer coproduct $\Delta'_{\scriptscriptstyle{\mathrm{CK}}}$ on the forest of two ladders
$$
  \Delta'_{\scriptscriptstyle{\mathrm{CK}}}\Forest{[1[2]]}\Forest{[3]}
  = \Forest{[1[2]]} \otimes \Forest{[3]}
    + \Forest{[3]} \otimes \Forest{[1[2]]}
    + \Forest{[2]]} \otimes \Forest{[1]}\Forest{[3]}
    + \Forest{[2]]}\Forest{[3]} \otimes \Forest{[1]}.
$$
Here the root-part is on the right. The first iterated reduced coproduct
$$
  (\Delta'_{\scriptscriptstyle{\mathrm{CK}}} \otimes \mathrm{id})\Delta'_{\scriptscriptstyle{\mathrm{CK}}}\Forest{[1[2]]}\Forest{[3]}
  = \Forest{[2]]} \otimes \Forest{[1]} \otimes \Forest{[3]}
    + \Forest{[2]]} \otimes \Forest{[3]} \otimes \Forest{[1]}
    + \Forest{[3]]} \otimes \Forest{[2]} \otimes \Forest{[1]}.
$$
This should be compared with the expression for $\kappa_x^{[1][2] \star [3]}$. Hence, a product $w_1 \star \cdots \star w_n$ corresponds to a forest $F(w_1 \star \cdots \star w_n)=t_1 \cdots t_n$. We denote the degree of a forest, i.e., the total number of its vertices, by $|t_1 \cdots t_n|:=\sum_{i=1}^n|t_i|$, where $|t_i|$ corresponds to the number of letters of the word $w_i=F^{-1}(t_i)$. Defining $\tilde{\kappa}_x:=\kappa_x\circ F^{-1}$ and $\tilde\mu_x:=\mu_x\circ F^{-1}$, we find for
\begin{align*}
  \lefteqn{\kappa_x^{w_1 \star \cdots \star w_n}
  = \tilde{\kappa}_x(t_1 \cdots t_n)}\\
  &=-\sum_{m=1}^{|t_1 \cdots t_n|} \frac{(-1)^m}{m} \tilde\mu_x^{\otimes m}
  \Delta^{[m-1]}_{\scriptscriptstyle{\mathrm{CK}}}(t_1) \cdots \Delta^{[m-1]}_{\scriptscriptstyle{\mathrm{CK}}}(t_n)\\
  &=-\sum_{m=1}^{|t_1 \cdots t_n|} \frac{(-1)^m}{m} \sideset{}{'}\sum_{(t_1,\ldots, t_n)}
  \tilde{\mu}_x( t^{(1)}_1 \cdots t^{(1)}_n) \cdots  \tilde{\mu}_x(t^{(m)}_1 \cdots t^{(m)}_n)
  \end{align*}
  which equals
{\small
\[
\sum_{m=1}^{N} \frac{(-1)^{m-1}}{m} \sideset{}{'}\sum_{(w_1,\ldots, w_n)}
  \E\left[ \S(x)\big(w^{(1)}_1) \cdots \S(x)(w^{(1)}_n) \right] \cdots\E\left[\S(x)(w^{(m)}_1) \cdots \S(x)(w^{(m)}_n)\right],
  \]
 }
where $N:=|t_1 \cdots t_n|=|w_1 \star \cdots \star w_n|$ and the primed sums refer to the constraint that none of the forests
$t^{(i)}_1 \cdots t^{(i)}_n$ (words $w^{(i)}_1 \cdots w^{(i)}_n$), for $i=1,\ldots,m$, can be the empty word, i.e., $F^{-1}(t^{(i)}_1 \cdots t^{(i)}_n)\neq \mathbf{1}$. This sum can be expressed in terms of linearly ordered partitions constructed as follows.
\begin{align*}
  \kappa_x^{w_1 \star \cdots \star w_n}
  = \tilde{\kappa}_x(t_1 \cdots t_n)
  = -\sum_{m=1}^{|t_1 \cdots t_n|} \frac{(-1)^m}{m} \sum_{\pi \in OP_m} \tilde{\mu}_x'(t_{\pi_1}) \cdots\tilde{\mu}_x'(t_{\pi_m}).
\end{align*}
The second sum on the right-hand side of the second equality runs over ordered partition with $m$ blocks. The computation of the order $m$, $\pi:=\{\pi_1, \cdots,\pi_m\}$ and its blocks ${\pi_i}$ is summarized in the following algorithm. The first step consists in partitioning $I \cup J =[n]$ into subsets, where $I \neq \emptyset$ . Then consider the corresponding subsets of trees, $t_{I}=t_{i_{1}} \cdots t_{i_{p}}$ and $t_{J}=t_{j_{p+1}} \cdots t_{j_{n}}$. Apply to each tree in $t_I$ a single non-empty cut. This may include the full cut (below the root). This produces a tensor product of forests
$$
  t'_I \otimes t''_I,
$$
where $t'_I \neq \emptyset$. Next, define the set $\pi_1:=\{t_I'\}$. Then, define the forest $t''_{I}t_J$ and repeat the procedure to define successively the block $\pi_2$, $\pi_3$, up to $\pi_m$ for $1 \le m \le |t_1 \cdots t_n|$.

\begin{rem} 
The computations of iterated coproducts of forests can be represented by matrices. Each forest $t_{\lambda_1} \cdots t_{\lambda_n}$ determines a partition of order $n$ of the degree $N = \lambda_1 + \cdots + \lambda_n$, where $\lambda_i=|t_{\lambda_i}| > 0$. We denote it as the $1 \times n$ matrix $(\lambda_1, \ldots,\lambda_n)$. Now, to compute the $l$th order convolution product, we may construct certain matrices of size $l \times n$, where in column $q$ we put a weak composition of length $l$, $(c_{1q},\ldots,c_{lq})$, of $\lambda_q=c_{1q} + \cdots + c_{lq}$, $1 \le q \le n$, $c_{iq} \ge 0$, for $1 \le i \le l$
$$
	\Lambda_{ln}=
	\left(\begin{array}{ccc}
	c_{11} & \cdots & c_{1n} \\
	\vdots & \ddots  & \vdots \\
	c_{l1} & \cdots & c_{ln}
	\end{array}\right).
$$ 
These matrices are constraint as follows:
\begin{enumerate}
\item	\label{item1} The sum of the entries in each row must be bigger than zero, that is, for all $1 \le k \le l$ we must have $\sum_{p=1}^n c_{kp}>0$.
\item \label{item2}  For $1 \le p \le n$, we have $\sum_{r=1}^n c_{rp}=\lambda_{p}$. 
\end{enumerate}
Item (\ref{item1}) reflects the fact that $(\tilde\mu - \epsilon)(\mathbf{1})=0$. The $l$ order convolution product is of the form 
$$
	(\tilde\mu - \epsilon)\prod_{i=1}^n t_{c_{1i}} \otimes (\tilde\mu - \epsilon)\prod_{i=1}^n t_{c_{2i}} \otimes 
	 \cdots \otimes (\tilde\mu - \epsilon)\prod_{i=1}^n t_{c_{li}}. 
$$
Here, $t_{c_{ij}}$ is the ladder tree of size $|t_{c_{ij}}| = c_{ij}$. Hence, the composition $(c_{1q},\ldots,c_{lq})$ amounts to cutting the tree $t_{\lambda_q}$ into $l$ (possibly empty) trees  $t_{c_{iq}}$ of size $c_{iq}$, $1 \le i \le l$. Translated to words, we find for $[1][2] \star [3]$ 
$$
	\Lambda^{(1)}_{12}=
	\left(\begin{array}{cc} 
	[1][2]  & [3]
	\end{array}\right)
	\quad
	\Lambda^{(1)}_{22}=
	\left(\begin{array}{cc} 
	[1][2]  & 0\\
	0        & [3]
	\end{array}\right)
	\quad
	\Lambda^{(2)}_{22}=
	\left(\begin{array}{cc} 
	0       & [3]\\
	{[1][2]} &  0
	\end{array}\right)
$$
$$
	\Lambda^{(3)}_{22}=
	\left(\begin{array}{cc} 
	[1] & [3]\\
	{[2]} &  0
	\end{array}\right)
	\quad
	\Lambda^{(4)}_{22}=
	\left(\begin{array}{cc} 
	[1] & 0\\
	{[2]} &  [3]
	\end{array}\right)
$$
$$
	\Lambda^{(1)}_{32}=
	\left(\begin{array}{cc} 
	[1] & 0\\
	{[2]} &  0\\
	0 & [3]
	\end{array}\right)
	\quad
	\Lambda^{(2)}_{32}=
	\left(\begin{array}{cc} 
	[1] & 0\\
	0 & [3]\\
	{[2]} & 0
	\end{array}\right)
	\quad
	\Lambda^{(3)}_{32}=
	\left(\begin{array}{cc} 
	0 & [3]\\
	{[1]} & 0\\
	{[2]} & 0
	\end{array}\right).
$$
Correspondingly, we have the iterated reduced coproducts:
$$
	[1][2] \star [3] 
	+ [1][2] \otimes [3] + [3] \otimes [1][2] + [1] \star [3] \otimes [2] + [1] \otimes[2]  \star [3]
	+ 3  [1] \otimes [2] \otimes [3]
$$
\end{rem}


\subsection{Chow's theorem}
\label{secc:chow}

Recall the ``classical'' Chow theorem for the iterated-integrals signature
\begin{thm}[{\cite[Theorem 7.28]{FrizVic2010}}]
  Every (finite dimensional projection of) a grouplike element (of the unshuffle coalgebra)
  can be realized as (the finite dimensional projection of) the iterated-integral signature
  of some piecewise smooth path $X$.
\end{thm}

Heuristically: ``iterated-integral signatures fill the entire group'' or respectively,
``the logarithms of iterated-integral signatures fill the entire Lie algebra''.
%
It turns out that something analogous is \emph{not} true for the iterated-sums signature.
Indeed, let $x = (x_0, x_, \dots, x_N) \in \R^{N+1}$ then one can calculate
\begin{align*}
  \langle [1^2], \log \S(x) \rangle
  = \sum_j (\delta x_j)^2 \ge 0.
\end{align*}
Therefore, the image of the logarithm of iterated-sums signatures
only reaches a certain subset of the Lie algebra.
This raises several questions
\begin{itemize}
  \item Does the problem persist if $x \in \C^{N+1}$? (The above problem evaporates
    in this setting, since $\sum_j (\delta x_j)^2$ can then reach any complex number.)

  \item In the real case: how to describe the subset of the Lie algebra that can be reached?

  \item Are there any implications, if any, to time series analysis?
\end{itemize}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
