By comparing these multinomial distributions with concentration inequalities, we can get $H_1 > H_j$ if $j > 1$ with high probability.
Before formally proving it in Lemma <ref>,
we introduce the Chernoff inequality to show the concentration of these random variables.

The Chernoff inequality: Let $X_1,X_2,...,X_n$ be independent Bernoulli random variables. Denote $X = \sum_{i=1}^n X_i$ with $\mu=E[X]$.
For all $0<\delta<1$, we have that $\PR \left(X<(1-\delta)\mu\right)<\exp(-\frac{\mu \delta^2}{2})$.

Applying the Chernoff inequality to the Binomial random variables
$n^j \sim B(T,1/2)$ for $1 \leq j \leq N$, we have

\begin{equation}
\label{n^j bound}
\PR\left(\left|n^j-\frac{1}{2}T\right|>\frac{\delta}{2}T\right) < 2\exp\bigg(-\frac{\delta^2 T}{4}\bigg)
\end{equation}

Now we are ready to bound the probabilities for the empirical Gini indices.
Since $\PR(G_j < G_1), j \geq 3$ are much smaller than $\PR(G_2 < G_1)$, we separately consider these two probabilities in the following lemma to get a better bound.

The probability that first cut is not on product one is at most

We first bound the probability that $H_1$ is small compared to its limit when $T$ is sufficiently large.
By (<ref>), because $n^1_1=n^1$ and $n^1_k=0$ for $k\ge 2$, we can rewrite $H_1$ as
$H_1 = n^1+\frac{\sum_{k=2}^{N+1} (n_k^{-1})^2}{T-n^1}$.
The concentration of the first term $n^1$ follows from (<ref>).
Conditional on $n^1$, $n_2^{-1} \sim B(T-{n}^1,1/2)$ and $n_3^{-1} \sim B(T-{n}^1,1/4)$. Define $\delta_1\triangleq\delta/\sqrt{1-\delta}$. By the Chernoff inequality we have:

\begin{align*}
&\PR\left((n_2^{-1})^2<\frac{1}{4} (1-\sqrt{2} \delta_1)^2 (T-n^1)^2 \bigg|n^1\right)\\
=&\PR\left(n_2^{-1}<\frac{1}{2} (1-\sqrt{2} \delta_1) (T-n^1)\bigg|n^1\right)
&\PR\left((n_3^{-1})^2<\frac{1}{16} (1-2 \delta_1)^2 (T-n^1)^2\bigg|n^1\right)\\
=&\PR\left(n_3^{-1}<\frac{1}{4} (1-2 \delta_1) (T-n^1)\bigg|n^1\right)
\end{align*}

Since $(n_k^{-1})^2\ge 0$, we can bound the probability of the sum $\sum_{k=2}^{N+1} (n_k^{-1})^2$ in the following way:

\begin{align*}
&\PR\left(\sum_{k=2}^{N+1} (n_k^{-1})^2<\left[\frac{1}{4} (1-\sqrt{2}\delta_1)^2+\frac{1}{16}(1-2\delta_1)^2\right](T-n^1)^2\bigg|n^1\right)\nonumber\\
<\,&\PR\left((n_2^{-1})^2+(n_3^{-1})^2<\left[\frac{1}{4} (1-\sqrt{2}\delta_1)^2+\frac{1}{16}(1-2\delta_1)^2\right](T-n^1)^2\bigg|n^1\right)\nonumber\\
<\,&\PR\left((n_2^{-1})^2<\frac{1}{4} (1-\sqrt{2} \delta_1)^2 (T-n^1)^2\bigg|n^1\right)
+\PR\left((n_3^{-1})^2<\frac{1}{16} (1-2 \delta_1)^2 (T-n^1)^2\bigg|n^1\right)\nonumber\\
\end{align*}

Therefore, conditional on $n^1$, we can bound $H_1$ as below

\begin{align}
\label{H_1|n_1}
&\PR\left(H_1<n^1+\left[\frac{1}{4} (1-\sqrt{2}\delta_1)^2+\frac{1}{16}(1-2\delta_1)^2\right](T-n^1)\bigg|n^1\right)\nonumber\\
=\,&\PR\left(\sum_{k=2}^{N+1} (n_k^{-1})^2<\left[\frac{1}{4} (1-\sqrt{2}\delta_1)^2+\frac{1}{16}(1-2\delta_1)^2\right](T-n^1)^2\bigg|n^1\right)\nonumber\\
\end{align}

Combined with (<ref>) when $j=1$, we can bound the unconditional probability:

\begin{align}
\label{H_1}
&\PR\left(H_1<\frac{(1-\delta)T}{2}+\left[\frac{1}{4} (1-\sqrt{2}\delta_1)^2+\frac{1}{16}(1-2\delta_1)^2\right]\frac{(1+\delta)T}{2}\right)\nonumber\\
&+\sum_{k:|k-T/2|<\delta T/2}\PR(n^1=k)\PR\left(H_1<\frac{(1-\delta)T}{2}+\left[\frac{1}{4} (1-\sqrt{2}\delta_1)^2+\frac{1}{16}(1-2\delta_1)^2\right]\frac{(1+\delta)T}{2}\bigg|n^1=k\right)\nonumber\\
<\,&2\exp\bigg(-\frac{\delta^2 T}{4}\bigg)+\sum_{k:|k-T/2|<\delta T/2}\PR(n^1=k)\times 2\exp\bigg(-\frac{\delta_1^2(T-k)}{2}\bigg)\nonumber\\
<\,&2\exp\bigg(-\frac{\delta^2 T}{4}\bigg)+2\exp\bigg(-\frac{\delta_1^2(1-\delta)T}{4}\bigg)
=4\exp\bigg(-\frac{\delta^2 T}{4}\bigg).
\end{align}

This establishes the bound for the probability that $H_1$ would be too large.

Next we bound the probability that $H_2$ is large compared to its mean.
Recall from (<ref>) that

\begin{equation}
\label{H_2 formulation}
H_2 = \frac{(n_1^2)^2+(n_2^2)^2}{n^2}+\frac{(n_1^{-2})^2 +\sum_{k=3}^{N+1} (n_k^{-2})^2}{T-n^2}
\end{equation}

For the first term in (<ref>), conditional on $n^2$, both $n_1^2$ and $n_2^2={n}^2-n_1^2$ follows $B({n}^2,1/2)$.
Therefore, by the Chernoff bound, we have

\begin{equation*}
\PR \left(\left|n_1^2-\frac{1}{2}n^2\right|>\frac{\sqrt{2}}{2}\delta_1 n^2\bigg|n^2\right)
<2\exp\left(-\frac{\delta_1^2 {n}^2}{2}\right)
\end{equation*}

Moreover, we have

\begin{align}
\label{H_2_1}
&\PR \left((n_1^2)^2+(n^2-n_1^2)^2>\frac{1}{2}(1+2\delta_1^2)(n^2)^2\bigg|n^2\right)\nonumber\\
=\,&\PR \left(\frac{1}{2} (n^2)^2 +2(n_1^2-\frac{1}{2} n^2)^2>\frac{1}{2}(1+2\delta_1^2)(n^2)^2\bigg|n^2\right)\nonumber\\
=\,&\PR \left(\left|n_1^2-\frac{1}{2}n^2\right|>\frac{\sqrt{2}}{2}\delta_1 n^2\bigg|n^2\right)
<\,2\exp\left(-\frac{\delta_1^2 {n}^2}{2}\right).
\end{align}

where the first equality above follows from $(n_1^2)^2+(n^2-n_1^2)^2=\frac{1}{2} (n^2)^2 +2(n_1^2-\frac{1}{2} n^2)^2$.

For the second term in (<ref>), conditional on $n^2$, we have $n_1^{-2} \sim B(T-{n}^2,1/2)$, $T-{n}^2-n_1^{-2} \sim B(T-{n}^2,1/2)$, $n_3^{-2} \sim B(T-{n}^2,1/4)$ and $T-{n}^2-n_1^{-2}-n_3^{-2} \sim B(T-{n}^2,1/4)$.
By the Chernoff bound we have:

\begin{align*}
\PR \left(n_3^{-2}<\frac{1}{4}(1-2\delta_1)(T-n^2)\bigg|n^2\right)&<\exp\left(-\frac{\delta_1^2(T-{n}^2)}{2}\right)\\
\PR \left(T-{n}^2-n_1^{-2}-n_3^{-2}<\frac{1}{4}(1-2\delta_1)(T-n^2)\bigg|n^2\right)&<\exp\left(-\frac{\delta_1^2(T-{n}^2)}{2}\right)
\end{align*}

From the above two equations we have

\begin{equation*}
\PR \left(n_3^{-2}(T-{n}^2-n_1^{-2}-n_3^{-2})<\frac{1}{16}(1-2\delta_1)^2(T-n^2)^2\bigg|n^2\right)<2\exp\left(-\frac{\delta_1^2(T-{n}^2)}{2}\right)
\end{equation*}

Similar to (<ref>) we also have

\begin{equation*}
\PR \left((n_1^{-2})^2+(T-n^2-n_1^{-2})^2>\frac{1}{2}(1+2\delta_1^2)(T-n^2)^2\bigg|n^2\right)<2\exp\left(-\frac{\delta_1^2 (T-{n}^2)}{2}\right)
\end{equation*}

Combining the above two inequalities we have

\begin{align}
\label{H_2_2}
&\PR \left((n_1^{-2})^2+(n_3^{-2})^2+\sum_{k=4}^{N+1} (n_k^{-2})^2>\left[\frac{1}{2}(1+2\delta_1^2)-\frac{1}{8}(1-2\delta_1)^2\right](T-n^2)^2\bigg|n^2\right)\nonumber\\
<\,&\PR \left((n_1^{-2})^2+(n_3^{-2})^2+(T-n^2-n_1^{-2}-n_3^{-2})^2>\left[\frac{1}{2}(1+2\delta_1^2)-\frac{1}{8}(1-2\delta_1)^2\right](T-n^2)^2\bigg|n^2\right)\nonumber\\
=\,&\PR \left((n_1^{-2})^2+(T-n^2-n_1^{-2})^2-2n_3^{-2}(T-n^2-n_1^{-2}-n_3^{-2})>\left[\frac{1}{2}(1+2\delta_1^2)-\frac{1}{8}(1-2\delta_1)^2\right](T-n^2)^2\bigg|n^2\right)\nonumber\\
<\,&\PR \left((n_1^{-2})^2+(T-n^2-n_1^{-2})^2>\frac{1}{2}(1+2\delta_1^2)(T-n^2)^2\bigg|n^2\right)\nonumber\\
&+\PR \left(n_3^{-2}(T-{n}^2-n_1^{-2}-n_3^{-2})<\frac{1}{16}(1-2\delta_1)^2(T-n^2)^2\bigg|n^2\right)\nonumber\\
\end{align}

The first inequality follows from $\sum_{k=4}^{N+1} n_k^{-2} = T-n^2-n_1^{-2}-n_3^{-2}$ and thus $\sum_{k=4}^{N+1} (n_k^{-2})^2 \leq (T-n^2-n_1^{-2}-n_3^{-2})^2$. The first equality follows from $(n_3^{-2})^2+(T-n^2-n_1^{-2}-n_3^{-2})^2=(T-n^2-n_1^{-2})^2-2n_3^{-2}(T-n^2-n_1^{-2}-n_3^{-2})$.

Combine (<ref>) and (<ref>) we have

\begin{align}
\label{H_2|n_2}
&\PR \left(H_2>\frac{1}{2}(1+2\delta_1^2)T-\frac{1}{8}(1-2\delta_1)^2(T-n^2)\bigg|n^2\right)\nonumber\\
<\,&\PR \left( \frac{(n_1^2)^2+(n^2-n_1^2)^2}{n^2}>\frac{1}{2}(1+2\delta_1^2)n^2\bigg|n^2\right)\nonumber\\
&+\PR \left( \frac{(n_1^{-2})^2+(n_3^{-2})^2+\sum_{k=4}^{N+1} (n_k^{-2})^2}{T-n^2}>\left[\frac{1}{2}(1+2\delta_1^2)-\frac{1}{8}(1-2\delta_1)^2\right](T-n^2)\bigg|n^2\right)\nonumber\\
=\,&\PR \left((n_1^2)^2+(n^2-n_1^2)^2>\frac{1}{2}(1+2\delta_1^2)(n^2)^2\bigg|n^2\right)\nonumber\\
&+\PR \left((n_1^{-2})^2+(n_3^{-2})^2+\sum_{k=4}^{N+1} (n_k^{-2})^2>\left[\frac{1}{2}(1+2\delta_1^2)-\frac{1}{8}(1-2\delta_1)^2\right](T-n^2)^2\bigg|n^2\right)\nonumber\\
<\,&2\exp\left(-\frac{\delta_1^2 {n}^2}{2}\right)+4\exp\left(-\frac{\delta_1^2(T-{n}^2)}{2}\right).
\end{align}

Next we bound the unconditional probability based on the conditional probability.
We have

