0
$\begingroup$

Let $\mathcal{S}_n$ be the set of all binary sequences formed by $n$ values in $\{-1,1\}$ and let $k<n$ a given non-negative integer with the same parity of $n$. For every sequence $\mathcal{S}\ni S=\langle x_1, x_2, \ldots, x_n\rangle$, let $\sigma_j(S)$ be the sum $\Sigma_{i=1}^j x_i$ of its first $j$ elements, where $j\le n$.


Question: What is the total number of possible sequences $S\in\mathcal{S}$ such that $\sigma_n(S)=k$ and $\sigma_j(S)\le k$ for all $j\in\{1, 2, \ldots, n-1\}$?


This is part of the following problem: Flipping a biased coin landing on head with probability $1/3$, we win one dollar for each head and lose one dollar for each tail. What is the probability that when we keep flipping the coin, we gain $2$ dollars? I know that the answer is $1/4$, but the solution is a bit involved. Hence, I wanted to find a simpler solution. Summing $\binom{2n+1}n(2/3)^n(1/3)^{n+2}$ over $n$ from $0$ to $\infty$, one gets $1/2$ because subsequences leading to winning $2$ dollars are overcounted. Hence, I would like to use this approach to solve the original problem, by suitably reducing the term $\binom{2n+1}n$ to exclude the subsequences overcounted in the above summation (in the above question $k=1$, because the target is winning $2$ dollars, and the total length $n$ of the sequence $S$ is the number of coin flips minus one, because the last outcome must be head).

$\endgroup$
5
  • $\begingroup$ @ParclyTaxel thank you for pointing out the parity issue that I forgot to add. Actually, this is part of the following problem: Flipping a biased coin landing on head with probability $1/3$, we win one dollar for each head and loose one dollar for each tail. What is the probability that, keeping flipping the coin, we gain $2$ dollars? I know that the answer is $1/4$, but the solution is a bit involved. Hence, I wanted to find a simpler solution. Summing ${2n+1\choose n} (2/3)^n (1/3)^{n+2}$ over $n$ from $0$ to $\infty$, one gets $1/2$ because subsequences leading to win $2$$ are overcounted. $\endgroup$ Apr 28 at 12:04
  • $\begingroup$ @ParclyTaxel Hence, I wanted to find a way the use the above described approach to solve the original problem, by excluding the subsequences overcounded. $\endgroup$ Apr 28 at 12:07
  • $\begingroup$ @ParclyTaxel Thank you for improving the question. The only approach that I have in mind to solve the problem is based on the inclusion–exclusion principle, but the calculations seem too complicated and I guess there is something simpler I am missing here. $\endgroup$ Apr 28 at 12:14
  • 1
    $\begingroup$ André's reflection method will work here. Cf. here. $\endgroup$ Apr 28 at 12:27
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ Apr 28 at 12:42
2
$\begingroup$

Your problem is equivalent to the following one. Start at $\langle 0,0\rangle$ on the integer grid, and take $n$ steps, where each step is either an up-step (from $\langle a,b\rangle$ to $\langle a+1,b+1\rangle$) for a down-step (from $\langle a,b\rangle$ to $\langle a+1,b-1\rangle$). How many ways are there to reach $\langle n,k\rangle$ while staying below the line $y=k$ for the first $n-1$ steps?

For any such path the last step must be an upstep from $\langle n-1,k-1\rangle$, so we can equivalently count paths of length $n-1$ from $\langle 0,0\rangle$ to $\langle n-1,k-1\rangle$ that never rise above the line $y=k-1$. Let $\mathscr{P}$ be the set of all paths from the origin to $\langle n-1,k-1\rangle$, and let $\mathscr{P}_0$ be the subset of paths that do not rise above the line $y=k-1$.

Clearly $n-k$ must be even, so let $n=2m+k$. Clearly any path in $\mathscr{P}$ must have $m+k-1$ up-steps and $m$ downsteps, and any combination of $m+k-1$ up-steps and $m$ down-steps is a path in $\mathscr{P}$, so $|\mathscr{P}|=\binom{2m+k-1}m=\binom{n-1}m$.

Now suppose that $P\in\mathscr{P}\setminus\mathscr{P}_0$; then $P$ hits the line $y=k$, so there is a least $\ell$ such that $\langle\ell,k\rangle$ is in $P$. Reflect the part of $P$ from $\langle\ell,k\rangle$ to $\langle n-1,k-1\rangle$ in the line $y=k$, converting each down-step into an up-step and vice versa, to get a new path $P'$. That part of $P$ has a net fall of $1$ unit, so its reflection has a net rise of $1$ unit, and $P'$ therefore ends at $\langle n-1,k+1\rangle$. Thus, $P'$ has

$$\frac{(n-1)-(k+1)}2=\frac{2m-2}2=m-1$$

down-steps and $(m-1)+(k+1)=m+k$ up-steps. Clearly there are $\binom{n-1}{m-1}$ such paths. Moreover, every path from the origin to $\langle n-1,k+1\rangle$ crosses the line $y=k$ at some point, and reflecting the part of it to the right of that point in the line $y=k$ produces a path in $\mathscr{P}\setminus\mathscr{P}_0$, so $|\mathscr{P}\setminus\mathscr{P}_0|=\binom{n-1}{m-1}$.

It follows that

$$\begin{align*} |\mathscr{P}_0|&=\binom{n-1}m-\binom{n-1}{m-1}\\ &=\frac{(n-1)!}{m!(n-m-1)!}-\frac{(n-1)!}{(m-1)!(n-m)!}\\ &=\frac{\big((n-m)-m\big)(n-1)!}{m!(n-m)!}\\ &=\frac{k}m\binom{n-1}{m-1}\,. \end{align*}$$

As a quick sanity check, note that when $k=1$ the paths in $\mathscr{P}_0$ are just the reflections in the $x$-axis of the Dyck paths from $\langle 0,0\rangle$ to $\langle n-1,0\rangle$, and it is well known that there are

$$\begin{align*} C_m&=\frac1{m+1}\binom{2m}m=\frac{(2m)!}{m!(m+1)!}\\ &=\frac1m\binom{2m}{m-1}=\frac{k}m\binom{n-1}{m-1}\,. \end{align*}$$

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .