Georgia Institute of Technology College of Sciences

The Scenery Reconstruction Problem consists in trying to reconstruct a coloring of the integers given only the observations made by a random walk. For this we consider a random walk S and a coloring of the integers X. At time $t$ we observe the color $X(S(t))$. The coloring is i.i.d. and we show that given only the sequence of colors $$X(S(0)),X(S(1)),X(S(2)),...$$ it is possible to reconstruct $X$ up to translation and reflection. The solution depends on the property of the random walk and the distribution of the coloring. Longest Common Subsequences (LCS) are widely used in genetics. If we consider two sequences X and Y, then a common subsequence of X and Y is a string which is a subsequence of X and of Y at the same time. A Longest Common Subsequence of X and Y is a common subsequence of X and Y of maximum length. The problem of the asymptotic order of the flucutation for the LCS of independent random strings has been open for decades. We have now been able to make progress on this problem for several important cases. We will also show the connection to the Scenery Reconstruction Problem.