Expected number of query pings in a simple "concentration" game This question is based on a recently posted clever memory game (that uses $k=16$) that can be explained as follows:
There are $k$ cards numbered $1 \to k$ face down randomly ordered in a row.  You (the player) make one "ping" consisting of choosing any card you like, turning it over, and seeing its number.  If it is $1$, the card remains face up (remains "exposed"), but if it is any other number, the card is returned face down.  Then you repeat.  The only card that can become "exposed" is the one that has a value $1$ greater than the highest existing "exposed" card.  You continue until all $k$ cards have are "exposed."
In short, the sequence of cards that becomes "exposed" must be $1, 2, \ldots, k$.  
Your final score is your total number of pings.  The lower the number of pings, the better.  Thus of course you do your best to remember all cards you have turned over (but are not yet "exposed").
Clearly the optimal score is $k$, where by great luck you just happen to ping cards in the order $1, 2, \ldots , k$.  But this is quite rare.  (It occurs with probability $\prod\limits_{i=1}^k \frac{1}{i}$.)
Questions 


*

*Perfect memory:  If you assume you have perfect memory of any card you have seen, and you play optimally, what is your expected score (as a function of $k$)?

*No memory:  If you assume you have no memory of any previous card you have seen, what is your expected score (as a function of $k$)?  Of course you never ping an "exposed" card, but by "no memory" I mean you might indeed randomly choose a card you have previously turned over (even on the current "round"), even if it will not become "exposed."

*No memory but systematic search:  Assume you have no memory but after each successful ping (leading to an "exposed" card) you repeat your sequence of pings, always starting at the left of the line of cards and pinging each available non-exposed card to the right until hitting the one card that can be "exposed."  (This guarantees the number of pings per exposed card becomes lower and lower as the game progresses.)

 A: The perfect memory case is particularly interesting to me (not because I have perfect memory).
Let $E(k)$ be the expected number of pings.
The first pick is of course random. So you have $\frac 1 k$ probability of getting $1$, and the game becomes a game with $k - 1$ cards. This contributes $\frac 1 k (1 + E(k - 1))$ to the expected number of pings.
In the rest $\frac {k - 1}k$ probability, you know the value of another card, but have to turn it back; now it essentially becomes a game of $k - 1$ cards, but when it comes to the first card you pick, you have to spend one more step to turn it over again. Hence this contributes $\frac {k - 1}k(2 + E(k - 1))$ to the expected number of pings.
So finally we get $E(k) = \frac 1 k (1 + E(k - 1)) + \frac {k - 1}k (2 + E(k - 1)) = E(k - 1) + 2 - \frac1k$.
Writing $B(k) = E(k) - 2k$, we get $B(k) = B(k - 1) - \frac 1 k$. Also, from $E(0) = 0$ we have $B(0) = 0$, hence $B(k) = - \sum_{j = 1}^k\frac1j = -H_k$, where $H_k$ is the $k$-th harmonic number.
Therefore we have $E(k) = 2k - H_k$. Since $H_k$ is assymptotically the size of $\ln k$, we see that $E(k)$ is assymptotically $2k - \ln k$.
For $k = 16$, we have approximately $E(k) = 28.619271...$.
A: For no memory at all (not even short term memory)
for 1st card:  $\sum\limits_{r=1}^{\infty} \frac{r(k-1)^{r-1}}{k^r}\ = k$
for 2nd card: $k-1$
for 3rd card:  $k-2$ ..... 
Eventually the full answer is $k +(k-1) +(k-2) + \ldots = \frac{k(k+1)}{2}$.

For short memory (we don't flip same card twice until a new card is exposed) or as defined in 3rd question are same probability wise (as random arrangement picked one by one or you pick one by one randomly are same)
For first card it's $\sum\limits_{r=1}^k \frac{r}{k}= \frac{k+1}{2}$ 
(It is equally probable for 1 to occur in any of the k slots.)
For 2nd card:  $\frac{k}{2}$ ,3rd $\frac{(k-1)}{2}$......
The final answer is then:  $\frac{k^2 +3k}{4}$

For perfect memory
Let's say you picked 1 (probability $\frac{1}{k}$) in your first turn; now the problem effective reduces to the same thing for $k-1$ cards where the expected value becomes $E(k-1) + 1$
If picked $1$ in 2nd ping (again, probability $\frac{1}{k}$) in your first turn:  Let's say it was 3 (the first card) then you will directly pick 3 once you expose 2, so 3 will be picked 2 (actually no card is picked more than 2 times) times and for other $'k-2'$ cards is effective $E(k-2)$. So our expected value in this way is $E(k-2) +3$.  And so on....
So our final answer is $\frac{1+3+5......(2k-1) + E(1) + E(2) + \ldots + E(k-1)}{k}$
$= k +\sum\limits_{r=1}^{k-1} \frac{E(r)}{k}$
I have no idea how to solve this recurring sequence, but of course it can be evaluated computationally.
A: This is a somewhat different way of doing the perfect memory case that may be of interest.
Since the cards are dealt randomly, we get the same expectation if we turn the cards over from left to right, counting $1$ if the card is the smallest unseen card and counting $2$ if it is not.  
We always count $1$ for the one and we count $1$ for the two precisely when it follows the one, that is $\frac12$ the time.  We count $1$ for the three when it follows both the one and the two, that is, with probability $\frac13$.  In general, we count $1$ for card $k$ precisely when it the last (rightmost) among cards $1$ through $k$, that is, with probability $\frac1k$.  
This give an expectation of $$2n-\sum_{k=1}^n\frac1k=2n-H_n$$
