Mientras yo estaba pensando en el Erdős discrepancia problema, el siguiente modelo de paseo aleatorio surgió naturalmente. Se fija un entero positivo k, y se toma una al azar paso de 1 o -1 en cada etapa, excepto en el caso de que el escenario es un múltiplo de k, en cuyo caso puedes elegir. Su objeto es mantener el pie tan cerca del origen como usted puede.
Una clara estrategia es un codicioso: cada vez que usted tiene la elección, si el pie es actualmente positivo que usted elija -1 y si está negativo de elegir +1. (Claramente no hace ninguna diferencia para el resultado de lo que usted hace si es cero.) Esto es como dar su paseo aleatorio de la deriva plazo de tamaño 1/k, pero la tendencia es siempre dirigida hacia el origen.
Un poco diferente de la pregunta sería si usted está presentado con todo el pie hasta el kN-1 y, a continuación, elija los signos de k, 2k, 3k, ... , Nk, tratando de minimizar la máxima distancia que va desde el origen.
No es difícil ver que debe ir al menos de forma logarítmica, ya que en el momento de llegar a M usted probablemente ha tenido una carrera de registro M 1s en la caminata al azar, que se puede hacer casi nada. He pensado sobre el problema en un no-modo riguroso y se siente a mí como a pesar de que no debería ser demasiado difícil probar que en el momento de llegar a M no han ido más allá de $(\log M)^2$ o $(\log M)^3$ o algo así. (El primer argumento es que si se mira de una carrera de a $k^2$ pasos, no tienden a la deriva más que sobre k, y vas a tener k pasos que usted puede elegir para cancelar la deriva. Que es lo que sucede normalmente, y las excepciones deben ser exponencialmente raro, por así decirlo.)
Mi principal pregunta es esta: ¿son estas, o al menos algo parecido, conocido preguntas? (¿O respuestas a los mismos a seguir casi al instante de resultados conocidos?)
