For a function $f$ consider a random sequence

$a_{n+1}$ can be either $a_n+f(a_n)$ or $a_n-f(a_n)$

Given that the next term in the sequence is subtracting $f(a_n)$ from the previous term 50% of the time and adding it 50% of the time, what function $f$ yields $a_{n+x} > a_n$ for "most" positive values of $x$?

  • 1
    $\begingroup$ Are there any restrictions on $f$? If not, try $f(x) = -1$ for all $x$. $\endgroup$
    – JimmyK4542
    Jul 15, 2014 at 23:22
  • $\begingroup$ What does "most" mean? What does "75% of the time" means? Math questions, please. $\endgroup$
    – user147263
    Jul 15, 2014 at 23:49
  • $\begingroup$ @This I think there is a sense in which this question is a math question, about setting up a biased random walk where the step size depends on the value of a given term, etc. and it asks for an optimal choice of $f$ for which one can in the long run guarantee the most cases wherein it goes to the right of where it is (at $x$ steps later), for hopefully a "large" set of positive $x$. $\endgroup$
    – coffeemath
    Jul 16, 2014 at 0:27
  • $\begingroup$ Waffle: I just tried an edit to make it look better at this site. It's still a bit vague in terms of what "most" positive $x$ should mean, hence I put that in quotes. Anything may be changed of course, to be as you want it. $\endgroup$
    – coffeemath
    Jul 16, 2014 at 0:38
  • $\begingroup$ It might help to formalize: let $b_n$ be iid Bernoulli(1/2) random variables independent of $a_n$, then $a_{n+1} = a_n + (2b_n - 1) f(a_n)$. It is easy to show that $a_n$ is a martingale. Under some boundedness assumptions on $f$, the optional stopping theorem makes the question in the OP more or less impossible. $\endgroup$
    – Ian
    Jul 18, 2014 at 3:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.