2
$\begingroup$

So recently I came across a math problem, which states the following: You play a game with a fair coin. You start with zero points, and you throw the coin. If you throw heads, you add 1 point to the score; if you get tails, you subtract 1 point (The score can be negative). What is the average amount of throws after which the score will return to zero for the first time?

From there you can proceed to find the probability weighted average of all numbers of throws ((2throws)*(probability of returning to zero after 2 throws) e.t.c.). To find the probability, however, you have to find the number of ways that the score can reach 0 after a certain number of tosses. If the score could reach zero before reaching the 0 again after these many tosses, the number of ways would be given through Pascal´s Triangle; i.e. binomial coefficient. Since the score cannot "cross" the zero line, however, you get a sort of a half of Pascal´s Triangle, with terms at the center line and to the left (WLOG) not being summed into the next rows. Does anyone know, or has an idea about how one could find, the general formula for a given number in the Pascal´s "Half-triangle"?

$\endgroup$
  • 1
    $\begingroup$ See Catalan_number. It's the number of monotonic lattice paths along the edges of a grid with n × n square cells. $\endgroup$ – Terence Hang Sep 9 '15 at 11:41
1
$\begingroup$

The following procedure can be used to identify the probability $p(i)$ of reaching a zero score for the first time after $i$ throws ($i>0$). It is easy to see that $p(i)=0$ for odd values of $i$.

Let $S_i$ denote the score after $i$ throws

The $i$ throws can be broken down into three parts as follows -

  1. Make the first throw; So, $S_1=\pm 1$

  2. Starting from second throw, for the next $i-2$ throws (i.e. upto but excluding the last throw), determine the probability of $S_i$ returning to $S_1$ ,i.e., $p(S_i \to S_1)$, such that $|S_i|\ge|S_1| \space \forall \space i$. Note that, $S_j=S_1$ may be possible for multiple values of $j$ such that $2\le j\le i-2$. Also, note that this set of $i-2$ throws represents monotonic lattice paths that do not cross the diagonal in an $n\times n$ grid where $n=(i-2)/2$. The right and up movements in the grid are analogous to the two outcomes of each throw. Constraining the path to not cross the diagonal is equivalent to maintaining $|S_i|\ge|S_1|$

  3. Determine the probability of $S_i=0$ after the $i^{th}$ throw (this can happen only if the last throw and first throw yield opposite results and hence evaluates to $0.5$)

Hence, $p(i)=p(S_1=\pm1) \times p(S_i \to S_1) \times p(S_i=0)$

Hence, $p(i)=p(S_1=\pm1) \times (\frac {C_{(i-2)/2}}{2^{i-2}}) \times p(S_i=0)$

where $C_n$ is a catalan number that counts the kind of lattice paths described in point no. 2 above in an $n \times n$ grid. The denominator gives the total number of paths possible with $i-2$ throws.

Hence, $p(i)=1 \times \frac{1}{2^{i-2}} (\frac {2}{i}){i-2\choose i/2-1} \times 0.5$

Hence, $p(i)= \frac{1}{i\cdot2^{i-2}} {i-2\choose i/2-1} $ for all even values of $i$ and zero otherwise.

Determining the average number of throws for the first zero score:

I am not sure how the probability computed above (assuming it is correct) could be used to determine the answer to the required question but I have two guesses -

  1. The smallest number $x$ such that $\sum_1^xp(i)\ge1/2$*

  2. Sum of number of moves weighted by their probabilities

$\endgroup$
2
$\begingroup$

An old question but I've seen this question about a formula for half Pascal's triangle many times so I thought I would weigh in.

The rows are, ${r-1 \choose \frac{2r+1-(-1)^r}{4}-n}$ where $r$ is the row and $n$ is the term. The columns are, ${2n+c-3 \choose n-1}$ where $c$ is the column and $n$ is the term. These give the right half of Pascal's triangle.

$\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.