\begin{align}
\label{H_2}
&\PR \left(H_2>\frac{1}{2}(1+2\delta_1^2)T-\frac{1}{8}(1-2\delta_1)^2\frac{(1-\delta)T}{2}\right)\nonumber\\
&+\sum_{k:|k-T/2|\le \delta T/2}\PR(n^2=k)\PR \left(H_2>\frac{1}{2}(1+2\delta_1^2)T-\frac{1}{8}(1-2\delta_1)^2\frac{(1-\delta)T}{2}\bigg|n^2=k\right)\nonumber\\
<\,&2\exp\bigg(-\frac{\delta^2 T}{4}\bigg)+\sum_{k:|k-T/2|\le \delta T/2}\PR(n^2=k)\left(2\exp\left(-\frac{\delta_1^2 k}{2}\right)+4\exp\left(-\frac{\delta_1^2(T-k)}{2}\right)\right) \nonumber\\
\le\,&2\exp\bigg(-\frac{\delta^2 T}{4}\bigg)+\sum_{k:|k-T/2|\le \delta T/2}\PR(n^2=k)\times 6\exp\left(-\frac{\delta_1^2 (1-\delta)T}{4}\right)\nonumber\\
=\,&2\exp\bigg(-\frac{\delta^2 T}{4}\bigg)+6\exp\bigg(-\frac{\delta_1^2(1-\delta) T}{4}\bigg)=\,8\exp\bigg(-\frac{\delta^2 T}{4}\bigg).
\end{align}

Next we choose a proper value for $\delta$.
By inequality (<ref>) and (<ref>), we want to find $\delta$ such that with high probability, we have

\begin{align*}
H_1&\ge \frac{(1-\delta)T}{2}+\left[\frac{1}{4} (1-\sqrt{2}\delta_1)^2+\frac{1}{16}(1-2\delta_1)^2\right]\frac{(1+\delta)T}{2}\\
&>\frac{1}{2}(1+2\delta_1^2)T-\frac{1}{8}(1-2\delta_1)^2\frac{(1-\delta)T}{2}\ge  H_2
\end{align*}

where $\delta_1=\delta/\sqrt{1-\delta}$.
We also have the constraint that $0<2\delta_1<1$, which is equivalent to $0<\delta<\frac{\sqrt{17}-1}{2} \approx 0.39$. Solving the above inequality for $0<\delta<0.39$ we have $0<\delta\le 0.166185$.
Let $\delta=0.166185$. Then $4/\delta^2 \approx 145$.
Plugging into (<ref>) and (<ref>), we have

\begin{align}
\PR\left(H_1<0.512041T\right)&<4\exp\left(-\frac{T}{145}\right)
\label{Prob_Small_H_1}
\\
\label{Prob_Large_H_2}
\PR\left(H_2>0.512041T\right)&<8\exp\left(-\frac{T}{145}\right)
\end{align}

\begin{align*}
\PR \left(H_1<H_2\right)<12\exp(- \frac{T}{145}).
\end{align*}

This implies that $G_1<G_2$ with high probability.
Notice that the probability bound in the above equation doesn't depend on $N$.
Next we consider $j \geq 3$. Recall that

\begin{equation}
\label{H_j formulation}
H_j = \frac{\sum_{k=1}^j (n_k^j)^2}{n^j}+\frac{\sum_{k=1}^{j-1} (n_k^{-j})^2 +\sum_{k=j+1}^{N+1} (n_k^{-j})^2}{T-n^j}
\end{equation}

Consider some $\delta_2>0$. From (<ref>) we have

\begin{equation}
\PR\left(\left|n^j-\frac{1}{2}T\right|>\frac{\delta_2}{2}T\right) < 2\exp\bigg(-\frac{\delta_2^2 T}{4}\bigg)
\end{equation}

We investigate the second term of (<ref>).
Conditional $n^j$, we have $n_1^{-j} \sim B(T-{n}^j,1/2)$, $T-{n}^j-n_1^{-j} \sim B(T-{n}^j,1/2)$, $n_2^{-j} \sim B(T-{n}^j,1/4)$ and $T-{n}^j-n_1^{-j}-n_2^{-j} \sim B(T-{n}^j,1/4)$. Define $\delta_3 \triangleq \delta_2/\sqrt{1-\delta_2}$. Then similar to (<ref>), we have

\begin{align}
\label{H_j_2}
&\PR \left((n_1^{-j})^2+(n_2^{-j})^2+\sum_{k=3}^{j-1} (n_k^{-j})^2 +\sum_{k=j+1}^{N+1} (n_k^{-j})^2>\left[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2\right](T-n^j)^2\bigg|n^j\right)\nonumber\\
<\,&\PR \left((n_1^{-j})^2+(n_2^{-j})^2+(T-n^j-n_1^{-j}-n_2^{-j})^2>\left[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2\right](T-n^j)^2\bigg|n^j\right)\nonumber\\
\end{align}

Then similarly we can bound the first term of (<ref>) since $n_1^{j} \sim B({n}^j,1/2)$, ${n}^j-n_1^{j} \sim B({n}^j,1/2)$, $n_2^{j} \sim B({n}^j,1/4)$ and ${n}^j-n_1^{j}-n_2^{j} \sim B(T-{n}^j,1/4)$.

\begin{align}
\label{H_j_1}
&\PR \left(\sum_{k=1}^j (n_k^j)^2>\left[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2\right](n^j)^2\bigg|n^j\right)\nonumber\\
<\,&\PR \left((n_1^j)^2+(n_2^j)^2+(n^j-n_1^j-n_2^j)^2>\left[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2\right](n^j)^2\bigg|n^j\right)\nonumber\\
\end{align}

Combining (<ref>) and (<ref>), we have

\begin{align}
\label{H_j|n_j}
&\PR \left(H_j>[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2]T\bigg|n^j\right)\nonumber\\
<\,&\PR \left(\sum_{k=1}^j (n_k^j)^2>[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2](n^j)^2\bigg|n^j\right)\nonumber\\
&+\PR \left(\sum_{k=1}^{j-1} (n_k^{-j})^2 +\sum_{k=j+1}^{N+1} (n_k^{-j})^2>[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2](T-n^j)^2\bigg|n^j\right)\nonumber\\
<\,&4\exp\left(-\frac{\delta_3^2 {n}^j}{2}\right)+4\exp\left(-\frac{\delta_3^2(T-{n}^j)}{2}\right)
\end{align}

Using a similar argument, we can bound the unconditional probability:

\begin{align}
\label{H_j}
\PR \left(H_j>[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2]T\right)
%	<\,&\PR\left(\left|n^j-\frac{1}{2}T\right|>\frac{\delta_2}{2}T\right)+\PR \left(H_j>[\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2]T\bigg|n^j=\tilde{n}^j,\left|\tilde{n}^j-\frac{1}{2}T\right|<\frac{\delta_2}{2}T\right)\nonumber\\
%	<\,&2\exp\bigg(-\frac{\delta_2^2 T}{4}\bigg)+8\exp\bigg(-\frac{\delta_2^2 T}{4}\bigg)\nonumber\\
<\,10\exp\bigg(-\frac{\delta_2^2 T}{4}\bigg).
\end{align}

Similarly we can calculate $\delta_2$.
By (<ref>) and (<ref>), we have the following condition for $\delta_2$

\begin{equation}
\frac{1}{2}(1+2\delta_3^2)-\frac{1}{8}(1-2\delta_3)^2<0.512041,
\end{equation}

where $\delta_3=\delta_2/\sqrt{1-\delta_2}$. Again when we consider $0<\delta_2<0.39$, the above inequality is equivalent to $0<\delta_2<0.200261$.
Let $\delta_2=0.200261$, then $4/\delta_2^2 \approx 99.74$, so we have for all $j \geq 3$

\begin{equation}
\label{Prob_Large_H_j}
\PR \left(H_j > 0.512041T \right)<10\exp\left(-\frac{T}{100}\right)
\end{equation}

Now note that

\begin{align}
\label{eq:first_split}
&\PR \left(\text{first split not on product one}\right)=\,\PR \left(G_1>\min\{G_j|2 \leq j\leq N\}\right)\nonumber\\
=\,&\PR \left(H_1<\max\{H_j|2 \leq j\leq N\}\right)
<\,\PR \left(H_1<0.512041T\right)+\sum_{j=2}^N \PR \left(H_j >0.512041T\right)\nonumber\\
<\,&4\exp\bigg(-\frac{\delta^2T}{4}\bigg)+8\exp\bigg(-\frac{\delta^2T}{4}\bigg)+(N-2)\times 10\exp\bigg(-\frac{\delta_2^2 T}{4}\bigg)\nonumber\\
\end{align}

This completes the proof of Lemma <ref>.

Next we are going to show that the probability of the second split on product two, third split on product 3 and so on, can be bounded similarly.
Let $\Tscr$ denote the training set.
Define a sequence of subsets of $\Tscr$ as follows: $\Tscr_i \triangleq \{S \in \Tscr| 1,2,...,i-1 \notin S\}$.
That is, $\Tscr_i$ only contains assortments that include a subset of $\{i,i+1,\dots,N\}$.
Let $T_i \triangleq |\Tscr_i|$ denote the cardinality of set $\Tscr_i$.
Notice that $\Tscr_1=\Tscr$ and $T_1=T$. for $2 \leq i \leq N$, since $T_i \sim B(T,1/2^{i-1})$, by the Chernoff inequality we have

\begin{equation}
\label{eq:T_i}
\PR \left(T_i<(1-\delta_0)\frac{1}{2^{i-1}}T\right)<\exp(-\frac{\delta_0^2 T}{2^i}),
\end{equation}

where $0<\delta_0<1$.

Define the event $A_i \triangleq \{\text{product } i \text{ is the best split for training set } \Tscr_i\}$, and let $\bar{A}_i$ denote the complement of event $A_i$.
Then conditional on $T_i$, we can bound the probability of event $\bar{A}_i$ using (<ref>) (with only $N-i+1$ products):

\begin{equation}
\label{eq:A_i|T_i}
\PR \left(\bar{A}_i\right|T_i) < 12\exp\left(-\frac{T_i}{145}\right)+10(N-i-1)\exp\left(-\frac{T_i}{100}\right)
\end{equation}

The unconditional probability can be bounded by combining (<ref>) and (<ref>):

\begin{align}
\label{eq:A_i}
\PR \left(\bar{A}_i\right)<\,&\PR \left(T_i>(1-\delta_0)\frac{1}{2^{i-1}}T\right)+\sum_{k:k\le (1-\delta_0)T/2^{i-1}}\PR(T_i=k)\PR\left(\bar{A}_i|T_i=k\right)\nonumber\\
<\,&\exp(-\frac{\delta_0^2 T}{2^i})+\sum_{k:k<(1-\delta_0)T/2^{i-1}}\PR(T_i=k)\left(12\exp\left(-\frac{k}{145}\right)+10(N-i-1)\exp\left(-\frac{k}{100}\right)\right)\nonumber\\
\leq\,&\exp(-\frac{\delta_0^2 T}{2^i})+12\exp\left(-\frac{(1-\delta_0)T}{145\cdot 2^{i-1}}\right)+10(N-i-1)\exp\left(-\frac{(1-\delta_0)T}{100 \cdot 2^{i-1}}\right)
\end{align}

Solving the equation $\frac{\delta_0^2 T}{2^i}=\frac{(1-\delta_0)T}{145\cdot 2^{i-1}}$, we get $\delta_0 \approx 0.1107$. Then we have

\begin{equation*}
\PR \left(\bar{A}_i\right)\le13\exp\left(-\frac{T}{164\cdot 2^{i-1}}\right)+10(N-i-1)\exp\left(-\frac{T}{113 \cdot 2^{i-1}}\right)
\end{equation*}

If all the events $A_1, A_2, ..., A_m$ happen, we can get the right split for the first $m$ step.
That is, the first split is on product one, the second split is on product two, …, the $m$th split is on product $m$. We can bound the probability by the union bound:

\begin{align}
\PR \left(\cap_{i=1}^m A_i\right)=\,&1-\PR \left(\cup_{i=1}^m \bar{A}_i\right)\nonumber\\
\ge\,&1-\sum_{i=1}^m \PR(\bar{A}_i)\nonumber\\
\ge \,& 1-\sum_{i=1}^m \left[13\exp\left(-\frac{T}{164\cdot 2^{i-1}}\right)+10(N-i-1)\exp\left(-\frac{T}{113 \cdot 2^{i-1}}\right)\right]
\end{align}

If the first $m$ splits match the products, then the assortments including at least one product among $\left\{1,\dots,m\right\}$ can be correctly classified.
Therefore, with a probability at least $\PR \left(\cap_{i=1}^m A_i\right)$, we can correctly predicts the choices of more than $(1-1/2^m)2^N$ assortments
Given $\epsilon>0$, letting $m=\lceil \log_2 \frac{1}{\epsilon} \rceil$ completes the proof.

