OFFSET
-4,1
COMMENTS
Consider the 1D random walk starting at position 0, with equal probability of moving one unit to the left or one unit to the right. This allows 2^s different trajectories if we consider a maximum of s steps (s=8 here). For each of the trajectories, compute the median position, which is in the interval [-s/2, +s/2].
The sequence shows the count of trajectories with median equal to n (so the sum over all elements of the sequence is again 2^s = 256).
1) Suppose s is even, the convolution of the probability distribution of the minimum and the maximum of a simple random walk up to s/2 is equal to the probability distribution of the median (see Mathematica program and references).
2) The median taken on partial sums of the simple random walk represents the market price in a simulation model wherein a single security among non-cooperating and asymmetrically informed traders is traded (see Pfeifer et al. 2009).
3) Transformation T007 gave a match with first differences of A089877 (superseeker).
REFERENCES
W. Feller, An Introduction to Probability Theory and its Applications I. New York: Wiley, 1968.
LINKS
C. Pfeifer, Probability Distribution of the Median Taken on Partial Sums of a Simple Random Walk, Stochastic Analysis and Applications, Volume 31, Issue 1, 2013, pp. 31-46; DOI:10.1080/07362994.2013.741359. - N. J. A. Sloane, Jan 04 2013
C. Pfeifer, K. Schredelseker, and G. U. H. Seeber, On the negative value of information in informationally inefficient markets. Calculations for large number of traders, Eur. J. Operat. Res., 195 (1) (2009) 117-126.
J. G. Wendel, Order Statistics of Partial Sums, Ann. Math. Statist. 31 (4) (1960) pp. 1034-1044.
EXAMPLE
The possible different paths (sequences of partial sums) in the case s=2:
{0,-1,-2}; median=-1
{0,-1,0}; median=0
{0,1,0}; median=0
{0,1,2}; median=1
Sequence of integers in the case s=2: 1,2,1.
In the current case s=8, we have 6 trajectories with median -4, 10 trajectories with median -3, etc.
MATHEMATICA
(* calculation of distribution of median single random walk *) p[n_, r_] := If[Floor[(n + r)/2] - (n + r)/2 == 0, Binomial[n, (n + r)/2], 0] maximum[n_, r_] := p[n, r] + p[n, r + 1]; (* prob. maximum *) minimum[n_, r_] := p[n, -r] + p[n, -r + 1]; (* prob. minimum *) median[n_] := ( (* distr. median *) listmin = Table[If[r < -(n/2) || r > 0, 0, minimum[n/2, r]], {r, -n, n}] (* distr. minimum *); listmax = Table[If[r > n/2 || r < 0, 0, maximum[n/2, r]], {r, -n, n}] (* distr. maximum *); listmedian = ListConvolve[listmax, listmin, {1, -1}] (* convolution *); listmedian[[3 n/2 + 1 ;; 5 n/2 + 1]]); (* result median *) Table[median[2 n], {n, 1, 7}](* result up to n=14 *)
CROSSREFS
KEYWORD
easy,fini,full,nonn
AUTHOR
Christian Pfeifer (christian.pfeifer(AT)uibk.ac.at), Mar 13 2008, May 03 2010
EXTENSIONS
Variables names normalized, offset set to -4 by R. J. Mathar, Sep 17 2009
STATUS
approved