OFFSET
1,2
COMMENTS
For n odd, one in about 7.82 of all walks have this property, while for n even it fluctuates more initially but converges to the same limit as n odd. This small constant ratio demonstrates the weakness of this test for proving with confidence better than 87.2% that an ostensibly increasing sequence is not just a purely random walk.
PROG
(C) .#include <math.h>
.#include <unistd.h>
.#include <stdlib.h>
.#include <stdio.h>
.
.#define MAX 10
.
.int n, w[4*MAX+1];
.
.double
.f(int i, int wk, int lh, int rh)
.{
. w[i] = wk;
. return
. i < n? f(i+1, wk-1, lh+wk, 0) + f(i+1, wk+1, lh+wk, 0): // init lh
. i < 2*n? f(i+1, wk-1, lh, rh+wk) + f(i+1, wk+1, lh, rh+wk): // init rh
. i < 4*n? (lh >= rh? 0:
. f(i+1, wk-1, lh+w[i-n]-w[i-2*n], rh+wk-w[i-n]) + // walk
. f(i+1, wk+1, lh+w[i-n]-w[i-2*n], rh+wk-w[i-n])):
. lh < rh; // stop
.}
.
.int
.main()
.{
. for (n = 1; n <= MAX; n++)
. printf("%2d %0.f\n", n, f(0, 0, 0, 0)/2);
. return 0;
.}
CROSSREFS
KEYWORD
hard,more,nonn,walk
AUTHOR
Vaughan Pratt (pratt(AT)cs.stanford.edu), Sep 18 2010
STATUS
approved