https://spherical-harmonics.hateblo.jp/entry/Kyodai/2025/Suri

2024.11.24記

[2] $n$ を $5$ 以上の自然数とする． $\rm K，O，T，Y$ が1文字ずつ書かれた4枚のカード $\fbox{K}，\fbox{O}，\fbox{T}，\fbox{Y}$ を用意する．この4枚のカードから1枚を引き，書かれた文字を記録し，戻すという操作を $n$ 回繰り返し，記録された順に文字を左から並べる．

このとき，並んだ $n$ 個の文字の中に連続した文字列「 $\rm KYOTO$ 」が現れる確率 $p_n$ が
$p_n\geqq 1-\left(\dfrac{1023}{1024}\right)^{n-4}$
を満たすことを示せ．

ただし，上の操作においては，それぞれのカードを毎回独立に，等しい確率で引くものとする．

本問のテーマ

文字列照合（における対象文字列の存在確率の下限）

2024.11.24記
$p_n\geqq 1-\left(\dfrac{1023}{1024}\right)^{n-4}$
という式から「余事象を考える」，「 $p_n$ を求めるのは面倒なので不等式にしていることから適当に評価をする」という方針が浮ぶ．

[解答]
並んだ $n$ 個の文字の中に連続した文字列「 $\rm KYOTO$ 」が１度も現れない確率 $q_n=1-p_n$ について考える．

記録された $n$ 個の文字の並び方は $4^n$ 通りでどの文字のパターンが登場する確率も $\dfrac{1}{4^n}$ で等しい．

並んだ $n$ 個の文字の中に連続した文字列「 $\rm KYOTO$ 」が現れないパターンの場合の数を $Q_n$ 通りあるとする．

新たに1文字加えたときに文字列「 $\rm KYOTO$ 」が完成するパターンは，最後の4文字が「 $\rm KYOT$ 」である $Q_{n-4}$ 通りだから， $Q_{n+1}=4Q_n-Q_{n-4}$ となるので両辺を $4^{n+1}$ で割ると
$q_{n+1}=q_n-\dfrac{q_{n-4}}{1024}$
が成立する．

ここで $q_n\geqq q_{n-4}$ (現れない確率は単調非増加である)により
$q_{n+1}\leqq q_n-\dfrac{q_{n}}{1024}=\dfrac{1023}{1024}q_n$
が成立するので
$q_{n}\leqq \left(\dfrac{1023}{1024}\right)^{n-5}q_5$ （ $n\geqq 5$ ）
が成立する．

今， $p_5$ は $\rm K，Y，O，T，O$ の順に引かれる確率だから $\left(\dfrac{1}{4}\right)^5=\dfrac{1}{1024}$ となるので $q_5=\dfrac{1023}{1024}$ であるから
$q_{n}\leqq \left(\dfrac{1023}{1024}\right)^{n-4}$ （ $n\geqq 5$ ）
となり，
$p_n\geqq 1-\left(\dfrac{1023}{1024}\right)^{n-4}$
を満たす．