Empirical scaling of the length of the longest increasing subsequences of random walks

Autor(es)

Mendonca, J. Ricardo G.,

• Tipo de documento: Artigo Científico
• Fonte: Journal of Physics A-Mathematical and Theoretical; v. 50, n. 8 FEB 24 2017.
• Citações Web of Science: 0
• Assunto(s): Análise de séries temporais

Resumo

We provide Monte Carlo estimates of the scaling of the length L-n of the longest increasing subsequences of n-step random walks for several different distributions of step lengths, short and heavy-tailed. Our simulations indicate that, barring possible logarithmic corrections, L-n similar to n(theta) with the leading scaling exponent 0.60 less than or similar to theta less than or similar to 0.69 for the heavy-tailed distributions of step lengths examined, with values increasing as the distribution becomes more heavy-tailed, and theta similar or equal to 0.57 for distributions of finite variance, irrespective of the particular distribution. The results are consistent with existing rigorous bounds for., although in a somewhat surprising manner. For random walks with step lengths of finite variance, we conjecture that the correct asymptotic behavior of L-n is given by root n ln n, and also propose the form for the subleading asymptotics. The distribution of L-n was found to follow a simple scaling form with scaling functions that vary with theta. Accordingly, when the step lengths are of finite variance they seem to be universal. The nature of this scaling remains unclear, since we lack a working model, microscopic or hydrodynamic, for the behavior of the length of the longest increasing subsequences of random walks. (AU)

• Processo FAPESP: 15/21580-0 - Análise e simulação de passeios aleatórios e processos de exclusão sobre grafos
• Beneficiário: José Ricardo Gonçalves de Mendonça
• Linha de fomento: Auxílio à Pesquisa - Regular