1
$\begingroup$

I apologize in advance if this question has a trivial answer. I am pretty sure this kind of problem was already studied and I am mostly asking for good references.

Given integers $0 < k \le n+1,$ I am interested in counting strings $s \in \{-1,1\}^n$ such that

  1. Every prefix of $s$ has more ones than -1's. In other words the respective sum of the prefix is strictly positive
  2. For every prefix of $s'$ of $s$ the sum of the elements of $s'$ is less than $k$

In other words for every prefix $s' = s_1 \cdots s_m$ of $s$ we have $$ 0 < \sum_{i=0}^m s_i < k.$$

Denoting this number by $a(n,k)$ I would like to obtain an asymptotic estimate or upper bound for $a(n,k).$

As far as I can see if I let $k+1$ this reduces to the theory of Dyck words. What am I interested in is the case when $k$ is smaller than $n.$ For example what if $k$ is a positive fraction of $n$?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

Essentially you're asking for the probability of not being absorbed in an unbiased random walk of $n-1$ steps starting at $1$ with absorbing boundaries at $0$ and $k$. This is a classical topic in probability, and I think e.g. Feller deals with it pretty thoroughly.

EDIT: In the terminology of Feller, chapter XIV, $k = a$, and $u_{1,n}$ is the probability that the process stops at the $n$'th step at barrier $0$, while by symmetry (since $p=q=1/2$) $u_{k-1,n}$ is the probability that it stops at the $n$'th step at barrier $k$. We then have (from formula (5.7))

$$\eqalign{u_{1,n} &= k^{-1} \sum_{\nu=1}^{k-1} \cos^{n-1}\left( \dfrac{\pi \nu}{k}\right) \sin^2 \left(\dfrac{\pi \nu}{k}\right)\cr u_{k-1,n} &= k^{-1} \sum_{\nu=1}^{k-1} \cos^{n-1}\left( \dfrac{\pi \nu}{k}\right) \sin \left(\dfrac{\pi \nu}{k}\right) \sin\left(\dfrac{\pi (k-1)\nu}{k}\right)\cr &= k^{-1} \sum_{\nu=1}^{k-1} \cos^{n-1}\left( \dfrac{\pi \nu}{k}\right) \sin^2 \left(\dfrac{\pi \nu}{k}\right) (-1)^{\nu-1}\cr u_{1,n} + u_{k-1,n} &= 2 k^{-1} \sum_{\nu \ \text{odd}} \cos^{n-1}\left( \dfrac{\pi \nu}{k}\right) \sin^2 \left(\dfrac{\pi \nu}{k}\right)}$$

The probability of not yet having been absorbed by the $n$'th step is $$\eqalign{ & \sum_{m=n+1}^\infty (u_{1,m} + u_{k-1,m})\cr & = 2 k^{-1} \sum_{\nu\ \text{odd}} \dfrac{\cos^n(\pi \nu/k)}{1 - \cos(\pi \nu/k)}\sin^2 \left(\dfrac{\pi \nu}{k}\right)\cr &= 2 k^{-1} \sum_{\nu \ \text{odd}} \cos^n\left(\dfrac{\pi \nu}{k}\right)\left(1 + \cos\left(\dfrac{\pi \nu}{k}\right)\right) \cr}$$

To get the asymptotics (for $k \to \infty$ with fixed $n$), treat this as a Riemann sum approximation to

$$ \int_0^1 \cos^n (\pi s) (1 + \cos(\pi s))\; ds = \cases{ 2^{-n} {n \choose n/2} & if $n$ is even\cr 2^{-n+1} {n-1 \choose (n-1)/2} & if $n$ is odd } $$

On the other hand, for $n \to \infty$ with fixed $k$, we take the $\nu$ giving the largest $|\cos(\pi \nu/k)|$, namely $\nu = 1$ (and, if $k$ is even, $\nu = k-1$).

$\endgroup$
1
  • $\begingroup$ Thanks for this. Could you elaborate a bit more? I have checked the book but do not see how to modify the introduced machinery in order to compute the asymptotics of $a(n,k)$ $\endgroup$
    – Jernej
    Oct 15, 2014 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.