Proposition 7.14 -- lower bound for the top-to-random shuffle

For every real number $\varepsilon > 0$, the theorem asserts the existence of a real threshold $\alpha_0$ with $\alpha_0 > 0$ such that: for every real $\alpha$ with $\alpha > \alpha_0$ (strict), there exists a natural number $N$ (which may depend on both $\varepsilon$ and $\alpha$) such that for every natural number $n \ge N$ and every natural number $t \ge 0$ satisfying $t \le n \ln n - \alpha n$ (natural logarithm; if $n \ln n - \alpha n < 0$ there is no such $t$ and the claim is vacuous for that $n$), one has the non-strict inequality

Here the state space is $S_n$, the group of permutations of an $n$-element set; $u$ is the constant function assigning each permutation the value $1/n!$ (the reciprocal of the cardinality of $S_n$); $P_n^t(x,\cdot)$ is row $x$ of the $t$-th power of the transition matrix $P_n$ (with $P_n^0 = I$); and for two real-valued functions $\mu,\nu$ on a finite set, $d_{\mathrm{TV}}(\mu,\nu) = \sup_{A}\bigl|\sum_{\sigma \in A}\mu(\sigma) - \sum_{\sigma \in A}\nu(\sigma)\bigr|$ is the supremum over all subsets $A$ (no factor of $\tfrac12$, and a maximum since the set is finite). The matrix $P_n$ is the top-to-random shuffle, defined concretely as follows: viewing a permutation $x$ as an arrangement (position $i$ holds card $x(i)$), for each position $j \in \{0,\dots,n-1\}$ the "insert" operation removes the top card $x(0)$ and places it at position $j$, i.e. produces the arrangement $y$ with $y(i) = x(i+1)$ for $i < j$, $y(j) = x(0)$, and $y(i) = x(i)$ for $i > j$ (so $j = 0$ returns $x$ itself); then $P_n(x,y)$ is defined as $\frac{1}{n}$ times the number of positions $j$ for which $y$ coincides pointwise with the result of inserting at $j$. (For $n = 0$ this formula divides by zero, yielding the junk value $0$; but such degenerate $n$ matter only if $N = 0$ forces them into range, and the statement quantifies over all $n \ge N$ for some existentially chosen $N$.) Note the quantifier structure carefully: $\alpha_0$ is only claimed to exist and to be positive — nothing ties its size to $\varepsilon$ quantitatively — the conclusion is required only for $\alpha$ strictly above $\alpha_0$, only for $n$ at least the (arbitrarily large) chosen $N$, and only for times $t$ below $n \ln n - \alpha n$; the coefficient of the $n \ln n$ term is $1$ (not $\tfrac12$), and $d(t)$ is a worst-case (supremum) over the starting permutation $x$.