On Card guessing after a single shelf shuffle Markus Kuba Abstract . We consider a card guessing game with complete feedback. An ordered deck of n n cards labeled 1 1 up to n n is shelf-shuffled exactly one time. One after the other a single card is drawn from the shuffled deck. The guesser makes has guess and the card is shown until no cards remain. We provide a distributional analysis of the number of correct guesses under the optimal strategy. We re-obtain the previously derived expectation and add a complete description of the distribution. We also obtain a central limit theorem for the number n n of cards tending to infinity. Furthermore, we discuss an unbalanced, biased shelf shuffle and show how to derive the extend our analysis, also adding the complete position matrix. Finally, a refined analysis of the number of correct guesses is carried out, distinguishing between pure luck guesses and certified correct guesses. 2000 Mathematics Subject Classification 05A15, 05A16, 60F05, 60C05 1. Introduction 1.1. Shuffling techniques and card guessing games The shuffling of cards and associated card guessing games have a long and rich history in mathematics at the intersection of combinatorics, probability theory and statistics, dating back to work of Markov [ 24 ] and Poincare [ 27 ] . Famous shuffling techniques include the riffle shuffle [ 1 , 9 , 13 ] , also called dove-tail shuffling, as well as the shelf shuffle [ 4 , 5 ] ; we refer the reader to [ 28 ] for references concerning other shuffling techniques such as the Thorpe shuffle and the clumpy shuffle and to [ 18 ] for the Monge shuffle. Additionally, we refer to the book of Diaconis and Fulman [ 7 ] for many more references. The different card shuffling techniques and their analysis are not only of purely mathematical interest. There are applications to the analysis of clinical trials [ 2 , 10 ] , fraud detection related to extra-sensory perceptions [ 6 ] , guessing so-called Zener Cards [ 25 ] , as well as relations to tea tasting and the design of statistical experiments [ 11 , 26 ] . In this work we analyze the shelf shuffle, as introduced by Diaconis, Fulman and Holmes [ 8 ] . Its importance stems from card shuffling machines called shelf-shuffler, which play an important role in the theory of card guessing, as sch machines have direct practical applications to casino gambling and manufacturing. A standard shuffling machine employs ten shelves. In a shuffling machine the cards are drawn from the top of the deck. Each card is placed, uniformly at random, on a shelf. The decision to place the card on the top or bottom of the existing pile on the shelf is also done randomly. The shelves are then removed and the cards are pressed together, forming a shuffled deck. Clay [ 4 ] analyzed properties of a single shelf shuffle, including a card guessing game with complete feedback. An ordered deck of n cards labeled 1 up to n is shelf-shuffled exactly one time. Then, one after the other a single card is drawn from the shuffled deck. The guesser wants to correctly guess the label of the drawn cards to maximze the number of correct guesses. The person gets full feedback after the guess: the card is always shown until no cards remain. Let X_{n} denote the number of correct guesses in the full feedback card guessing game after a single shelf shuffle. Clay obtained the expected value of X_{n} and showed that {\mathbb{E}}(X_{n})=\frac{3}{4}\cdot n . We note here in passing that similar questions recently received very much attention and mention a few corresponding works for the riffle shuffle [ 3 , 19 , 20 , 21 , 23 ] and also refer to the recent work of Tripathi [ 29 ] and of Clay [ 5 ] for related problems. The purpose of this work is to extend the analysis of X_{n} and to obtain the distribution, the variance, as well as a central limit theorem for X_{n} . Additionally, we introduce a biased, asymmetric shelf shuffle with parameter p\in(0,1) and show how to extend the analysis to this case and also uncovering a phase transition for p\to 1 . Finally, motivated by other card guessing games [ 22 ] we also discuss a refined analysis of X_{n} : correct guesses are either pure luck L_{n} , as they occur with probability one-half, or they are certified correct guesses C_{n} with probability one. Thus, the random variable X_{n} decomposes into the random variables L_{n} and C_{n} , counting pure luck and certified correct guesses, respectively: X_{n}=L_{n}+C_{n}. We study the joint distribution of both random variables, shedding more light into the distribution of X_{n} ; in particular, we prove that exactly n/2 guesses are expected to certified correct and n/4 to be pure luck, refining {\mathbb{E}}(X_{n})=\frac{3}{4}\cdot n . 1.2. Notation As a remark concerning notation used throughout this work, we always write X\law Y to express equality in distribution of two random variables (r.v.) X and Y , and X_{n}\claw X for the weak convergence (i.e., convergence in distribution) of a sequence of random variables X_{n} to a r.v. X . Furthermore we use x^{\underline{s}}:=x(x-1)\dots(x-(s-1)) for the falling factorials, and x^{\overline{s}}:=x(x+1)\dots(x+s-1) for the rising factorials, s\in\mathbb{N}_{0} . Moreover, f_{n}\ll g_{n} denotes that a sequence f_{n} is asymptotically smaller than a sequence g_{n} , i.e., f_{n}=o(g_{n}) , n\to\infty , and f_{n}\gg g_{n} the opposite relation, g_{n}=o(f_{n}) . 2. Shelf Shuffling We begin by recalling the definition of the shelf shuffle with a single shelf. Definition 1 (Single-shelf shuffle) . Given an ordered deck of n cards labelled one up to n . Cards are drawn from the bottom of the deck and placed in a pile or on a shelf. When a card is drawn, it is placed at the top or at the bottom of the pile with probability 1/2. An important intermediate result for our analysis is the so-called position matrix, encoding the positions of each card after one shelf shuffle. We collect the result of [ 4 ] . Lemma 1 (Position matrix of a single shelf shuffle) . Suppose a deck of n cards is shuffled once in a shelf-shuffler with one shelf. Let m_{i,j} be the probability that card i lands in position j . Then, we have m_{i,j}=\frac{\binom{i-1}{j-1}+\binom{i-1}{n-j}}{2^{i}},\qquad 1\leq i\leq n,\quad 1\leq j\leq n, with the convention that \binom{0}{0}=1 and \binom{0}{k}=0 for all positive integers k . In particular, m_{i,j}=0 if and only if 1\leq j\leq n-i , and m_{i,n-j+1}=m_{i,j} for all i,j . For the reader’s convenience and to make this work more self-contained we include the very short argument [ 4 ] . Proof. Cards are always drawn from the bottom of the ordered deck. Thus, immediately before selecting the card labelled i we have exactly n-i cards in the pile. The i th card is placed at the bottom or the top of the pile with probability 1/2. If the card is placed at the top, we select j-1 cards from the remaining i-1 cards and place them at the top. If the card is placed at the bottom, we may choose n-j cards from the remaining i-1 cards and place them at the bottom. As these events are disjoint, the result readily follows. ∎ The distribution of the first card \fc is simply given by m_{i,1} , 1\leq i\leq n : {\mathbb{P}}\{\fc=i\}=m_{i,1}=\frac{1+\delta_{i,n}}{2^{i}}, (1) where \delta_{k,\ell} denotes the Kronecker-delta. Thus, the optimal strategy follows directly from Lemma 1 . Proposition 1 (Optimal strategy for full feedback) . Suppose a deck of n cards is given a shelf shuffle with a single shelf, and the player is given complete feedback. The player should guess card labelled one as the first guess and then always the card immediately following the previously shown card in all other positions. Once one of card n-1 or n is first shown, the player should guess the remaining cards in descending order, and is guaranteed to get these correct. The following example highlights the optimal strategy. Example 1 . For example, if n=20 , say, and the first cards that come out are, in order, 1, 2, 5, 10, 11, 19, the player will have guessed cards 1, 2, 3, 6, 11, 12 under the optimal strategy and have gotten cards 1, 2, 11 correct. After this, the player will guess cards 20, 18, 17, 16, 15, 14, 13, 12, 9, 8, 7, 6, 4, 3 and get them all correct. 3. Distributional analysis In [ 4 ] an elaborate probabilistic formulation of the guessing strategy with complete feedback is given using maps of sequences and in terms of the filtration generated by the cards that have already appeared. Although natural, as the information available to the player is increasing with respect to time, is seems more difficult to perform a distributional analysis using this point of view, apart from the expected value. We proceed in a different way, setting up a stochastic recurrence relation for the number of correct guesses X_{n} . This recurrence relation is then solved using generating functions. The benefit of this point of approach is that it is robust enough to be generalized to an asymmetric shelf shuffle. 3.1. Recursive description The key to our analysis is the following recurrence relation. Theorem 2 . The random variable X=X_{n} of correctly guessed cards, starting with a deck of n cards, after a one-time shelf shuffle satisfies for n\geq 2 the following distributional equation: X_{n}\law I_{1}\big(X^{\ast}_{n-1}+1\big)+(1-I_{1})(X^{\ast}_{n-J_{n}}+J_{n}-1), (2) with initial values X_{1}=1 and X_{0}=0 and {\mathbb{P}}\{J_{n}=i\}=\frac{1+\delta_{i-n}}{2^{i-1}},\quad 2\leq i\leq n. Here, X^{\ast} denotes an independent copy of X and the random variables appearing in the decomposition are mutually independent, with I_{1}\law\Be(1/2) denoting a Bernoulli distribution. Proof. We guess the card labelled one with probability 1/2 correctly. Otherwise, we draw any card i of the remaining n-1 cards with probability ( 1 ). As pointed out in the optimal strategy in Proposition 1 once we have observed card i , we know where the cards 1,2,\dots,i-1 are and these guesses are certified correct. Thus, we the only source of randomness are the correct guesses in the remaining n-i cards. As the shuffle is generated by a sequence of n-1 independent Bernoulli trials, this leads to an independent copy of X^{\ast} of X with a smaller number n-i of cards. ∎ 3.2. Distributional analysis Let s_{n}(v)={\mathbb{E}}(v^{X_{n}}) denote the probability generating function of X_{n} . From Theorem 2 we obtain for n\geq 2 by taking expectations the recurrence relation s_{n}(v)=\frac{1}{2}vs_{n-1}(v)+\frac{1}{2}\sum_{k=2}^{n-1}\frac{1}{2^{k-1}}v^{k-1}s_{n-k}(v)+\frac{1}{2}\cdot\frac{1}{2^{n-1}}\cdot 2s_{0}(v)v^{n-1}, (3) with initial values s_{0}(v)=1 and s_{1}(v)=v . Let S_{(}z,v) denote the generating function of the s_{n}(v) , defined S(z,v)=\sum_{n\geq 1}{\mathbb{E}}(v^{X_{n}})z^{n}. Lemma 3 . The bivariate generating function S(z,v) of the number of correct guesses after a single shelf shuffle with complete feedback is given by S(z,v)=\frac{zv+\frac{\frac{z^{2}v}{2}}{1-\frac{zv}{2}}}{1-\frac{zv}{2}-\frac{\frac{z}{2}}{1-\frac{zv}{2}}+\frac{z}{2}}=\frac{2zv\big(2+(1-v)z\big)}{4-4vz+(v^{2}-v)z}. Proof. From the recurrence relation ( 3 ) we get first \begin{split}s_{n}(v)z^{n}&=\frac{zv}{2}\cdot s_{n-1}(v)z^{n-1}+\frac{z}{2}\sum_{k=1}^{n-1}\frac{v^{k-1}z^{k-1}}{2^{k-1}}\big(s_{n-k}(v)z^{n-k}\big)-\frac{z}{2}s_{n-1}(v)z^{n-1}\\ &\qquad+z\frac{(zv)^{n-1}}{2^{n-1}}.\end{split} (4) Summing up over n\geq 2 translates the recurrence relation to the equation S(z,v)-zv=\frac{zv}{2}\cdot S(z,v)+\frac{z}{2}\frac{S(z,v)}{1-\frac{zv}{2}}-\frac{z}{2}S(z,v)+\frac{z^{2}v/2}{1-zv/2}, and furthermore to \Big(1-\frac{zv}{2}-\frac{\frac{z}{2}}{1-\frac{zv}{2}}+\frac{z}{2}\Big)\cdot S(z,v)=zv+\frac{\frac{z^{2}v}{2}}{1-\frac{zv}{2}}. This leads to an explicit expression, which is then readily simplified (using a computer algebra system) to the stated form. ∎ 3.3. Expectation, variance and limit law The expected value and the variance of X_{n} can be obtained from the generating function S(z,v) : {\mathbb{E}}(X_{n})=[z^{n}]\partial_{v}S(z,1),\quad{\mathbb{V}}(X_{n})=[z^{n}]\big(\partial_{v}^{2}S(z,1)\big)+{\mathbb{E}}(X_{n})-{\mathbb{E}}(X_{n})^{2}. Here, [z^{n}] denotes as usual the extraction of coefficients operator [ 12 ] . We also used a short-hand notation \partial_{v}S(z,1)=\big(\partial_{v}S(z,v)\big)|_{v=1}. After taking the derivative with respect to v and evaluation at v=1 we obtain from Lemma 3 \partial_{v}S(z,1)=\frac{z(z^{2}-2z+4)}{4(1-z)^{2}}=z+\sum_{n=2}^{\infty}\frac{3}{4}\cdot n\cdot z^{n}. Similarly, we obtain \partial_{v}^{2}S(z,1)=\frac{z^{2}(z^{3}-2z^{2}-8)}{8(z-1)^{3}}, and thus the second factorial moment {\mathbb{E}}(X_{n}^{\underline{2}}) . After partial fraction decomposition and the standard identity \frac{1}{(1-z)^{m+1}}=\sum_{n\geq 0}\binom{n+m}{m}z^{n}, as well as the classical formula {\mathbb{V}}(X_{n})={\mathbb{E}}(X_{n}^{\underline{2}})+{\mathbb{E}}(X_{n})-{\mathbb{E}}(X_{n})^{2}. (5) we arrive at the following result. Theorem 4 . The random variable X=X_{n} of correctly guessed cards, starting with a deck of n cards, after a one-time shelf shuffle satisfies {\mathbb{E}}(X_{n})=\frac{3}{4}\cdot n,\quad n\geq 2,\quad\text{with }{\mathbb{E}}(X_{1})=1. Furthermore, {\mathbb{V}}(X_{n})=\frac{n}{16},\quad n\geq 3,\quad\text{with }{\mathbb{V}}(X_{1})=0,\quad{\mathbb{V}}(X_{2})=\frac{1}{4}. Next we turn to the limit law for X_{n} . For the derivation of the limit law we use Hwang’s quasi-power theorem [ 15 , 17 ] . First, we state our result. Theorem 5 . The random variable X=X_{n} of correctly guessed cards, starting with a deck of n cards, after a one-time shelf shuffle satisfies a central limit theorem \frac{X_{n}-\frac{3}{4}n}{\sqrt{n}/4}\to\mathcal{N}(0,1). For the proof of this result we turn to the quasi-power theorem in the formulation of [ 12 ] . Given a function f(v) analytic at v=1 and assumed to satisfy f(1)\neq 0 , we set \mathfrak{m}(f)=\frac{f^{\prime}(1)}{f(1)},\qquad\mathfrak{v}(f)=\frac{f^{\prime\prime}(1)}{f(1)}+\frac{f^{\prime}(1)}{f(1)}-\left(\frac{f^{\prime}(1)}{f(1)}\right)^{2}. (6) The quantities \mathfrak{m}(f) and \mathfrak{v}(f) are called the analytic mean and analytic variance of function f [ 12 ] . We collect the following result. Theorem 6 (Hwang’s quasi-powers Theorem) . Let the X_{n} be non-negative discrete random variables, supported by \mathbb{Z}_{\geq 0} , with probability generating functions p_{n}(u) . Assume that, uniformly in a fixed complex neighbourhood of v=1 , for sequences \beta_{n},\kappa_{n}\to+\infty , one has {\mathbb{E}}(v^{X_{n}})=A(v)\,B(v)^{\beta_{n}}\left(1+O\!\left(\frac{1}{\kappa_{n}}\right)\right), where A(u) , B(u) are analytic at u=1 and A(1)=B(1)=1 . Assume finally that B(u) satisfies the so-called variability condition, \mathfrak{v}(B(v))=B^{\prime\prime}(1)+B^{\prime}(1)-B^{\prime}(1)^{2}\neq 0. Under these conditions, the mean and variance of X_{n} satisfy \mu_{n}=\mathbb{E}(X_{n})=\beta_{n}\mathfrak{m}(B(v))+\mathfrak{m}(A(v))+O\!\left(\kappa_{n}^{-1}\right), \sigma_{n}^{2}=\mathbb{V}(X_{n})=\beta_{n}\mathfrak{v}(B(v))+\mathfrak{v}(A(v))+O\!\left(\kappa_{n}^{-1}\right). The distribution of X_{n} is, after standardization, asymptotically Gaussian, and the speed of convergence to the Gaussian limit is \mathcal{O}\left(\kappa_{n}^{-1}+\beta_{n}^{-1/2}\right) : \mathbb{P}\left\{\frac{X_{n}-\mathbb{E}(X_{n})}{\sqrt{\mathbb{V}(X_{n})}}\leq x\right\}=\Phi(x)+\mathcal{O}\left(\frac{1}{\kappa_{n}}+\frac{1}{\sqrt{\beta_{n}}}\right), where \Phi(x) is the distribution function of a standard normal, \Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-v^{2}/2}\,dv. Proof of Theorem 5 . We analyze the singular structure of S(z,v) . The denominator 4-4vz+(v^{2}-v)z has two roots \rho_{1}(v) and \rho_{2}(v) \rho_{1}(v)=\frac{2(v-\sqrt{v})}{v(v-1)},\quad\rho_{2}(v)=\frac{2(v+\sqrt{v})}{v(v-1)}, with dominant singularity \rho(v)=\rho_{1}(v) , satisfying \lim_{v\to 1}\rho(v)=1 . The quasi-power theorem applies because the dominant singularity \rho(v) is simple and analytic near v=1 ,. and S(z,v) is analytic except at z=\rho(v) . We expand S(z,v) around z=\rho(v) , for v close to 1 , obtaining the singular expansion S(z,v)\sim\frac{A(v)}{1-\frac{z}{\rho(v)}},\quad A(v)\neq 0. By standard contour integration we get the desired expansion of s_{n}(v)={\mathbb{E}}(v^{X_{n}}) : {\mathbb{E}}(v^{X_{n}})=[z^{n}]S(z,v)\sim\frac{A(v)}{\rho(v)^{n}}. Application of the Quasi-Power theorem then leads to the stated result; one may also check that the asymptotics \beta_{n}\mathfrak{m}(B(v))=3n/4 and \beta_{n}\mathfrak{v}(B(v))=n/16 . ∎ Finally, we note that the powerful theorems of Hwang [ 16 ] also directly leads to a large deviation principle. 4. Extensions 4.1. Asymmetric shelf shuffle An obvious question is how robust the presented approach is. Consider the following biased asymmetric shelf shuffle Definition 2 (Asymmetric Single-shelf shuffle) . Given an ordered deck of n cards labelled one up to n and a parameter p\in(0,1) . Cards are drawn from the bottom of the deck and placed in a pile. When a card is drawn, it is placed at the top with probability p and at the bottom of the pile with probability 1-p . Our aim is to maximize again the number of correct guesses. We require the distribution of the first drawn card. Lemma 7 . The distribution of the first card \fc_{n} in a single asymmetric shelf shuffle with parameter p\in(0,1) is given by as follows: {\mathbb{P}}\{\fc_{n}=i\}=p(1-p)^{i-1},\quad 1\leq i\leq n-1 (7) and {\mathbb{P}}\{\fc_{n}=n\}=(1-p)^{n-1}. Proof. For i , with 1\leq i\leq n-1 , landing on top, we must have a successful coin toss with probability p , and then i-1 unsuccessful tosses. For n ending on top we require all other cards to be below. ∎ Of course, we can also obtain the complete position matrix, which is double stochastic. Proposition 2 (Position matrix of a single asymmetric shelf shuffle) . Suppose a deck of n cards is shuffled once in an asymmetric shelf-shuffler with one shelf with parameter p . Let m_{i,j} be the probability that card i lands in position j . Then, we have m_{i,j}=p^{j}(1-p)^{i-j}\binom{i-1}{j-1}+p^{i-1-(n-j)}(1-p)^{n-j+1}\binom{i-1}{n-j}, for 1\leq i\leq n-1 and 1\leq j\leq n . For i=n we have m_{n,j}=p^{j-1}(1-p)^{n-j}\binom{n-1}{j-1},\quad 1\leq j\leq n. Here, we used again the convention that \binom{0}{0}=1 and \binom{0}{k}=0 for all positive integers k . In particular, m_{i,j}=0 if and only if 1\leq j\leq n-i , and m_{i,n-j+1}=m_{i,j} for all i,j . Proof. We readily adapt the argument from the case p=1/2 . Immediately before selecting the card labelled i we have exactly n-i cards in the pile. The i th card is placed at the bottom with probability 1-p or the top of the pile with probability p . If the card is placed at the top, we select j-1 cards from the remaining i-1 cards and place them at the top, leading to a common factor p^{j}(1-p)^{i-j} and the number of ways to choose the j-1 cards. If the card is placed at the bottom, we may choose n-j cards from the remaining i-1 cards and place them at the bottom. This gives a common factor p^{i-1-(n-j)}(1-p)^{n-j+1} , which takes into account that i went to the bottom, as well as n-j cards too, and the remaining cards to the top. As these events are disjoint, the result readily follows. ∎ For \frac{1}{2}\leq p<1 we can carry out analysis as before, as the optimal strategy stays the same, but for p<\frac{1}{2} the structure is asymptotically similar, but the optimal strategy changes, as we do not always guess the number one, as the guess depends on the value of p . Apparently, we have to study the equation p=(1-p)^{n-1} , allowing us to distinguish which label appear with the highest probability. Let \nu=\lfloor\ln(p)/\ln(1-p)\rfloor+1 . Given a value of n with 2\leq n\leq\nu , we guess always the largest label n , but for all n>\nu we guess the smallest label one. We note again that once card n-1 or n is first shown, the player should guess the remaining cards in descending order, and is guaranteed to get these correct. After the first guess, we notice the label j of the shown card. We now immediately know the positions of cards labelled one up to j-1 . Concerning randomness we replace n by n-j and continue similar to starting with a set of n-j cards by comparing n-j to \nu in order to make our choice for the next guess. Then, we continue the guessing, adding the number j to our guess, as we actually have the set of labels j+1,\dots,n left. We continue until n-1 or n is shown and then correctly guess all the remaining cards. Example 2 (Non-uniqueness of optimal strategy) . Consider the case of n=4 cards and the equation p=(1-p)^{3} . It has a real solution p^{\ast}=\frac{1}{6}\left(2^{2/3}\sqrt[3]{\sqrt{93}-9}-2^{2/3}\sqrt[3]{9+\sqrt{93}}+6\right)\approx 0.31767<1/2 and thus the optimal strategy is not unique, as we can either guess one or four. Example 3 . Consider the case of n=4 cards. For any p
\nu.\end{cases} After the card, say labelled j is shown to the guesser, we proceed in a similar way, but with a reduced set of indices \{1,\dots,n-j\} and guess the label corresponding to the maximum of \{p,(1-p)^{n-j}\} , shifted of course by j . Thus, the distributional equation has a slightly different form. We can group the two cases together by using a suitably defined indicator variable. Theorem 9 . The random variable X=X_{n} of correctly guessed cards, starting with a deck of n cards, after an asymmetric one-time shelf shuffle with parameter p\in(0,1) satisfies for n\geq 2 the following distributional equation: X_{n}\law X^{\ast}_{n-\fc_{n}}+\fc_{n}-1+\mathbb{I}_{n}(\fc_{n}=\maxP_{n}), (8) with initial values X_{1}=1 and X_{0}=0 and the random variable \fc as stated in ( 1 ). Here, \mathbb{I}_{n}(\fc_{n}=\maxP_{n}) denotes the indicator of the event that the guess is correct and X^{\ast} denotes an independent copy of X and the random variables appearing in the decomposition are mutually independent. As mentioned before, for p\geq\frac{1}{2} we always have \maxP_{n}=1 , and the distributional equation can be written as X_{n}\law I_{1}\big(X^{\ast}_{n-1}+1\big)+(1-I_{1})(X^{\ast}_{n-J_{n}}+J_{n}-1), (9) with I_{1}\law\Be(p) denoting a Bernoulli distribution and initial values X_{1}=1 and X_{0}=0 and {\mathbb{P}}\{J_{n}=i\}=p(1-p)^{i-2},\quad 2\leq i\leq n-1,\quad{\mathbb{P}}\{J_{n}=n\}=(1-p)^{n-2}. The generating functions approach works directly exactly the same and we obtain for S(z,v)=S(z,v;p)=\sum_{n\geq 1}{\mathbb{E}}(v^{X_{n}})z^{n} the following result. S(z,v)=\frac{-z\big(1+(v-1)(p-1)z\big)v}{zv-1+pv(v-1)(p-1)z^{2}} We obtain by extraction of coefficients from \partial_{v}S(z,1) and \partial_{v}^{2}S(z,1) for the expected value and the variance for n\geq 3 and \frac{1}{2}\leq p<1 the results \displaystyle{\mathbb{E}}(X_{n}) \displaystyle=(1-p+p^{2})n+3p-1-2p^{2}, \displaystyle{\mathbb{V}}(X_{n}) \displaystyle=(1-p)p(3p^{2}-3p+1)n+p(1-p)(10p-8p^{2}-3). The denominator is readily factorized and we obtain the dominant singularity \rho(v) , depending on \frac{1}{2}\leq p<1 \rho(v)=\frac{-v+\sqrt{(1+4p(p-1))(v^{2}-v)+v}}{2vp(pv-p-v+1)}. We can readily obtain a central limit theorem using the quasi-power theorem, such that \frac{X_{n}-\mu_{n}}{\sigma_{n}}\to\mathcal{N}(0,1), with \mu_{n}={\mathbb{E}}(X_{n}) , \sigma_{n}^{2}={\mathbb{V}}(X_{n}) ; details are omitted. Of interest is also the transition at p=1 . Here, we deterministically have X_{n}=n . Thus, we set p=1-\frac{\lambda}{n^{\alpha}} , with real \alpha,\lambda>0 , which approaches one as n tends to infinity. The transition can be easily observed by looking at the probability {\mathbb{P}}\{X_{n}=n\} , as it satisfies for p=1-\frac{\lambda}{n^{\alpha}} , \alpha,\lambda>0 and n\to\infty the expansions {\mathbb{P}}\{X_{n}=n\}\to\begin{cases}1,\quad 0<\alpha<1,\\ e^{-\lambda},\quad\alpha=1,\\ 0,\quad\alpha\geq 1,\end{cases} which follows directly from the explicit formula {\mathbb{P}}\{X_{n}=n\}=p^{n} and the \exp-\log expansion. More refined, we additionally anticipate here a phase transition for the shifted random variable Z_{n}=n-X_{n} depending on the value of \alpha from degenerated, to a discrete distribution, and then to a normal distribution. We expect a classical \Po(\lambda) discrete limit in the case \alpha=1 , motivated by the corresponding expansions of the expected value and the variance in this range {\mathbb{E}}(X_{n})\sim n-c+\mathcal{O}\big(\frac{1}{n}\big),\quad{\mathbb{V}}(X_{n})\sim c+\mathcal{O}\big(\frac{1}{n}\big) This can be made precise by a closer inspection of the probability generating function using the dominant singularity; details are again omitted. In the case of 0
\nu. Let T=T(z,v)=\sum_{n\geq 1}{\mathbb{E}}(v^{Y_{n}})z^{n} . We obtain the equation T-zv=zpT+\frac{zpT}{1-zv(1-p)}-zpT+\frac{z^{2}v^{2}(1-p)}{1vz(1-p)}, which leads to a very simple explicit expression for T : T(z,v)=\frac{zv}{1-z\big(p+(1-p)v\big)}, such that Y_{n} , and consequently also X_{n} for n\leq\nu , is given by a sum of n-1 iid Bernoulli random variables B_{k}\law\Be(1-p) shifted by one: X_{n}\law 1+\sum_{k=1}^{n-1}B_{k}\law 1+\Bin(n-1,1-p),\quad 1\leq n\leq\nu. Then, we use again generating functions for treating ( 8 ). As before, let S=S(z,v)=\sum_{n\geq 1}{\mathbb{E}}(v^{X_{n}})z^{n} , which splits into two parts \displaystyle S(z,v)=S_{\leq\nu}(z,v)+S_{>\nu}(z,v)=\sum_{n=1}^{\nu}{\mathbb{E}}(v^{X_{n}})z^{n}+\sum_{n>\nu}{\mathbb{E}}(v^{X_{n}})z^{n}, (11) with S_{\leq\nu}(z,v)=\sum_{n=1}^{\nu}{\mathbb{E}}(v^{X_{n}})z^{n} already known from T(z,v) : S_{\leq\nu}(z,v)=\sum_{n=1}^{\nu}{\mathbb{E}}(v^{Y_{n}})z^{n}=zv\frac{1-z^{\nu}\big(p+(1-p)v\big)^{\nu}}{1-z\big(p+(1-p)v\big)}. (12) From ( 8 ) we obtain the equation \displaystyle S(z,v)-zv \displaystyle=pz\big(S_{\leq\nu}(z,v)-(1-v)s_{\nu}(v)+vS_{>\nu}(z,v)\big) \displaystyle\quad+\frac{zpS(z,v)}{1-zv(1-p)}-zpS(z,v)+\sum_{n\geq 2}(1-p)^{n-1}v^{n-1+\mathbb{I}_{n}(n\leq\nu)}z^{n}. This allows to characterize S_{>\nu}(z,v) , and thus the distribution of X_{n} in terms of the S_{\leq\nu}(z,v) ( 12 ) and s_{\nu}(v)=v(p+v(1-p))^{\nu-1} : \displaystyle S_{>\nu}(z,v) \displaystyle=\frac{zv+(pz-1)S_{\leq\nu}(z,v)-p(1-v)zs_{\nu}(v)+\frac{zpS_{\leq\nu}(z,v)}{1-zv(1-p)}-zpS_{\leq\nu}(z,v)}{1-pzv-\frac{zp}{1-zv(1-p)}+zp} \displaystyle\quad+\frac{1}{1-pzv-\frac{zp}{1-zv(1-p)}+zp}\sum_{n\geq 2}(1-p)^{n-1}v^{n-1+\mathbb{I}_{n}(n\leq\nu)}z^{n}. 4.2. Refined analysis of the ordinary shelf shuffle As outlined in the introduction, we turn to a refined analysis of X_{n} , by keeping track of the pure luck L_{n} and the certified correct guesses C_{n} . We continue and refine Example 1 . Example 4 . If n=20 the first cards that come out are, in order, 1, 2, 5, 10, 11, 19, the player will have guessed cards 1, 2, 3, 6, 11, 12 under the optimal strategy and have gotten cards 1, 2, 11 correct. After this, the player will guess cards 20, 18, 17, 16, 15, 14, 13, 12, 9, 8, 7, 6, 4, 3 and get them all correct. Thus, here we have three pure luck guesses and 14 certified correct guesses. Of course, the distributional equation of Theorem 2 is readily refined to keep track of the random vector (L_{n},C_{n}) : \binom{L_{n}}{C_{n}}\law I_{1}\binom{L^{\ast}_{n-1}+1}{C^{\ast}_{n-1}}+(1-I_{1})\binom{L^{\ast}_{n-J_{n}}}{C^{\ast}_{n-J_{n}}+J_{n}-1}, (13) for n\geq 2 with L_{1}=L_{0}=0 , C_{1}=1 and C_{0}=0 . Here, we have again {\mathbb{P}}\{J_{n}=i\}=\frac{1+\delta_{i-n}}{2^{i-1}},\quad 2\leq i\leq n. Let s_{n}(v,w)={\mathbb{E}}(v^{L_{n}}w^{C_{n}}) , such that s_{n}(v,v)={\mathbb{E}}(v^{L_{n}+C_{n}})={\mathbb{E}}(v^{X_{n}}). We obtain for n\geq 2 by taking expectations the recurrence relation s_{n}(v,w)=\frac{1}{2}vs_{n-1}(v,w)+\frac{1}{2}\sum_{k=2}^{n-1}\frac{1}{2^{k-1}}w^{k-1}s_{n-k}(v,w)+\frac{1}{2}\cdot\frac{1}{2^{n-1}}\cdot 2s_{0}(v,w)w^{n-1}, (14) with initial values s_{0}(v,w)=1 and s_{1}(v,w)=w . Let S_{(}z,v,w) denote the generating function of the s_{n}(v,w) , defined by S(z,v,w)=\sum_{n\geq 1}{\mathbb{E}}(v^{L_{n}}w^{C_{n}})z^{n}. Summing up over n\geq 2 translates the recurrence relation to the equation S(z,v,w)-zw=\frac{zv}{2}\cdot S(z,v)+\frac{z}{2}\frac{S(z,v,w)}{1-\frac{zw}{2}}-\frac{1}{2}S(z,v,w)+\frac{z^{2}w/2}{1-zw/2}, leading to the following result. Lemma 10 . The trivariate generating function S(z,v,w) of the number of correct guesses decomposed into pure luck guesses and certified correct guesses after a single shelf shuffle with complete feedback is given by S(z,v,w)=\frac{zw+\frac{\frac{z^{2}w}{2}}{1-\frac{zw}{2}}}{1-\frac{zv}{2}-\frac{\frac{z}{2}}{1-\frac{zw}{2}}+\frac{z}{2}}=\frac{2zw\big(2+(1-w)z\big)}{4+w(v-1)z^{2}-2z(v+w)}. From this generating function we readily obtain various results. First, we turn to the expectation, variance and covariance of L_{n} and C_{n} . They are obtained by extraction of coefficients from \partial_{v}S(z,1,w),\quad\partial_{w}S(z,v,1), as well as \partial_{v}^{2}S(z,1,w),\quad\partial_{w}^{2}S(z,v,1),\quad\partial_{w}\partial_{v}S(z,1,1), using the identity ( 5 ). We omit the computations. Theorem 11 . The random variables L_{n} and C_{n} , counting the pure luck L_{n} and the certified correct guesses C_{n} in the card guessing game with full feedback after a single shelf shuffle satisfy {\mathbb{E}}(L_{n})=\frac{n}{4},\quad{\mathbb{E}}(C_{n})=\frac{n}{2},\quad n\geq 2. Moreover, {\mathbb{V}}(L_{n})=\frac{5n}{16},\quad{\mathbb{V}}(C_{n})=\frac{n}{4},\quad\Cov(L_{n},C_{n})=-\frac{n}{4},\quad n\geq 3. Finally, we note that the denominator of S(z,v,w) has a particularly simple form: \begin{split}w(v-1)z^{2}-2z(v+w)+4&=w(v-1)\big(z-\rho_{1}(v,w)\big)\big(z-\rho_{2}(v,w)\big)\\ &=4\big(1-z/\rho_{1}(v,w)\big)\big(1-z/\rho_{2}(v,w)\big),\end{split} with \rho_{1}(v,w)=\frac{v+w-\sqrt{(v-w)^{2}+4w}}{(v-1)w},\quad\rho_{2}(v,w)=\frac{v+w+\sqrt{(v-w)^{2}+4w}}{(v-1)w}. The dominant singularity around v=w=1 is \rho=\rho_{1}(v,w) , which satisfies \lim_{v,w\to 1}\rho(v,w)=1. Here, one may apply the higher dimensional quasi-power theorem analogs of Heuberger and Kropf [ 14 ] , leading to a central limit theorem, with variance-covariance governed by ( 11 ). We omit the details. 4.3. Refined analysis of the asymmetric shelf shuffle Finally, we note that both ideas, asymmetric shelf shuffle and refined number of correct guesses, can be combined. For \frac{1}{2}\leq p<1 this leads to the distributional equation \binom{L_{n}}{C_{n}}\law I_{1}\binom{L^{\ast}_{n-1}+1}{C^{\ast}_{n-1}}+(1-I_{1})\binom{L^{\ast}_{n-J_{n}}}{C^{\ast}_{n-J_{n}}+J_{n}-1}, (15) for n\geq 2 with L_{1}=L_{0}=0 , C_{1}=1 and C_{0}=0 , and I_{1}=\Be(p) . We only state the corresponding generating function S(z,v,w)=S(z,v,w,p) : S(z,v,w)=\frac{zv\big(1+(v-1)(-1+p)z\big)}{1-pv(w-1)(-1+p)z^{2}-(1-p)v+wpz}, from which results for the expected values, variances and the covariance can readily be obtained, as well as distributional results. It is also possible to extend this analysis to the case 0