We need to show that the $b$th tree constructed by the algorithm of both link functions returns the same partition (in the sense that each region contains the same set of observations in the training data) of the predictor space $[0,1]^N$ and the same class labels in each region/leaf.
The class labels are guaranteed to be the same because we control the internal randomizer in Step <ref>.
To show the partitions are the same, it suffices to show that each split creates regions that are identical for the two link functions in the sense that the resulting regions contain the same set of observations.
We will use induction to prove this claim.

Before the construction of the $b$th tree, because the internal randomizers in Step <ref> are equalized, the root node $[0,1]^N$ for both link functions contains the same set of observations.
Now focusing on a leaf node in the middle of constructing the $b$th tree for both link functions.
We use $[l^{(j)}_1,u^{(j)}_1]\times\dots\times [l^{(j)}_N,u^{(j)}_N]\subset [0,1]^N$ to denote the region of the leaf node for link functions $j=1,2$.
By the inductive hypothesis, both regions contain the same set of observations.
Without loss of generality, we assume that the regions contain $\left\{g_1(\bm p_t)\right\}_{t=1}^{T_1}$ and $\left\{g_2(\bm p_t)\right\}_{t=1}^{T_1}$, respectively.
After Step <ref>, the same set of candidate splitting products are selected.
To show that Step <ref> results in the same split in the two regions, consider a given split product $m$ and split point $x^{j}$ for $j=1,2$.
If $[l^{(1)}_1,u^{(1)}_1]\times\dots[l^{(1)}_m, x^{(1)}]\times\dots\times [l^{(1)}_N,u^{(1)}_N]$ and $[l^{(2)}_1,u^{(2)}_1]\times\dots[l^{(2)}_m, x^{(2)}]\times\dots\times [l^{(2)}_N,u^{(2)}_N]$ contain the same set of observations, i.e., for $t=1,\dots,T_1$

\begin{align*}
&g_1(\bm p_t)\in [l^{(1)}_1,u^{(1)}_1]\times\dots[l^{(1)}_m, x^{(1)}]\times\dots\times [l^{(1)}_N,u^{(1)}_N]\\
\iff &g_2(\bm p_t)\in [l^{(2)}_1,u^{(2)}_1]\times\dots[l^{(2)}_m, x^{(2)}]\times\dots\times [l^{(2)}_N,u^{(2)}_N],
\end{align*}

then the Gini indices resulting from the splits are equal for the two link functions.
This is because the Gini index only depends on the class composition in a region instead of the locations of the input, and the splits above lead to the same class composition in the sub-regions.
This implies that in Step <ref>, both trees are going to find the optimal splits that lead to the same division of training data in the sub-regions.
By induction and the recursive nature of the tree construction, Algorithm <ref> outputs the same partition in the $b$th tree for both link functions, i.e., the training data is partitioned equally.
This completes the proof.

§ SAMPLE CODE

§ CHOICE OF HYPER-PARAMETERS

In this section, we conduct an extensive numerical study on the hyper-parameters of Algorithms <ref> to find the optimal choice and test the sensitivity.
The hyper-parameters investigated include the number of trees $B$,
the sub-sample size $z$, the number of products to split $m$, and the terminal leaf size $l$.
Note that in all the numerical studies in the paper, we use $B = 1000$, $z = T$, $m = \sqrt{N}$, and $l = 50$.
Such choice seems to be robust across all problem setups.

§.§ Rank-based DCM

In this section, we generate the data using the rank-based DCM with 10 customer types.
We consider $N \in \{10,30,50\}$ products.
We first generate the training data using the rank-based DCM, where the proportion/weight of 10 types follows a Dirichlet distribution.
For each type, the preference is a random permutation of $N$ products and the outside option.
The customer will choose the product (or the outside option) ranked the highest among the offered assortment.
If the outside option is ranked higher than all products in the assortment, then she leaves without purchase.
The training data consists of $\tilde{T} \in \{30, 150, 600\}$ periods.
In each period, we generate 10 transactions under a selected assortment, whose selection method is given shortly.
The total size of the training data is thus $T = 10 \tilde{T}$.
For $N=10$, we randomly and uniformly select an assortment from all $2^N-1$ assortments.
For $N =30$ and $50$, each product has a probability $1/6$ and $1/10$ respectively to be included in an assortment, so the average number of products in an assortment is always 5 for $N\in \left\{10, 30, 50\right\}$.
We make this choice to compare the RMSE (<ref>)
across different $N$, because for assortments of different sizes, their RMSE usually differ substantially.
However, since we cannot enumerate $2^{30}$ or $2^{50}$ assortments to compute the RMSE, we randomly sample 10,000 assortments as a test set $\mathcal{T}_{test}$ to approximate the RMSE:

\begin{equation}
\label{eq:RMSE_MC}
R M S E\left(\PR, \hat\PR\right)=\sqrt{\frac{\sum_{S \subseteq \mathcal{T}_{test}} \sum_{j \in S \cup\{0\}}\left(\PR(j , S)-\hat\PR(j , S)\right)^{2}}{\sum_{S \subseteq \mathcal{T}_{test}}(|S|+1)}}.
\end{equation}

We set $B = 1000, z = T, m = \sqrt{N}, l = 50$ as the default hyper-parameters.
We vary one of them to investigate the effect while fixing the other three.
When testing a combination of hyper-parameters, we generate 100 independent training datasets and compute the average and standard deviation of the RMSEs.
Table <ref> shows the average and standard deviation of RMSE for different $z$ when $B = 1000, m = \sqrt{N}, l = 50$.
Similarly, we test $m$ and $l$ in Tables <ref> and <ref>.
For the number of trees $B$, we report RMSEs and running time in Tables <ref> and <ref> respectively.
We can see that our default choice is among the best in all the cases.
From Tables <ref> and <ref> we can see that the performance is better when $B$ is large.
However, when $B \geq 1000$, the RMSEs are almost the same. But the running time grows linearly in $B$.
Therefore, choosing $B = 1000$ strikes a balance between the performance and computational efficiency.

$N$     $T$      $z = T/20$          $z = T/10$          $z=T/4$                      $z=T/2$                      $\bm {z=T}$

10      300      0.113 (0.017)     0.113 (0.017)     0.099 (0.013)     0.092 (0.012)              0.089 (0.012)

10      1500     0.092 (0.010)     0.078 (0.008)     0.066 (0.006)     0.060 (0.006)              0.057 (0.005)

10      6000     0.063 (0.005)     0.053 (0.005)     0.044 (0.005)     0.040 (0.004)     0.041 (0.004)

30      300      0.217 (0.027)     0.218 (0.027)     0.187 (0.021)     0.171 (0.017)              0.168 (0.017)

30      1500     0.161 (0.020)     0.137 (0.012)     0.124 (0.008)     0.117 (0.008)              0.114 (0.008)

30      6000     0.117 (0.009)     0.104 (0.007)     0.092 (0.007)     0.087 (0.007)              0.085 (0.008)

50      300      0.256 (0.030)     0.256 (0.030)     0.224 (0.023)     0.209 (0.020)              0.206 (0.020)

50      1500     0.188 (0.018)     0.155 (0.012)     0.143 (0.010)     0.140 (0.010)              0.139 (0.011)

50      6000     0.128 (0.008)     0.121 (0.006)     0.111 (0.007)     0.108 (0.008)              0.107 (0.009)

The average and standard deviation of RMSE using random forests with different sub-sample size $z$ when the training data is generated by the rank-based model.

$N$     $T$      $m = 1$                      $m = \log N$                  $\bm {m = \sqrt{N}}$     $m = N/2$           $m = N$

10      300      0.096 (0.013)              0.091 (0.012)              0.089 (0.012)     0.090 (0.013)     0.102 (0.017)

10      1500     0.071 (0.007)              0.061 (0.005)              0.057 (0.005)     0.059 (0.006)     0.068 (0.008)

10      6000     0.051 (0.005)              0.043 (0.003)              0.041 (0.004)     0.043 (0.005)     0.052 (0.006)

30      300      0.171 (0.020)              0.166 (0.017)     0.168 (0.017)              0.180 (0.021)     0.191 (0.024)

30      1500     0.131 (0.015)              0.116 (0.008)              0.114 (0.008)     0.129 (0.017)     0.140 (0.020)

30      6000     0.109 (0.012)              0.088 (0.006)              0.085 (0.008)     0.096 (0.015)     0.104 (0.016)

50      300      0.200 (0.019)     0.201 (0.018)              0.206 (0.020)              0.222 (0.027)     0.230 (0.030)

50      1500     0.155 (0.016)              0.139 (0.009)     0.139 (0.011)              0.162 (0.021)     0.171 (0.021)

50      6000     0.127 (0.014)              0.108 (0.007)              0.107 (0.009)     0.126 (0.017)     0.134 (0.019)

The average and standard deviation of RMSE using random forests with different split  products $m$ when the training data is generated by the rank-based model.

$N$     $T$      $l = 1$             $l = 10$                     $\bm {l = 50}$                     $l = 100$                    $l = 200$

10      300      0.094 (0.011)     0.094 (0.011)              0.089 (0.012)     0.095 (0.013)     0.113 (0.017)

10      1500     0.073 (0.004)     0.071 (0.004)              0.057 (0.005)     0.061 (0.006)     0.068 (0.006)

10      6000     0.076 (0.004)     0.074 (0.004)              0.041 (0.004)     0.041 (0.005)     0.046 (0.005)

30      300      0.166 (0.017)     0.166 (0.017)     0.168 (0.017)              0.177 (0.018)     0.217 (0.027)

30      1500     0.114 (0.010)     0.114 (0.010)     0.114 (0.008)              0.121 (0.008)     0.131 (0.009)

30      6000     0.086 (0.008)     0.086 (0.008)              0.085 (0.008)     0.089 (0.008)     0.097 (0.007)

50      300      0.206 (0.021)     0.205 (0.021)     0.206 (0.019)              0.214 (0.020)     0.256 (0.030)

50      1500     0.139 (0.012)     0.139 (0.012)     0.139 (0.011)              0.145 (0.011)     0.153 (0.011)

50      6000     0.108 (0.010)     0.108 (0.009)              0.107 (0.009)     0.111 (0.009)     0.120 (0.008)

The average and standard deviation of RMSE using random forests with different leaf sizes $l$ when the training data is generated by the rank-based model.

$N$     $T$      $B = 10$            $B = 100$           $\bm {B = 1000}$          $B = 5000$          $B = 10000$

10      300      0.096 (0.014)     0.089 (0.012)     0.089 (0.012)     0.089 (0.012)     0.089 (0.012)

10      1500     0.066 (0.006)     0.058 (0.005)     0.057 (0.005)     0.057 (0.005)     0.057 (0.005)

10      6000     0.050 (0.004)     0.042 (0.004)     0.041 (0.004)     0.041 (0.004)     0.041 (0.004)

30      300      0.178 (0.018)     0.168 (0.017)     0.168 (0.017)     0.167 (0.017)     0.167 (0.017)

30      1500     0.128 (0.010)     0.115 (0.008)     0.114 (0.008)     0.114 (0.008)     0.114 (0.008)

30      6000     0.099 (0.009)     0.086 (0.008)     0.085 (0.008)     0.084 (0.008)     0.084 (0.008)

50      300      0.219 (0.022)     0.207 (0.020)     0.206 (0.020)     0.206 (0.020)     0.206 (0.020)

50      1500     0.154 (0.014)     0.141 (0.011)     0.139 (0.011)     0.139 (0.011)     0.139 (0.011)

50      6000     0.122 (0.011)     0.109 (0.009)     0.107 (0.009)     0.107 (0.009)     0.107 (0.009)

The average and standard deviation of RMSE using random forests with different numbers of trees $B$ when the training data is generated by the rank-based model.

$N$     $T$      $B = 10$            $B = 100$           $\bm {B = 1000}$          $B = 5000$          $B = 10000$

10      300      0.03         0.16          1.48           7.44           14.86

10      1500     0.03         0.19          1.76           8.71           17.47

10      6000     0.04         0.30          2.82           13.92          27.13

30      300      0.16         0.42          3.07           14.04          27.52

30      1500     0.18         0.50          3.85           17.24          32.92

30      6000     0.18         0.63          5.76           24.96          49.86

50      300      0.18         0.48          3.45           16.66          32.97

50      1500     0.19         0.56          4.69           20.52          40.89

50      6000     0.19         0.79          7.30           32.97          66.04

The running time (in seconds) of random forests with different numbers of trees $B$ when the training data is generated by the rank-based model.

§.§ The MNL Model

In this section, we generate the data using the MNL model, where the expected utility of each product and the outside option is drawn uniformly randomly from $[0,1]$.
Other settings are the same as Section <ref>.
The results are shown in Tables <ref> to <ref>.
We can see that except for $m$, our default choice is among the best in all the cases.
For $m$, the optimal choice seems to be less than $\sqrt{N}$.
Even in this case, using $m=\sqrt{N}$ is within one standard deviation away from the best choice.

$N$     $T$      $z = T/20$          $z = T/10$          $z=T/4$                      $z=T/2$                      $\bm {z=T}$

