I'm reading Durrett's Probability : Theory and Examples and in the Subadditive Ergodic Theorem Chapter I'm trying to solve the exercise about bounding the limit of the longest common subsequence derived from the subadditive ergodic theorem:
This is what we have: Let $ X_1,X_2,X_3$ and $Y_1,Y_2,Y_3$ be iid Ber(1/2). Then define $L_{m,n} := max\{K : X_{i_k}=Y_{j_k} \text{ for } 1\leq k\leq K ,\text{where the i's and j's are increasing and bigger than m and smaller or equal to n}\}$ - the longest common subsequence of X and Y from m+1 to n.
Then apply the subadditive ergodic theorem to $-L_{m,n}$ to get $L_{0,n}/n \rightarrow \gamma = sup E(L_{0,m}/m)$.
I was able to figure this out. Now the exercise is to find bounds for Gamma. A lower bound can be calculated by computing the expectation of the right side for m=2 which is 9/16. However for the upper bound the exercise says: "Show $\gamma < 1$ by computing the expected number of i and j sequences of length K=an with the desired property."
So my goal is to show that the limit is indeed smaller than 1. However I don't know how to do that. To begin, What is the number of i and j sequences of length K = an (I assume that the desired property is that both X and Y common subsequences have length K)? Where does the a come from? Are we considering sequences from $L_{0,n}$ or for n to infinity? How do we conclude that gamma is less than 1?