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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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