The following question is somewhat related to:

Asymmetric random walk

Let $(X_i)_{i=1}^n$ be a sequence of i.i.d. random variables with $\Pr(X_i=1)=\Pr(X_i=-1)=1/2$. Let $S_0=0$ and, for $1\le i\le n$, $S_i = X_1+X_2+\cdots+X_i$. Let $\Pi_n$ denote the number of strictly positive terms among $S_1,\ldots,S_n$. In the symmetric case, namely, when $p=1/2$, the law of $\Pi_n$ is known to be (e.g. Feller, Ch. XII.8) $$ \Pr(\Pi_{n}=k) = {2k\choose k}{2n-2k\choose n-k}\frac1{2^{2n}}. $$ I am trying to find asymptotic (in $k,m,n$) formula for the number of positive terms given the value of the last term, or more generally, $$ \Pr(\Pi_{n}=k,S_n=m) $$ Of course not all values of $k,m$ are possible. Also, clearly, the additional event that $S_n=m$ breaks the nice symmetry of the process $(X_i)_{i=1}^n$, so in some sense $(X_i)_{i=1}^n$ can be thought as being drawn uniformly over some subspace of the hyper-cube. Note that this probability can be probably upper bounded by removing the $S_n=m$ constraint but assuming that $(X_i)_{i=1}^n$ is now an asymmetric process with success probability that is proportional to $m/n$.

  • 1
    $\begingroup$ Assuming that $m \ge 0$ and that $m$ and $n$ have the same parity, then I think at the extremes $\Pr(\Pi_{n}=n \mid S_n=m) = \dfrac{m}{n}$ while $\Pr(\Pi_{n}=m \mid S_n=m) = \dfrac{ 2 \binom{n-m}{(n-m)/2}}{\left({n-m}+2\right)\binom{n}{m}}$ $\endgroup$ – Henry Aug 15 '17 at 22:05
  • $\begingroup$ Agree, thanks! However, I need the general case :\ $\endgroup$ – J.John Aug 15 '17 at 22:23
  • $\begingroup$ @Henry Actually, can you prove that? $\endgroup$ – J.John Aug 16 '17 at 14:32
  • $\begingroup$ I think the first is the ballot theorem while the second is essentially the "lattice paths staying below the diagonal" interpretation of Catalan numbers for the first $n-m$ steps. $\endgroup$ – Henry Aug 16 '17 at 15: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.