10      300      0.076 (0.014)     0.076 (0.014)     0.067 (0.013)              0.065 (0.011)     0.066 (0.010)

10      1500     0.058 (0.009)     0.050 (0.007)     0.045 (0.006)              0.045 (0.005)     0.047 (0.004)

10      6000     0.039 (0.005)     0.035 (0.004)     0.033 (0.002)     0.035 (0.002)              0.039 (0.001)

30      300      0.196 (0.017)     0.196 (0.017)     0.164 (0.015)              0.148 (0.013)              0.145 (0.013)

30      1500     0.140 (0.011)     0.114 (0.010)     0.102 (0.008)              0.098 (0.006)              0.097 (0.006)

30      6000     0.095 (0.007)     0.084 (0.006)     0.075 (0.004)              0.073 (0.003)     0.074 (0.003)

50      300      0.244 (0.015)     0.244 (0.014)     0.204 (0.013)              0.183 (0.012)              0.179 (0.012)

50      1500     0.170 (0.010)     0.133 (0.008)     0.121 (0.007)     0.122 (0.006)              0.124 (0.006)

50      6000     0.105 (0.008)     0.100 (0.007)     0.092 (0.005)              0.092 (0.004)     0.095 (0.003)

The average and standard deviation of RMSE using random forests with different sub-sample size $z$ when the training data is generated by the MNL model.

$N$     $T$      $m = 1$                      $m = \log N$                  $\bm {m = \sqrt{N}}$     $m = N/2$           $m = N$

10      300      0.061 (0.011)     0.063 (0.010)              0.066 (0.010)             0.071 (0.011)     0.079 (0.013)

10      1500     0.042 (0.005)     0.043 (0.004)              0.047 (0.004)             0.055 (0.005)     0.064 (0.006)

10      6000     0.034 (0.002)     0.035 (0.002)              0.039 (0.001)             0.047 (0.002)     0.055 (0.003)

30      300      0.138 (0.015)     0.141 (0.013)              0.145 (0.013)             0.156 (0.014)     0.162 (0.016)

30      1500     0.092 (0.010)              0.092 (0.007)     0.097 (0.006)             0.111 (0.007)     0.117 (0.008)

30      6000     0.068 (0.007)              0.067 (0.004)     0.074 (0.003)             0.089 (0.005)     0.093 (0.006)

50      300      0.171 (0.014)     0.174 (0.012)              0.179 (0.012)             0.189 (0.012)     0.194 (0.013)

50      1500     0.119 (0.011)              0.117 (0.008)     0.124 (0.006)             0.138 (0.008)     0.141 (0.009)

50      6000     0.088 (0.009)              0.085 (0.006)     0.095 (0.003)             0.110 (0.006)     0.113 (0.006)

The average and standard deviation of RMSE using random forests with different split products $m$ when the training data is generated by the MNL model.

$N$     $T$      $l = 1$             $l = 10$                     $\bm {l = 50}$                     $l = 100$                    $l = 200$

10      300      0.079 (0.007)     0.078 (0.007)              0.066 (0.010)     0.067 (0.012)              0.076 (0.015)

10      1500     0.072 (0.003)     0.070 (0.003)              0.047 (0.004)              0.047 (0.005)     0.049 (0.006)

10      6000     0.082 (0.002)     0.080 (0.002)              0.039 (0.001)              0.035 (0.002)     0.036 (0.002)

30      300      0.141 (0.013)     0.141 (0.013)     0.145 (0.013)              0.156 (0.013)              0.196 (0.016)

30      1500     0.096 (0.005)     0.096 (0.005)     0.097 (0.006)              0.106 (0.006)              0.117 (0.007)

30      6000     0.076 (0.002)     0.075 (0.002)              0.074 (0.003)     0.079 (0.003)              0.089 (0.003)

50      300      0.175 (0.013)     0.175 (0.012)     0.179 (0.012)              0.192 (0.012)              0.243 (0.015)

50      1500     0.122 (0.006)     0.122 (0.006)     0.124 (0.006)              0.131 (0.006)              0.142 (0.007)

50      6000     0.095 (0.003)     0.095 (0.003)              0.095 (0.003)     0.100 (0.003)              0.112 (0.004)

The average and standard deviation of RMSE using random forests with different leaf sizes $l$ when the training data is generated by the MNL model.

$N$     $T$      $B = 10$            $B = 100$           $\bm {B = 1000}$          $B = 5000$          $B = 10000$

10      300      0.075 (0.010)     0.067 (0.011)     0.066 (0.010)     0.066 (0.010)     0.066 (0.010)

10      1500     0.057 (0.004)     0.048 (0.004)     0.047 (0.004)     0.047 (0.004)     0.047 (0.004)

10      6000     0.048 (0.002)     0.040 (0.001)     0.039 (0.001)     0.039 (0.002)     0.039 (0.002)

30      300      0.157 (0.012)     0.146 (0.013)     0.145 (0.013)     0.145 (0.013)     0.145 (0.013)

30      1500     0.112 (0.005)     0.099 (0.005)     0.097 (0.006)     0.097 (0.006)     0.097 (0.006)

30      6000     0.090 (0.003)     0.075 (0.003)     0.074 (0.003)     0.073 (0.003)     0.073 (0.003)

50      300      0.191 (0.013)     0.180 (0.012)     0.179 (0.012)     0.179 (0.011)     0.179 (0.011)

50      1500     0.139 (0.006)     0.125 (0.006)     0.124 (0.006)     0.124 (0.006)     0.124 (0.006)

50      6000     0.111 (0.003)     0.096 (0.003)     0.095 (0.003)     0.094 (0.003)     0.094 (0.003)

The average and standard deviation of RMSE using random forests with different numbers of trees $B$ when the training data is generated by the MNL model.

$N$     $T$      $B = 10$            $B = 100$           $\bm {B = 1000}$          $B = 5000$          $B = 10000$

10      300      0.03         0.16          1.32           7.30           14.62

10      1500     0.03         0.20          1.61           8.72           17.26

10      6000     0.04         0.30          2.58           14.15          28.20

30      300      0.17         0.45          3.00           15.62          31.17

30      1500     0.17         0.55          3.58           18.76          36.26

30      6000     0.19         0.67          5.54           26.79          50.99

50      300      0.18         0.51          3.47           18.17          36.52

50      1500     0.19         0.59          4.22           22.53          44.48

50      6000     0.20         0.82          6.79           33.27          66.06

The running time (in seconds) of random forests with different numbers of trees $B$ when the training data is generated by the MNL model.

§ EXPECTED DISTANCE IN SECTION <REF>

In this section, we show that a polynomial number of assortments cannot guarantee the expected distance to be within $O(\log N)$ by numerical studies.
The result complements Proposition <ref>.
Let $M$ be the number of assortments randomly drawn with replacement in the training data.
We sample 100,000 instances for a combination of  $N$ and $M$ and take the average number of zeros for the largest binary numbers. The results are shown in Figure <ref>.

Average distances of different $N$ and $M$.

We can observe that even for $M = O(N^{\log N})$, the average distance is still growing linearly.

§ NUMERICAL EXPERIMENTS FOR RANK-BASED DCM

In this section, we complement the results in Theorem <ref> by additional numerical studies.
Theorem <ref> states that the random forest algorithm can recover the rank-based DCM with a single ranking
when the training data is sampled uniformly.
We will demonstrate numerically that the result still holds when the training data is not uniform.
We also provide some examples showing that even though random forests may fail to recover the rankings exactly,
the predicted probability is still quite accurate.

Moreover, we demonstrate the insights that when the rank-based DCM consists of more than one ranks (customer types),
the random forest may output a tree that “concatenates” multiple ranks.

§.§ Non-uniform Training Data

Consider $N=3$ products for the illustration purpose.
Suppose customers prefer $1 \succ 2 \succ 3 \succ 0$, where 0 denotes the outside option.
Figure <ref> illustrates the decision tree corresponding to the preference of the customers,
where the splits are in the order of 1, 2, 3.
We evaluate the performance of random forests by the number of correct splits until the first mistake is made.
Notice that if the algorithm returns a tree that correctly splits the first $i$ cuts, then it can accurately predict a fraction of $1-1/2^i$ of total assortments.
For example, if the splits are 1, 3, 2 in order, then the algorithm makes one correct split and accurately predicts a half of total assortments.

Now consider $N=10$ and $2^N=1024$ possible assortments (including the empty set).
The parameter of random forests are $B=10, z = T, m = N, l = 1$.
We compare the performance of random forests in the following three sampling schemes:

* Uniform: Each assortment is observed with equal probability $1/2^N$;

* Non-uniform: The probability of observing each assortment follows a Dirichlet distribution with concentration parameters all equal to ones;

* Different occurrences: generate probability $p_i$ for each product, where $p_i$ independently follows a normal distribution with mean 0.5 and standard deviation 0.15 so that $p_i$ falls into $[0,1]$ with high probability. We set $p_i=0$ if the random variable is negative and $p_i = 1$ if it exceeds 1.
In each assortment in the data, each product is included with probability $p_i$.

We test different sizes of training data $T \in [100, 1000, 10000]$.
For each setup, we generate 100 independent datasets and inspect $B=10$ trees for each dataset.
The mean and standard deviation of the correct splits are reported in Table <ref>.

$T$       Uniform           Non-uniform       Different occurrences

100       4.281 (0.951)     4.185 (0.922)     3.575 (1.372)

1000      7.715 (1.058)     7.370 (1.110)     6.369 (1.732)

10000     9.961 (0.256)     9.131 (0.986)     8.610 (2.145)

The number of correct splits by random forests.

In general the uniform sampling has the best performance, but the algorithm is quite robust to other non-uniform sampling schemes.

§.§ Reconstruction of Decision Trees

From the numerical studies, we observe that some of the trees learned from the random forest may not have the some structure as the actual ranking.
They nevertheless represent the same choice probabilities.
To illustrate, consider $N=3$ and let the consumers' ranking be represented by Figure <ref>.

The random forest may learn a tree as shown in Figure <ref> or <ref>, which represents the same DCM but with a different structure.

[The tree representing the preference list of consumers]

