Expected number of draws to obtain a soft streak

From papers

Let consecutive letters be drawn uniformly from the alphabet {1,2,,n}\{1,2,\ldots,n\}, and stop when a soft streak of length kk—that is, a non-decreasing word of length kk—is obtained. Let ψk,r\psi_{k,r} and ωk\omega_k be the quantities used in the preceding generating-function identities. Then the expected number of letters drawn is

Esoft(n,k)=(1nk)nr=0(k1)nψk,rBs(n,k,r)nrE_{\mathrm{soft}}(n,k)=\frac{(1-n^{-k})^n}{\displaystyle\sum_{r=0}^{(k-1)n}\psi_{k,r}\operatorname{B}_s(n,k,r)n^{-r}}

and equivalently

Esoft(n,k)=ks=1k1(1ωks)(1ωksn)n.E_{\mathrm{soft}}(n,k)=\frac{k}{\displaystyle\sum_{s=1}^{k-1}(1-\omega_k^{-s})\left(1-\frac{\omega_k^s}{n}\right)^{-n}}.

Expected-number conjecture. The expected number of letters drawn is given by these two equivalent expressions.

This is presented as a corollary of the generating-function method and extends the preceding theorem for strictly increasing streaks to soft streaks. The supplied excerpt does not provide evidence that the conjecture has been resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Senan Sekhon, “Counting words without strictly increasing subwords of fixed length”, arXiv:2511.13287 (2025).

Solutions 0

No solutions have been posted yet.