Concavity and sharp inequalities for a recursive sequence arising in game theory ✩

This paper is concerned with the sequence q(n) recursively defined as q(2) = ¼ and q(n)=n−1n(1−21/(1−n)+q(n−1)n/(n−1)),n=3,4..., where each q(n) represents certain winning probability in a secretary problem with horizon n. We show that this sequence is concave, as well as subadditive and supermultiplicative in a strong sense. We also present several sharp inequalities implying in particular that q(n) converges towards its limit at the rate n−1, as n→∞.