  We define and study the Plancherel-Hecke probability measure on Young
diagrams; the Hecke algorithm of [Buch-Kresch-Shimozono-Tamvakis-Yong '06] is
interpreted as a polynomial-time exact sampling algorithm for this measure.
Using the results of [Thomas-Yong '07] on jeu de taquin for increasing
tableaux, a symmetry property of the Hecke algorithm is proved, in terms of
longest strictly increasing/decreasing subsequences of words. This parallels
classical theorems of [Schensted '61] and of [Knuth '70], respectively, on the
Schensted and Robinson-Schensted-Knuth algorithms. We investigate, and
conjecture about, the limit typical shape of the measure, in analogy with work
of [Vershik-Kerov '77], [Logan-Shepp '77] and others on the ``longest
increasing subsequence problem'' for permutations. We also include a related
extension of [Aldous-Diaconis '99] on patience sorting. Together, these results
provide a new rationale for the study of increasing tableau combinatorics,
distinct from the original algebraic-geometric ones concerning K-theoretic
Schubert calculus.
