The longest common subsequence (LCS) between two random words is poorly understood. At the start of the talk, I will survey what is known about the problem, and present new conjectures. Most of the talk will be devoted to a simpler problem, the LCS between a fixed periodic word and a random word. We will relate it to "frog dynamics'', a new interacting particle system similar to PushASEP. Given time, I hope to present a beautiful, but mysterious connection of the frog dynamics to a random walk on Dyck paths.
Joint work with Chris Cox.