for tree=l sep+=.8cm,s sep+=.5cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[Has product 1
[1,edge label=node[midway,left]Y
[Has product 2,edge label=node[midway,right]N
[2, edge label=node[midway,left]Y]
[Has product 3, edge label=node[midway,right]N
[3, edge label=node[midway,left]Y]
[0, edge label=node[midway,right]N]

[A reconstructed tree having the same choice]

for tree=l sep+=.8cm,s sep+=.5cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[Has product 2
[Has product 1,edge label=node[midway,left]Y
[1, edge label=node[midway,left]Y]
[2, edge label=node[midway,right]N]
[Has product 1,edge label=node[midway,right]N
[1, edge label=node[midway,left]Y]
[Has product 3, edge label=node[midway,right]N
[3, edge label=node[midway,left]Y]
[0, edge label=node[midway,right]N]

[A reconstructed tree having the same choice]

for tree=l sep+=.8cm,s sep+=.5cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[Has product 3
[Has product 1,edge label=node[midway,left]Y
[1, edge label=node[midway,left]Y]
[Has product 2, edge label=node[midway,right]N
[2, edge label=node[midway,left]Y]
[3, edge label=node[midway,right]N]
[Has product 1,edge label=node[midway,right]N
[1, edge label=node[midway,left]Y]
[Has product 2, edge label=node[midway,right]N
[2, edge label=node[midway,left]Y]
[0, edge label=node[midway,right]N]

Three possible trees representing the same choice.

§.§ Multiple Rankings

Next we study the case when customers are represented by a mixture of multiple rankings.
More precisely, consider $N=5$ and two customer segments.
Suppose 70% of customers are type one and have preference $1 \succ 2 \succ 3 \succ 4 \succ 5 \succ 0$; the remaining 30% of customers are type two preferring $5 \succ 4 \succ 3 \succ 2 \succ 1 \succ 0$.
When $T = 1000, B=10, z = T, m = N, l = 1$, a number of trees learned by Algorithm <ref> resemble the structure shown in Figure <ref>.
There may be more than one chosen product in the leaf node explained in (<ref>).
For example, “1(5)” implies that most customers select product one in this leaf node, but some others purchase product 5.
We can see that the main branch on the right looks like the preference list of type one.
Meanwhile, some branches of the ranking of type two customers are attached to it.
Random forests somehow merge the preferences of various segments into a single tree.
This is a phenomenon commonly observed in our experiments and may shed light on the robust performance of random forests.

for tree=l sep+=.5cm,s sep+=.3cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[Has 1
[Has 5,edge label=node[midway,left]Y
[1(5), edge label=node[midway,left]Y]
[Has 4, edge label=node[midway,right]N
[1(4), edge label=node[midway,left]Y]
[Has 3, edge label=node[midway,right]N
[1(3), edge label=node[midway,left]Y]
[Has 2, edge label=node[midway,right]N
[1(2), edge label=node[midway,left]Y]
[1, edge label=node[midway,right]N]
[Has 2,edge label=node[midway,right]N
[Has 5, edge label=node[midway,left]Y
[2(5), edge label=node[midway,left]Y]
[Has 4, edge label=node[midway,right]N
[2(4), edge label=node[midway,left]Y]
[Has 3, edge label=node[midway,right]N
[2(3), edge label=node[midway,left]Y]
[2, edge label=node[midway,right]N]
[Has 3, edge label=node[midway,right]N
[Has 5, edge label=node[midway,left]Y
[3(5), edge label=node[midway,left]Y]
[Has 4, edge label=node[midway,right]N
[3(4), edge label=node[midway,left]Y]
[3, edge label=node[midway,right]N]
[Has 4, edge label=node[midway,right]N
[Has 5, edge label=node[midway,left]Y
[4(5), edge label=node[midway,left]Y]
[4, edge label=node[midway,right]N]
[Has 5, edge label=node[midway,right]N
[5, edge label=node[midway,left]Y]
[0, edge label=node[midway,right]N]

A tree output by random forests that merges two rankings.

§ NUMERICAL EXAMPLES FOR PRODUCT IMPORTANCE

§.§ Synthetic Examples

Here we give an example of MDI (see Section <ref> for details) under the rank-based DCM (with one ranking) and the MNL model.

Consider 10 products and data size $T = 10000$.
The assortment in training data is uniformly generated among non-empty subsets.
We use $B = 1000, m = \sqrt{N}, l = 50$ for the random forest algorithm.
The ground-truth model is a single ranking: $1 \succ 2 \succ \ldots \succ 10$.
The MDI is shown in Figure <ref>.
We can observe that the MDI is decreasing in product indices.

MDI of a single ranking when $N = 10, T = 10000$.

When the ground-truth model is MNL, we generate utilities $u_i$ from a uniform distribution on $[0,1]$ for each product.
The attraction of product $i$ is defined as $a_i = \exp(u_i)$ and the choice probability is $p(i, S) = a_i / \sum_{j \in S} a_j$.
We show the attractions and MDI of random forests in Figure <ref>.
It is clear that the MDI is highly correlated with attractions.

MDI of the MNL model when $N = 10, T = 10000$.

§.§ Hotel and IRI Datasets

We also calculate the MDI for the hotel and IRI datasets.
Products with the highest MDI are listed in Tables <ref> and <ref>.
In the IRI dataset (Table <ref>), the products are represented by the vendor codes.
MDI-insightsThe products with the highest MDI do not necessarily have high demand, but play an important role in customers' decision process.
Therefore, we recommend the firms to prioritize the experimentation of these products when optimizing over assortments or prices.

Hotel       Room type                            MDI
Hotel 1     King Room 3                          0.222

Special Type Room 1                  0.160

Queen Room 2                         0.100

King Room 4                          0.096
Hotel 2     2 Queen Beds Room 2 Smoking          0.279

2 Queen Beds Room 1 Non-Smoking      0.202

2 Queen Beds Room 2 Non-Smoking      0.157

King Room 3 Non-Smoking              0.148
Hotel 3     King Room 1 Non-Smoking              0.523

2 Double Beds Room 1 Non-Smoking     0.263

King Room 3 Non-Smoking              0.081

2 Double Beds Room 1 Smoking         0.049
Hotel 4     King Room 1 Non-Smoking              0.641

2 Queen Beds Room 1 Non-Smoking      0.179

2 Queen Beds Room 1 Smoking          0.100

Suite 2 Non-Smoking                  0.080
Hotel 5     King Room 2 Non-Smoking              0.496

King Room 1 Non-Smoking              0.228

2 Double Beds Room 1 Non-Smoking     0.085

2 Double Beds Room 2 Non-Smoking     0.077

Four room types with the highest MDI in each hotel.

Product Category     No.1 prod     MDI     No.2 prod     MDI     No.3 prod     MDI

Beer     87692     0.375     83820     0.364     78250     0.148

Blades     99998     0.302     52754     0.149     41058     0.140

Carbonated Beverages     73800     0.276     42200     0.178     71698     0.171

Cigarettes     710     0.322     90500     0.248     99998     0.170

Coffee     75101     0.210     11141     0.200     71038     0.162

Cold Cereal     42400     0.358     18627     0.175     21908     0.148

Deodorant     19045     0.315     9973     0.297     22600     0.150

Diapers     99998     0.424     48157     0.216     32913     0.206

Facial Tissue     63435     0.357     43032     0.296     99998     0.099

Frozen Dinners/Entrees     50100     0.334     17854     0.251     72655     0.234

Frozen Pizza     74653     0.234     19600     0.202     35300     0.180

Household Cleaners     35000     0.276     23400     0.260     25700     0.190

Hotdogs     75278     0.178     85331     0.168     46600     0.151

Laundry Detergent     45893     0.447     35000     0.186     72613     0.138

Margarine/Butter     96451     0.479     33100     0.202     34500     0.115

Mayonnaise     45200     0.248     52100     0.224     52500     0.172

Milk     99998     0.280     75457     0.269     41483     0.241

Mustard     71828     0.250     24000     0.235     70080     0.190

Paper Towels     43032     0.293     44096     0.216     30400     0.164

Peanut Butter     71018     0.321     45300     0.202     34000     0.117

Photo     74101     0.322     99998     0.280     41778     0.143

Razors     41058     0.350     99998     0.325     47400     0.197

Salt Snacks     41780     0.401     41262     0.284     72600     0.157

Shampoo     65632     0.350     71249     0.226     99998     0.142

Soup     41789     0.351     24000     0.332     50100     0.164

Spaghetti/Italian Sauce     72940     0.313     77644     0.254     6010     0.161

Sugar Substitutes     99998     0.191     19098     0.174     58312     0.137

Toilet Tissue     43032     0.416     44096     0.233     30400     0.205

Toothbrushes     70942     0.252     69055     0.216     416     0.140

Toothpaste     68305     0.376     77326     0.248     10310     0.164

Yogurt     21000     0.389     41148     0.171     53600     0.151

Three product vendors with the highest MDI in each category of the IRI dataset.

§ ADDITIONAL RESULTS FOR THE IRI DATASET

In this section, we provide additional results for the IRI dataset when the top five and fifteen products are considered.
The setup is described in Section <ref>.

Product category     #Data     #Unique assort    #Avg prod     RF     MNL     MC Beer     10,440     8     2.88     0.3268 (0.0005)     0.3269 (0.0006)     0.3268 (0.0006) Blades     1,085     10     3.10     0.3200 (0.0054)     0.3192 (0.0052)     0.3197 (0.0052) Carbonated Beverages     71,114     4     3.75      0.3503 (0.0006)     0.3508 (0.0006)     0.3505 (0.0006) Cigarettes     6,760     8     3.50     0.2916 (0.0023)     0.2916 (0.0024)     0.2916 (0.0024) Coffee     8,135     8     3.50     0.3396 (0.0012)     0.3405 (0.0012)     0.3400 (0.0012) Cold Cereal     30,369     4     4.00     0.3324 (0.0004)     0.3324 (0.0004)     0.3324 (0.0004) Deodorant     2,775     4     3.75     0.3429 (0.0005)     0.3430 (0.0005)     0.3430 (0.0005) Diapers     1,528     6     3.17     0.3585 (0.0030)     0.3590 (0.0022)     0.3590 (0.0024) Facial Tissue     8,956     9     3.12     0.3389 (0.0006)     0.3422 (0.0009)     0.3410 (0.0007) Frozen Dinners/Entrees     48,349     6     3.83     0.3298 (0.0004)     0.3303 (0.0005)     0.3300 (0.0004) Frozen Pizza     16,263     14     3.43     0.3471 (0.0005)     0.3491 (0.0004)     0.3478 (0.0004) Household Cleaners     6,403     4     3.50     0.3272 (0.0025)     0.3272 (0.0024)     0.3272 (0.0024) Hotdogs     7,281     13     3.08     0.3489 (0.0017)     0.3511 (0.0016)     0.3498 (0.0019) Laundry Detergent     7,854     11     3.36     0.3319 (0.0021)     0.3343 (0.0018)     0.3333 (0.0018) Margarine/Butter     9,534     5     3.80     0.3428 (0.0005)     0.3431 (0.0004)     0.3429 (0.0004) Mayonnaise     4,380     7     2.71     0.3552 (0.0010)     0.3567 (0.0008)     0.3553 (0.0009) Milk     56,849     12     3.25     0.2641 (0.0012)     0.2645 (0.0011)     0.2643 (0.0012) Mustard     5,354     7     3.29     0.3348 (0.0007)     0.3353 (0.0007)     0.3350 (0.0007) Paper Towels     9,520     8     3.63     0.3258 (0.0012)     0.3260 (0.0013)     0.3258 (0.0013) Peanut Butter     4,985     9     3.44     0.3321 (0.0012)     0.3332 (0.0008)     0.3326 (0.0011) Photography supplies     189     17     2.88     0.3526 (0.0117)     0.3526 (0.0111)     0.3542 (0.0100) Razors     111     8     2.50     0.2942 (0.0567)     0.2957 (0.0458)     0.2992 (0.0444) Salt Snacks     44,975     7     3.57     0.3140 (0.0009)     0.3152 (0.0009)     0.3147 (0.0008) Shampoo     3,353     8     3.38     0.3391 (0.0011)     0.3390 (0.0010)     0.3390 (0.0010) Soup     68,049     5     4.20     0.3346 (0.0003)     0.3355 (0.0003)     0.3350 (0.0003) Spaghetti/Italian Sauce     12,377     7     3.43     0.3369 (0.0008)     0.3371 (0.0008)     0.3369 (0.0008) Sugar Substitutes     1,269     9     3.44     0.3276 (0.0050)     0.3274 (0.0053)     0.3277 (0.0053) Toilet Tissue     11,154     9     3.44     0.3421 (0.0002)     0.3428 (0.0002)     0.3424 (0.0001) Toothbrushes     2,562     12     3.25     0.3415 (0.0010)     0.3415 (0.0012)     0.3414 (0.0011) Toothpaste     4,258     6     3.50     0.3230 (0.0016)     0.3229 (0.0017)     0.3229 (0.0017) Yogurt     61,671     11     3.18     0.3341 (0.0011)     0.3383 (0.0011)     0.3369 (0.0011)
The summary statistics (the data size, the number of unique assortments in the data, and the average number of products in an assortment) of the IRI dataset after preprocessing and the average and standard deviation of the out-of-sample RMSE (<ref>) for each category when considering the top 5 products.

Product category     #Data     #Unique assort    #Avg prod     RF     MNL     MC Beer     10,441     234     10.13     0.2294 (0.0010)     0.2303 (0.0009)     0.2302 (0.0010) Blades     1,085     56     5.46     0.3092 (0.0036)     0.3074 (0.0040)     0.3077 (0.0041) Carbonated Beverages     71,114     229     7.83      0.2733 (0.0003)     0.2763 (0.0004)     0.2759 (0.0005) Cigarettes     6,760     179     6.86     0.2521 (0.0015)     0.2530 (0.0020)     0.2528 (0.0017) Coffee     8,135     269     9.08     0.2619 (0.0011)     0.2669 (0.0008)     0.2656 (0.0009) Cold Cereal     30,369     325     10.52     0.2375 (0.0005)     0.2387 (0.0004)     0.2386 (0.0004) Deodorant     2,775     227     10.41     0.2439 (0.0008)     0.2436 (0.0006)     0.2435 (0.0006) Diapers     1,528     13     3.85     0.3581 (0.0027)     0.3583 (0.0022)     0.3584 (0.0025) Facial Tissue     8,956     63     4.89     0.3238 (0.0010)     0.3306 (0.0012)     0.3290 (0.0011) Frozen Dinners/Entrees     48,349     163     11.13     0.2282 (0.0003)     0.2318 (0.0002)     0.2311 (0.0002) Frozen Pizza     16,263     317     8.25     0.2680 (0.0008)     0.2742 (0.0002)     0.2726 (0.0003) Household Cleaners     6,403     93     11.78     0.2346 (0.0005)     0.2347 (0.0004)     0.2346 (0.0004) Hotdogs     7,281     259     7.61     0.2764 (0.0017)     0.2863 (0.0006)     0.2837 (0.0010) Laundry Detergent     7,854     158     7.81     0.2589 (0.0020)     0.2717 (0.0019)     0.2689 (0.0017) Margarine/Butter     9,534     89     9.34     0.2733 (0.0003)     0.2745 (0.0003)     0.2740 (0.0003) Mayonnaise     4,380     263     6.79     0.2912 (0.0022)     0.2958 (0.0006)     0.2938 (0.0011) Milk     56,849     99     6.47     0.2318 (0.0011)     0.2379 (0.0013)     0.2362 (0.0014) Mustard     5,354     410     9.84     0.2476 (0.0009)     0.2492 (0.0006)     0.2487 (0.0005) Paper Towels     9,520     80     6.66     0.2870 (0.0009)     0.2903 (0.0009)     0.2894 (0.0008) Peanut Butter     4,985     166     7.10     0.2896 (0.0019)     0.2986 (0.0012)     0.2970 (0.0014) Photography supplies     189     37     3.43     0.3416 (0.0094)     0.3455 (0.0085)     0.3444 (0.0086) Razors     111     10     2.60     0.3269 (0.0334)     0.3294 (0.0251)     0.3323 (0.0218) Salt Snacks     44,975     170     7.89     0.2463 (0.0012)     0.2487 (0.0011)     0.2481 (0.0012) Shampoo     3,354     219     10.96     0.2387 (0.0006)     0.2380 (0.0007)     0.2380 (0.0007) Soup     68,049     199     10.82     0.2258 (0.0004)     0.2330 (0.0003)     0.2321 (0.0003) Spaghetti/Italian Sauce     12,377     207     9.43     0.2532 (0.0010)     0.2568 (0.0008)     0.2563 (0.0007) Sugar Substitutes     1,269     126     6.13     0.3060 (0.0050)     0.3049 (0.0051)     0.3046 (0.0050) Toilet Tissue     11,154     67     7.21     0.2971 (0.0006)     0.3022 (0.0003)     0.3011 (0.0004) Toothbrushes     2,562     280     10.49     0.2431 (0.0010)     0.2436 (0.0004)     0.2434 (0.0004) Toothpaste     4,258     550     9.64     0.2360 (0.0013)     0.2377 (0.0010)     0.2377 (0.0011) Yogurt     61,671     121     6.36     0.2730 (0.0011)     0.2803 (0.0009)     0.2782 (0.0009)
The summary statistics (the data size, the number of unique assortments in the data, and the average number of products in an assortment) of the IRI dataset after preprocessing and the average and standard deviation of the out-of-sample RMSE (<ref>) for each category when considering the top 15 products.


# A Nascent Tidal Dwarf Galaxy Forming within the Northern HI Streamer of M82

Imad Pasha NSF Graduate Research Fellow  Department of Astronomy, Yale
University, 52 Hillhouse Ave., New Haven, CT 06511  Deborah Lokhorst
Department of Astronomy & Astrophysics, University of Toronto, 50 St. George
Street, Toronto, ON, M5S 3H4, Canada  Dunlap Institute of Astronomy &
Astrophysics, University of Toronto, 50 St. George Street, Toronto, ON, M5S
3H4, Canada  Pieter G. van Dokkum Department of Astronomy, Yale University, 52
Hillhouse Ave., New Haven, CT 06511  Seery Chen Department of Astronomy &
Astrophysics, University of Toronto, 50 St. George Street, Toronto, ON, M5S
3H4, Canada  Dunlap Institute of Astronomy & Astrophysics, University of
Toronto, 50 St. George Street, Toronto, ON, M5S 3H4, Canada  Roberto Abraham
Department of Astronomy & Astrophysics, University of Toronto, 50 St. George
Street, Toronto, ON, M5S 3H4, Canada  Dunlap Institute of Astronomy &
Astrophysics, University of Toronto, 50 St. George Street, Toronto, ON, M5S
3H4, Canada  Johnny Greco Center for Cosmology and AstroParticle Physics
(CCAPP), The Ohio State University, Columbus, OH 43210, USA  Shany Danieli
Department of Astronomy, Yale University, 52 Hillhouse Ave., New Haven, CT
06511  Tim Miller Department of Astronomy, Yale University, 52 Hillhouse Ave.,
New Haven, CT 06511  Erin Lippitt Department of Astronomy, Yale University, 52
Hillhouse Ave., New Haven, CT 06511  Ava Polzin Department of Astronomy, Yale
University, 52 Hillhouse Ave., New Haven, CT 06511  Zili Shen Department of
Astronomy, Yale University, 52 Hillhouse Ave., New Haven, CT 06511  Michael A.
Keim Department of Astronomy, Yale University, 52 Hillhouse Ave., New Haven,
CT 06511  Qing Liu (刘青) Department of Astronomy & Astrophysics, University of
Toronto, 50 St. George Street, Toronto, ON, M5S 3H4, Canada  Dunlap Institute
of Astronomy & Astrophysics, University of Toronto, 50 St. George Street,
Toronto, ON, M5S 3H4, Canada  Allison Merritt Max-Planck-Institut für
Astronomie, Königstuhl 17, D-69117 Heidelberg, Germany  Jielai Zhang Centre
for Astrophysics and Supercomputing, Swinburne University of Technology, Mail
Number H29, PO Box 218, 31122 Hawthorn, VIC, Australia  ARC Centre of
Excellence for Gravitational Wave Discovery (OzGrav), Hawthorn, 3122,
Australia

(Accepted by ApJL)

###### Abstract

We identify a $\sim$600 pc-wide region of active star formation located within
a tidal streamer of M82 via H$\alpha$ emission ($F_{H\alpha}\sim 6.5\times
10^{-14}$ erg s-1 cm-2), using a pathfinder instrument based on the Dragonfly
Telephoto Array. The object is kinematically decoupled from the disk of M82 as
confirmed via Keck / LRIS spectroscopy, and is spatially and kinematically
coincident with an overdensity of HI and molecular hydrogen within the
“northern HI streamer” induced by the passage of M81 several hundred Myr ago.
From HI data, we estimate that $\sim 5\times 10^{7}$ M⊙ of gas is present in
the specific overdensity coincident with the H$\alpha$ source. The object’s
derived metallicity (12+$\log(O/H)\simeq 8.6$), position within a gas-rich
tidal feature, and morphology (600 pc diameter with multiple star forming
clumps), indicate that it is likely a tidal dwarf galaxy in the earliest
stages of formation.

galaxies — imaging, galaxies — evolution, tidal dwarf galaxies

††software: numpy (Van Der Walt et al., 2011), astropy (Astropy Collaboration
et al., 2018), matplotlib (Hunter, 2007), emcee (Foreman-Mackey et al., 2013),
PypeIt (Prochaska et al., 2020), SExtractor (Bertin & Arnouts, 1996).

##  1 Introduction

M82 is among the most extensively-studied galaxies, with decades of high
resolution observations having been facilitated by the M81 group’s close
proximity (D $\simeq$ 3.63 Mpc; Karachentsev et al., 2004). M82 is considered
the “prototypical” starbursting galaxy, featuring a bipolar superwind outflow
that extends kiloparsecs along the minor axis of the galaxy. Many of M82’s
features, including a disturbed disk and the starburst itself, are thought to
have been triggered by the recent passage of M81 $\sim$200$-$300 Myr ago
(e.g., Cottrell, 1977). Studies of the neutral and molecular hydrogen in M82
have found evidence of tidally induced structures, including disruption of the
gas from the disk of M82 (e.g., Sofue, 1998) and a significant amount of gas
located in the field and in tidal bridges between M81, M82 and NGC 3077 (e.g.,
Yun et al., 1994).

This environment makes the M81 group conducive to the formation of Tidal Dwarf
Galaxies (TDGs), which form in the tidal arms and bridges induced by galaxy
encounters. Gravitational instabilities develop in the absence of the
rotational support that existed in the disk, and the Jeans mass rises due to
the additional dispersion created by the heating of the material during the
encounter (e.g. Duc et al., 2000; Struck et al., 2005). In contrast to typical
low mass dwarf galaxies, TDGs have little to no dark matter, and have
metallicities commensurate with their progenitor spirals rather than the range
expected from the dwarf mass-metallicity relation (e.g., Duc et al., 2004;
Bournaud & Duc, 2006). The creation rate of TDGs and their survivability rates
are poorly constrained, but have potential impacts on the interpretation of
satellite population statistics in a $\Lambda$CDM framework.

Several of the dwarf galaxies in the M81 group are thought to be TDGs,
including Holmberg IX, BK3N, Arp-loop (A0952+69), and Garland (e.g., Makarova
et al., 2002; Weisz et al., 2008; Sabbi et al., 2008; de Mello et al., 2008);
however, none of these candidate TDGs or TDG progenitors are located in the
vicinity of M82, instead clustering near M81 and NGC 3077. Indeed, no regions
of active star formation have been reported in and around M82 outside the
galactic disk.

We have used a novel telescope built on the framework of the Dragonfly
Telephoto Array (Abraham & van Dokkum, 2014), the 3-lens narrowband pathfinder
version of the forthcoming Dragonfly Spectral Line Mapper (pDSLM), to image
low surface brightness emission in the M81 group in H$\alpha$ and [NII]. We
selected the M81 group to vet the narrowband design because deep prior
H$\alpha$ observations exist, providing a test of the depths being reached by
the instrument. Our final H$\alpha$ images of the field reach surface
brightness depths of $\sim 5\times 10^{-19}$ erg s-1 cm-2 arcsec-2, and
uncover several new features in the gas around M82 that will be described in
forthcoming work. Details of the pDSLM instrument are provided in Lokhorst et
al. (2019, 2020).

In this Letter, we present the analysis of an H$\alpha$ object near M82 that
is likely a TDG in formation, using the first science data obtained with this
instrument. We have designated this source DF-E1 (“Sapling”), as it is the
first emission source cataloged by Dragonfly.

Figure 1: pDSLM continuum-subtracted image of M82 in H$\alpha$, with
foreground stars masked. The HST composite image of M82 from Mutchler et al.
(2007) has been overlaid for a sense of scale. An inset panel shows a 2.5′
$\times$ 2.5′ square cutout around DF-E1, with red contours showing HI from de
Blok et al. (2018) (dB18 hereafter) and blue contours showing CO from Leroy et
al. (2015) (L15 hereafter) in the region overlaid. The strongest overdensity
of the northern HI tidal arm spatially overlaps with DF-E1, with the peak of
the HI emission falling within 15′′ of the peak of the H$\alpha$ source.
Similarly, an overdensity of CO is present, consistent with the HI peak.

##  2 Narrowband Imaging

###  2.1 Observations

The pDSLM builds on the telephoto array concept of Dragonfly by placing ultra
narrowband interference filters ($\Delta\lambda=0.8-3$ nm) in front of each
lens of the array, targeting H$\alpha$ and [NII] via tilting of the filters,
and [OIII].

The M81 group was observed with the pDSLM over the course of several weeks
during the spring of 2020 at both H$\alpha$ and [NII] tilts. Observations were
carried out semi-autonomously, with a dither pattern of 15′ between exposures.
Individual frames had exposure times of 1800 seconds. During data reduction,
low quality frames were automatically identified and removed. Frames
ultimately used in this analysis were also checked by eye to ensure quality;
some frames were removed due to light contamination from sources in the dome
or were cropped due to significant amplifier glow in corners of the frame.

The final images presented here comprise 190 frames in H$\alpha$ (taken across
the three lenses in the pathfinder array), for a “single-lens” total exposure
time of 95 hours, and 89 frames in [NII] for an total exposure time of 44.5
hours. Individual images were flatfielded and dark current subtracted using
calibration frames taken nearest each observation temporally.

###  2.2 Continuum Subtraction and Flux Calibration

Continuum subtraction was performed using exposures taken with the Dragonfly
Telephoto Array in the Sloan-$r$ band. These images have similar pixel scales
and point spread functions to the images taken with the pDSLM setup. An
effective scaling factor of 11.3 was determined between the continuum image
and the narrow band images, using a combination of aperture photometry on
stars in the field as well as apertures placed on the disk of M82. We used the
SourceExtractor package (Bertin & Arnouts, 1996) to identify and mask any
point-like sources in images prior to continuum subtraction.

Published fluxes of HII regions in M81 were used to directly calibrate our
image counts; while not shown in the cutouts presented here, M81 was in the
imaging field of view. We selected two independent datasets to use, one from
Lin et al. (2003), the other from Patterson et al. (2012), which present
spectrally-calibrated H$\alpha$+[NII] fluxes and H$\alpha$ luminosities,
respectively. We defined one calibration by combining our [NII] and H$\alpha$
images and comparing to Lin et al. (2003), and another by comparing to the
fluxes implied by the Patterson et al. (2012) luminosities to our H$\alpha$
image alone.

Table 1: Properties of DF-E1 Source Property |  Value
---|---
R.A. | 09 56 32.184
DEC | +69 42 45.453
$v_{\rm helio}$ | 276.7 ($\pm$ 25) km s-1
$v_{\rm helio}-v_{\rm M82}$ | 73.7 ($\pm$ 25) km s-1
DiameteraaDefined as the mean FWHM of a Gaussian fit to the Dragonfly image. (arcsec) | 34.6′′
DiameterbbAssuming a distance of 3.63 Mpc. (pc) | 608 pc
H$\alpha$ FluxccNot corrected for dust attenuation. | (6.5$\pm$0.9)$\times$10-14 erg s-1 cm-2
[NII] FluxccNot corrected for dust attenuation. | (2.9$\pm$0.4)$\times$10-14 erg s-1 cm-2
[NII]/H$\alpha$ (pDSLM) | 0.38 $\pm$ 0.06
[NII]/H$\alpha$ (LRIS) | 0.31 $\pm$ 0.015
[OIII]/$H\beta$ (LRIS) | 0.34 $\pm$ 0.07
12+$\log(O/H)$ (via $O3N2$) | 8.67 $\pm$ 0.14
L(H$\alpha$)ccNot corrected for dust attenuation. | (1.03$\pm$0.14)$\times$1038 erg s-1
log SFR(H$\alpha$) |  $-$2.39 $\pm$ 0.03
FUV Flux Density | (2.73$\pm$1.1)$\times$10-14 erg s-1 cm-2 Å-1
log SFR(FUV)ccNot corrected for dust attenuation. |  $-$2.317
HI Mass |  $\sim$5$\times$107 M⊙

For each calibration, we computed best-fit relations in log space using a
first degree polynomial in an iterative sigma-clipping routine that eliminates
outliers of $>3\sigma$ in each iteration. Both calibrations were consistent
with each other, with no observed systematic offset. Due to the greater number
of HII regions included and marginally tighter scatter, we have adopted the
best fit relation to the Lin et al. (2003) observations in this work, which
has a derived calibration of

$\log(F)\;\rm[erg\;s^{-1}\;cm^{-2}]=0.99\log(cts)-16.801,$ (1)

where log is base 10 (adopted throughout). Based on the scatter in the fit
relation, we estimate the calibration uncertainty is $\sim$5% in flux.
Additional details regarding the instrument, reduction and calibration are
provided in a companion paper (Lokhorst et al., submitted).

##  3 An H$\alpha$ Object Near M82

A summary of measurements presented in the following sections is provided in
Table 1.

###  3.1 The H$\alpha$ feature seen with the pDSLM

An H$\alpha$ image from pDSLM of M82 is presented in Figure 1. DF-E1 is
$\sim$4.3 kpc from the galactic center and 493 pc above the midplane ($\sim$3
$h_{z}$; Lim et al., 2013). While several H$\alpha$ maps from previous studies
(e.g., Lehnert et al., 1999; Hoopes et al., 2005; Karachentsev & Kaisin, 2007)
show evidence for H$\alpha$ emission overdensities at DF-E1’s location, the
detections were not discussed in those works. No study to our knowledge has
specifically referenced this H$\alpha$ object.

Figure 2: DF-E1 in HST F814W (top left), continuum-subtracted F658N (top
right), F435W (bottom left), and GALEX FUV (bottom right). The F814W panel
serves to contextualize DF-E1’s position and size with respect to M82; note,
the inner part of M82 is shown in an inverse color scaling for visual clarity.
The other three panels demonstrate a strong correspondence between the
H$\alpha$ emission morphology of DF-E1, resolved point sources in HST F435W,
and FUV emission.

DF-E1 has a well defined peak in the Dragonfly data, and exhibits lobes of
elongation in both the north-south and east-west directions, resembling an
“L-shaped” blob. We measure the size of DF-E1 from the pDSLM imaging by
fitting Gaussians to the flux profile of the source along both the north-south
and east-west position angles, passing through the peak flux location. The
average of the two fits was kept. The two fits were nearly identical, with a
full width half maximum (FWHM) value of 34.6′′ and 95% width of 58.8′′,
corresponding to linear scales of 608 pc and 1034 pc, respectively.

Figure 3: HI Moment 0 map from dB18 (left), with tidal features and the disk
midplane labeled. In the right panel, we extract a position-velocity diagram
along the slice indicated by the white aperture in the left panel from both
the HI and CO data. The location of DF-E1 in position-velocity space is
indicated by a plus, demonstrating its velocity correspondence with the tidal
feature.

The flux of the source in the aperture defined by the FWHM is
$\sim$6.5$\times$10-14 erg s-1 cm-2. We did not explicitly correct for a
background contribution to the flux from M82, but note that in the region
around but not including the source, the H$\alpha$ background is $\sim$10% of
the measured flux, which we adopt into our uncertainty. We measured the [NII]
flux similarly, obtaining $F_{[NII]}=$2.9$\times$10-14 erg s-1 cm-2,
corresponding to an [NII]/H$\alpha$ ratio of 0.38$\pm$0.06, in line with
typical values for star forming regions, and in general lower than the disk of
M82, which is known to have elevated [NII]/H$\alpha$ ratios due to turbulence
and shocks (e.g., Shopbell & Bland-Hawthorn, 1998).

The corresponding dust-uncorrected H$\alpha$ luminosity of the source is
1.03$\times$1038 erg s-1. To estimate a star formation rate from this value,
we used the calibration from Lee et al. (2009):

$\log SFR\;[M_{\odot}\;\textrm{yr}^{-1}]=0.62\log\left(7.9\times
10^{42}L_{H\alpha}\right)-0.47,$ (2)

where $L_{H\alpha}$ is in erg s-1. We selected this calibration as it is (a)
tuned to local dwarf galaxies with H$\alpha$ luminosities in the range of 1037
to 2.5$\times$1039 erg s-1, matching our source and (b) is calibrated using
the extinction-corrected FUV-H$\alpha$ relation to be intrinsically dust-
correcting. Using this calibration, we obtained an SFR of 0.004 $M_{\odot}$
yr-1 (log SFR $=-2.39$).

###  3.2 Far-UV and Optical Imaging

If DF-E1 is indeed forming stars, then we expect cospatial FUV emission. In
Figure 2 we present Galaxy Evolution Explorer (GALEX) imaging from Hoopes et
al. (2005) of M82, as well as F435W, F814W, and F658N imaging from HST
(Mutchler et al., 2007). We identify several regions of concentrated FUV
emission within the extent of DF-E1, indicating the existence of young O/B
stars. That this emission is not a background source is confirmed by the F435W
imaging, which resolves the FUV clumps into several regions containing one or
more bright point sources, and at least one clustering of stars, which we note
are found to form efficiently in TDGs (Fensch et al., 2019). These sources
furthermore, align with the ionized gas in the region.

Because TDGs form in tidal arms where dust content is expected to be minimal
compared to the host galaxy, FUV emission provides a useful direct probe of
ongoing star formation. Leveraging this expected consistency, we use the
H$\alpha$-derived SFR to infer the expected ionizing FUV flux, and compare
this with the GALEX data. We convert the H$\alpha$-derived SFR via Kennicutt
(1998):

$SFR\;[M_{\odot}\;\textrm{yr}^{-1}]=1.4\times 10^{-28}\;L_{FUV}\;[\rm
erg\;s^{-1}\;Hz^{-1}],$ (3)

which predicts a FUV flux of 1.83$\times$10-26 erg s-1 cm-2 Hz-1. We measure
the FUV flux directly in an 11′′ aperture, as the emission is more
concentrated than the H$\alpha$. Given the extremely low UV background in
GALEX FUV, we assume Poisson uncertainties on the counts. This produces a FUV
flux of (2.2$\pm$0.5)$\times$10-26 erg s-1 cm-2 Hz-1, consistent with the
predicted FUV value. In the absence of resolved HST imaging, it is clear from
Figure 2 that UV emission is a valuable locator of the star-forming sites
within the diffuse H$\alpha$ emission region or HI extent of these objects
(e.g., Mundell et al., 2004; Neff et al., 2005).

###  3.3 Neutral and Molecular Hydrogen

DF-E1 is spatially coincident with the base of a several kpc-long structure
known as the “countertail” or Northern HI streamer (Yun et al., 1993,
hereafter Y93). This feature is theorized to have been torqued northward —
opposite another HI stream in the south-west which extends down toward M81 —
after the close passage of the two galaxies several hundred Myr ago.

The overdensity of HI in the stream at the location of DF-E1 can be seen in
Figures 1 and 3 (left). The HI gas mass for the full countertail, calculated
via

$M_{\rm HI}=2.356\times 10^{5}D^{2}\int S_{\nu}dv$ (4)

where $S_{\nu}$ is in Jy and $D$ is in Mpc, is $\sim$2$\times$108 M⊙, with
$\sim$5.1$\times$107 M⊙ in an aperture cospatial with the H$\alpha$ source in
the moment 0 map. For mass calculations we use the available zero-spacing
corrected data cube from dB18 which combines the sensitivity of previous
single dish observations (Chynoweth et al., 2008) with the high resolution
data gathered by dB18. The HI gas in this region has a mean velocity of 45 km
s-1 with respect to M82’s recession velocity, with a 1$\sigma$ spread of 47 km
s-1 along the line of sight (Figure 3, right). It is well known that this gas
is kinematically decoupled from the disk of M82 (e.g., Sofue, 1998), as the
disk has a rotation velocity of $\sim$120 km s-1 at roughly the position of
DF-E1 (Greco et al., 2012).

Figure 4: Left: Extracted LRIS spectrum of DF-E1 in the blue (top) and red
side (bottom). On the blue side, we show the raw spectrum in blue and one
binned by 3 pixels in black. We readily detect H$\alpha$, both [NII] lines,
both [SII] lines, H$\beta$, [OII], [OIII] (5007 Å and 4959 Å), and H$\delta$.
The source’s velocity is estimated by performing a Bayesian fit to four lines
on the red side. Right: BPT diagram showing DF-E1’s location (white plus)
relative to SDSS galaxies from the NASA Sloan Atlas, colored by stellar mass.

Given the presence of star formation, we would also expect to see
kinematically and spatially coincident molecular hydrogen in the general
vicinity of DF-E1. Indeed, CO ($J=2\rightarrow 1$) data from L15 show an
overdensity in the 251 km s-1 channel. This corresponds to a velocity of 42 km
s-1 with respect to M82’s recession — in strong agreement with the peak of HI
emission (Figure 3).

While the spatial alignment of H$\alpha$ and FUV emission of DF-E1 with that
of HI and CO strongly suggests a star forming object within the tidal
streamer, unambiguously confirming the association of the H$\alpha$ region and
ionizing sources with the tidal feature, rather than the disk of M82, requires
detailed velocity information for DF-E1. To this end, we obtained optical
spectroscopy with Keck.

##  4 Keck / LRIS Spectroscopy

Red side and blue side spectroscopy of DF-E1 was carried out using the LRIS
spectrograph (Oke et al., 1995; Rockosi et al., 2010), mounted on the Keck I
telescope, on the nights of April 14, 2021 and May 07, 2021, respectively.
While the primary goal was to obtain the velocity of the source, we also
obtained relevant diagnostic line ratios, including [NII]/H$\alpha$ and
[OIII]/H$\beta$.

Conditions during the runs were clear and the seeing was stable at $\sim$0.6′′
and $\sim$1.3′′ for the two nights, respectively. Exposures were obtained
using the 1.5′′-wide, 168′′ longslit, using the 560 nm dichroic, 600/4000
grism, and 1200/7500 grating with a 39.6∘ dispersion angle to place 6563 Å at
the center of the red side detector. M82 was observed at its highest
elevation, which corresponded to an airmass of $\sim$1.5. Two consecutive 600s
exposures were obtained. The longslit was aligned with the brightest knot of
emission determined from the HST data with a position angle of $-15^{\circ}$.

Reduction was carried out using the PypeIt pipeline (Prochaska et al., 2020)
using the settings for lris_red and lris_blue. Instrumental flats and arcs
obtained at the beginning of the evening — as well as skylines in the science
exposures — were used to trace the slit edges and perform wavelength
calibration, sky modeling and sky subtraction.

Extracted 1-D spectra (observed frame) are presented in Figure 4, with
relevant emission lines denoted. Wavelengths are shown in vacuum, and a
heliocentric correction of $-18$ km s-1 was applied during reduction. Due to a
skyline near H$\alpha$ which was not fully removed in the pypeIt reduction, we
re-reduced the frames using sky backgrounds to measure the H$\alpha$ flux.

To determine the velocity of DF-E1, we fit a model to the four other emission
lines in the red using emcee (Foreman-Mackey et al., 2013). Emission lines
were fit with Gaussians, with amplitudes and widths left free. We constrained
the wavelength differences between the lines to their intrinsic separations,
and fit for a single wavelength shift.

We find a best-fit velocity of 276.7 km s-1, with a 1$\sigma$ posterior spread
of 1.12 km s-1; the velocity uncertainty is dominated by the calibration
uncertainty, which we estimate to be 25 km s-1. Assuming a heliocentric-
corrected velocity for M82 of 203 km s-1 (de Vaucouleurs et al., 1991), this
corresponds to a velocity of 73.7 km s-1 with respect to the recession
velocity of M82, indicating conclusively that DF-E1 is not embedded within the
rotating disk ($\sim 120$ km s-1). This is shown in Figure 3 (right), in which
DF-E1’s velocity is well within the envelope of the HI gas and well-separated
from the rotation velocity of M82.

We also extract line ratios from our spectroscopy, finding [NII]/H$\alpha$
$=0.31\pm 0.015$ and [OIII]/H$\beta=0.34\pm 0.07$. Using the $O3N2$
metallicity calibration of Pettini & Pagel (2004),

$12+\log(O/H)=8.73-0.32\times O3N2,$ (5)

we find that DF-E1 has a metallicity of $8.67\pm 0.14$, similar to
metallicities found in other TDGs (e.g., Lisenfeld et al., 2008) and
consistent with the star forming gas being pre-enriched — as one would expect
for gas liberated from the galactic disk of a massive spiral galaxy (e.g., Duc
et al., 2000; Recchi et al., 2015). This is reflected in Figure 4 (right),
where on the Baldwin, Phillips & Telervich (BPT) diagram, DF-E1 falls on the
locus of star forming galaxies, here drawn from the NASA Sloan Atlas (Blanton
et al., 2011), in a location consistent with M82’s log stellar mass of
$\sim$9-9.5.

##  5 Discussion

Based on these observations, DF-E1 is an object similar to other claimed Tidal
Dwarf Galaxies that have been recently discussed in the literature (e.g.,
Mundell et al., 2004; Querejeta et al., 2021; Román et al., 2021). If it
survives the eventual dissipation of the tidal streamer and does not fall back
into M82, it will join the ranks of dwarf satellite galaxies in the M81 group.

Many objects of this type, however, are transient in nature, quickly falling
back into the galactic disk Bournaud & Duc (2006). The tidal tail which houses
this complex of star forming regions is only several hundred Myr old, and
numerical simulations suggest that a $\sim$Gyr of decoupled evolution is
needed before one can unambiguously declare an object a TDG. DF-E1 has
properties that both aid and hinder its potential longevity. The velocity of
the tidal arm and DF-E1 is prograde with respect to M82’s rotation, which has
been found to be helpful in maintaining the TDG over time (Bournaud & Duc,
2006). Conversely, the most successful TDGs seem to be those which form at the
very tip of tidal arm structures (as far as possible from their original
host). DF-E1 is near the base of the tidal structure. An important factor
governing its survival is the velocity at which the arm (and TDG progenitor
within) is moving upward and away from M82; however, this motion is primarily
in the sky-plane and is thus unconstrained.

Further complicating this picture is the broader environment of M82. Over the
next Gyr, simulations indicate that the main galaxies in the group, M81, M82,
and NGC 3077, are likely to merge (Yun, 1999; Oehm et al., 2017), making the
fate of this particular object an open question. It is interesting to consider
whether any other TDGs may be forming in this region; if there are, they would
likely be found farther up along the northern tidal streamer, or along the
southern streamer toward M81. Deeper, higher S/N observations with the
upgraded pDSLM will be needed to investigate this possibility.

Ultimately, DF-E1 is a strong candidate for a young TDG, is in the earliest
stages of its formation, and is remarkably nearby at $\sim$3.6 Mpc, making it
a prime candidate for resolved studies of the earliest stages of this class of
object.

Keck:I (LRIS); Dragonfly Telephoto Array

## Acknowledgements

We thank the anonymous referee, whose comments and suggestions improved the
quality of this work. We thank Todd Thompson and Natascha Förster Schreiber
for valuable discussion and feedback. I.P. is supported by the National
Science Foundation Graduate Research Fellowship Program under grant No.
DGE1752134. Some of the data presented herein were obtained at the W. M. Keck
Observatory, which is operated as a scientific partnership among the
California Institute of Technology, the University of California, and the
National Aeronautics and Space Administration. The Observatory was made
possible by the generous financial support of the W. M. Keck Foundation. The
authors wish to recognize and acknowledge the very significant cultural role
and reverence that the summit of Maunakea has always had within the indigenous
Hawaiian community. We are most fortunate to have the opportunity to conduct
observations from this mountain. This research is based on observations made
with the NASA/ESA Hubble Space Telescope obtained from the Space Telescope
Science Institute, which is operated by the Association of Universities for
Research in Astronomy, Inc., under NASA contract NAS 5–26555. These
observations are associated with program 10776 (PI: Matt Mountain). The
authors thank the staff at New Mexico Skies Observatory for their support and
aid in maintaining the pDSLM instrument. The Dunlap Institute is funded
through an endowment established by the David Dunlap family and the University
of Toronto.

## References

  * Abraham & van Dokkum (2014) Abraham, R. G., & van Dokkum, P. G. 2014, PASP, 126, 55, doi: 10.1086/674875
  * Astropy Collaboration et al. (2018) Astropy Collaboration, Price-Whelan, A. M., Sipőcz, B. M., et al. 2018, AJ, 156, 123, doi: 10.3847/1538-3881/aabc4f
  * Bertin & Arnouts (1996) Bertin, E., & Arnouts, S. 1996, A&AS, 117, 393, doi: 10.1051/aas:1996164
  * Blanton et al. (2011) Blanton, M. R., Kazin, E., Muna, D., Weaver, B. A., & Price-Whelan, A. 2011, AJ, 142, 31, doi: 10.1088/0004-6256/142/1/31
  * Bournaud & Duc (2006) Bournaud, F., & Duc, P. A. 2006, A&A, 456, 481, doi: 10.1051/0004-6361:20065248
  * Chynoweth et al. (2008) Chynoweth, K. M., Langston, G. I., Yun, M. S., et al. 2008, AJ, 135, 1983, doi: 10.1088/0004-6256/135/6/1983
  * Cottrell (1977) Cottrell, G. A. 1977, MNRAS, 178, 577, doi: 10.1093/mnras/178.4.577
  * de Blok et al. (2018) de Blok, W. J. G., Walter, F., Ferguson, A. M. N., et al. 2018, ApJ, 865, 26, doi: 10.3847/1538-4357/aad557
  * de Mello et al. (2008) de Mello, D. F., Smith, L. J., Sabbi, E., et al. 2008, AJ, 135, 548, doi: 10.1088/0004-6256/135/2/548
  * de Vaucouleurs et al. (1991) de Vaucouleurs, G., de Vaucouleurs, A., Corwin, Herold G., J., et al. 1991, Third Reference Catalogue of Bright Galaxies
  * Duc et al. (2004) Duc, P. A., Bournaud, F., & Masset, F. 2004, A&A, 427, 803, doi: 10.1051/0004-6361:20041410
  * Duc et al. (2000) Duc, P. A., Brinks, E., Springel, V., et al. 2000, AJ, 120, 1238, doi: 10.1086/301516
  * Fensch et al. (2019) Fensch, J., Duc, P.-A., Boquien, M., et al. 2019, A&A, 628, A60, doi: 10.1051/0004-6361/201834403
  * Foreman-Mackey et al. (2013) Foreman-Mackey, D., Hogg, D. W., Lang, D., & Goodman, J. 2013, PASP, 125, 306, doi: 10.1086/670067
  * Greco et al. (2012) Greco, J. P., Martini, P., & Thompson, T. A. 2012, ApJ, 757, 24, doi: 10.1088/0004-637X/757/1/24
  * Hoopes et al. (2005) Hoopes, C. G., Heckman, T. M., Strickland, D. K., et al. 2005, ApJ, 619, L99, doi: 10.1086/423032
  * Hunter (2007) Hunter, J. D. 2007, Computing In Science & Engineering, 9, 90
  * Karachentsev & Kaisin (2007) Karachentsev, I. D., & Kaisin, S. S. 2007, AJ, 133, 1883, doi: 10.1086/512127
  * Karachentsev et al. (2004) Karachentsev, I. D., Karachentseva, V. E., Huchtmeier, W. K., & Makarov, D. I. 2004, AJ, 127, 2031, doi: 10.1086/382905
  * Kennicutt (1998) Kennicutt, Robert C., J. 1998, ARA&A, 36, 189, doi: 10.1146/annurev.astro.36.1.189
  * Lee et al. (2009) Lee, J. C., Gil de Paz, A., Tremonti, C., et al. 2009, ApJ, 706, 599, doi: 10.1088/0004-637X/706/1/599
  * Lehnert et al. (1999) Lehnert, M. D., Heckman, T. M., & Weaver, K. A. 1999, ApJ, 523, 575, doi: 10.1086/307762
  * Leroy et al. (2015) Leroy, A. K., Walter, F., Martini, P., et al. 2015, ApJ, 814, 83, doi: 10.1088/0004-637X/814/2/83
  * Lim et al. (2013) Lim, S., Hwang, N., & Lee, M. G. 2013, ApJ, 766, 20, doi: 10.1088/0004-637X/766/1/20
  * Lin et al. (2003) Lin, W., Zhou, X., Burstein, D., et al. 2003, AJ, 126, 1286, doi: 10.1086/377519
  * Lisenfeld et al. (2008) Lisenfeld, U., Mundell, C. G., Schinnerer, E., Appleton, P. N., & Allsopp, J. 2008, ApJ, 685, 181, doi: 10.1086/590420
  * Lokhorst et al. (2019) Lokhorst, D., Abraham, R., van Dokkum, P., Wijers, N., & Schaye, J. 2019, ApJ, 877, 4, doi: 10.3847/1538-4357/ab184e
  * Lokhorst et al. (2020) Lokhorst, D. M., Abraham, R. G., van Dokkum, P., & Chen, S. 2020, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 11445, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 1144527, doi: 10.1117/12.2561162
  * Makarova et al. (2002) Makarova, L. N., Grebel, E. K., Karachentsev, I. D., et al. 2002, A&A, 396, 473, doi: 10.1051/0004-6361:20021426
  * Mundell et al. (2004) Mundell, C. G., James, P. A., Loiseau, N., Schinnerer, E., & Forbes, D. A. 2004, ApJ, 614, 648, doi: 10.1086/423732
  * Mutchler et al. (2007) Mutchler, M., Bond, H. E., Christian, C. A., et al. 2007, PASP, 119, 1, doi: 10.1086/511160
  * Neff et al. (2005) Neff, S. G., Thilker, D. A., Seibert, M., et al. 2005, ApJ, 619, L91, doi: 10.1086/426137
  * Oehm et al. (2017) Oehm, W., Thies, I., & Kroupa, P. 2017, MNRAS, 467, 273, doi: 10.1093/mnras/stw3381
  * Oke et al. (1995) Oke, J. B., Cohen, J. G., Carr, M., et al. 1995, PASP, 107, 375, doi: 10.1086/133562
  * Patterson et al. (2012) Patterson, M. T., Walterbos, R. A. M., Kennicutt, R. C., Chiappini, C., & Thilker, D. A. 2012, MNRAS, 422, 401, doi: 10.1111/j.1365-2966.2012.20616.x
  * Pettini & Pagel (2004) Pettini, M., & Pagel, B. E. J. 2004, MNRAS, 348, L59, doi: 10.1111/j.1365-2966.2004.07591.x
  * Prochaska et al. (2020) Prochaska, J. X., Hennawi, J. F., Westfall, K. B., et al. 2020, Journal of Open Source Software, 5, 2308, doi: 10.21105/joss.02308
  * Querejeta et al. (2021) Querejeta, M., Lelli, F., Schinnerer, E., et al. 2021, A&A, 645, A97, doi: 10.1051/0004-6361/202038955
  * Recchi et al. (2015) Recchi, S., Kroupa, P., & Ploeckinger, S. 2015, MNRAS, 450, 2367, doi: 10.1093/mnras/stv798
  * Rockosi et al. (2010) Rockosi, C., Stover, R., Kibrick, R., et al. 2010, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 7735, Ground-based and Airborne Instrumentation for Astronomy III, ed. I. S. McLean, S. K. Ramsay, & H. Takami, 77350R, doi: 10.1117/12.856818
  * Román et al. (2021) Román, J., Jones, M. G., Montes, M., et al. 2021, A&A, 649, L14, doi: 10.1051/0004-6361/202141001
  * Sabbi et al. (2008) Sabbi, E., Gallagher, J. S., Smith, L. J., de Mello, D. F., & Mountain, M. 2008, ApJ, 676, L113, doi: 10.1086/587548
  * Shopbell & Bland-Hawthorn (1998) Shopbell, P. L., & Bland-Hawthorn, J. 1998, ApJ, 493, 129, doi: 10.1086/305108
  * Sofue (1998) Sofue, Y. 1998, PASJ, 50, 227, doi: 10.1093/pasj/50.2.227
  * Struck et al. (2005) Struck, C., Kaufman, M., Brinks, E., et al. 2005, MNRAS, 364, 69, doi: 10.1111/j.1365-2966.2005.09539.x
  * Van Der Walt et al. (2011) Van Der Walt, S., Colbert, S. C., & Varoquaux, G. 2011, ArXiv e-prints, arXiv:1102.1523.  https://arxiv.org/abs/1102.1523
  * Weisz et al. (2008) Weisz, D. R., Skillman, E. D., Cannon, J. M., et al. 2008, ApJ, 689, 160, doi: 10.1086/592323
  * Yun (1999) Yun, M. S. 1999, in Galaxy Interactions at Low and High Redshift, ed. J. E. Barnes & D. B. Sanders, Vol. 186, 81
  * Yun et al. (1993) Yun, M. S., Ho, P. T. P., & Lo, K. Y. 1993, ApJ, 411, L17, doi: 10.1086/186901
  * Yun et al. (1994) Yun, M. S., Ho, P. T. P., & Lo, K. Y. 1994, Nature, 372, 530, doi: 10.1038/372530a0