Coin toss with rule +1 if it is a head and -1 otherwise

[alfredbobo]

Coin toss with rule "+1 if it is a head and -1 otherwise"

25 < my age < 54. Start from the number of my age and toss a fair coin, plus one if it is a head and minus one otherwise, on average, you need to toss 210 times to hit the bound, i.e. 25 or 54. There are two integers satisfying the condition. Fortunately, the smaller one is my age.

 

[ramsey2879]

25 < my age < 54. Start from the number of my age and toss a fair coin, plus one if it is a head and minus one otherwise, on average, you need to toss 210 times to hit the bound, i.e. 25 or 54. There are two integers satisfying the condition. Fortunately, the smaller one is my age.

if what you say is true you could subtract 24 from 25, 54 and your age to get the same problem so 1<age-24<30. 30 *7 = 210. 7 = 2^3-1. 30 = 2^5-2 = 2*(2^4-1) I am not sure what these numbers mean but powers of 2 would seem important in coin toss problems. I searched "coin toss" in Sloane's Online Encyclopedia of Integer Sequences and got ten sequences of interest but no hint of solution. It is interesting that although the average ratio of heads to tails should be 50:50 that there would be an average for the number of tosses to get a certain offset value.

 

[Diffy]

First, is this a trick question? I spent some time on this, and wanted to try to practice my programming skills to figure it out. I have programmed a model of this question. I am having trouble interpretting the results though. I create an array (call it array A) of size 210. I fill it with random 1's and -1's. I sum this array and record the result in a separate array (call it array B).

Now I looped this so I would record 10,000 results in array B. The problem is the results are all Positive, and negative, and the average is very close to zero.

We want to find out, on average, after 210 flips, how much would we add, or subtract from the age. So it seems clear that I need to separate the positives and negatives into two separate arrays, and average those. But what do I do with all the zeros?

Should I count them, and put that many zeroes on the positive, and the same amount in the negatives? Do I put half of them in the positives and half in the negatives?

I need to do something with them because it affects the number that I will be dividing by.

 

[Diffy]

By the way, I ask if this is a trick question because of the wording. "plus one if it is a head and minus one otherwise"

Why does it not specifically state, minus one if it is a tails. Otherwise? If it lands on it's edge do I subtract 1? If a lion eats the coin in mid air do I subtract 1?

 

[ramsey2879]

First, is this a trick question? I spent some time on this, and wanted to try to practice my programming skills to figure it out. I have programmed a model of this question. I am having trouble interpretting the results though. I create an array (call it array A) of size 210. I fill it with random 1's and -1's. I sum this array and record the result in a separate array (call it array B).

Now I looped this so I would record 10,000 results in array B. The problem is the results are all Positive, and negative, and the average is very close to zero.

We want to find out, on average, after 210 flips, how much would we add, or subtract from the age. So it seems clear that I need to separate the positives and negatives into two separate arrays, and average those. But what do I do with all the zeros?

Should I count them, and put that many zeroes on the positive, and the same amount in the negatives? Do I put half of them in the positives and half in the negatives?

I need to do something with them because it affects the number that I will be dividing by.

You probable should be looking not at the low values or the extreme values, those farthest away from 0 are probably more likely to first appear with more coin tosses while those near 0 are more likly to first appear with fewer coin tosses. I don't think it is a trick question, see for instance http://www.research.att.com/~njas/sequences/A050231 also see A050232, A050033, A033504 and A059943 in the same site and see http://mathworld.wolfram.com/CoinTossing.html. There should be an answer but it can't be by just looking at results for 210 tosses of the coin since you want to find the value that is first reached on an average of 210 tosses and to know that you have to consider what happens after of n tosses where n is other than 210. I thought it might be a trick question too (like what is the average of "n" and infinity) but after looking at the sites above I changed my mind.

 

[robert Ihnot]

The guess I made was he was referring to the $$STD = \sqrt{pq*210}=7.25 ...$$ So that at this point 68% of the time the variation would not move more than 7 whole points. So if the age was 32 (the starting point) it may reach or pass the boundry of 25. ?

 

[Diffy]

So I have modified my program. It will now start at with the value 26. It will create the arrays 10,000 times and average how many flips it took to get to the boundry (either 25, or 54). Once I have an average for 26, it will move on to 27 and so on and so forth until it reaches 53. I will then look at the average number of flips it took for each integer contained in (25, 54).

This should work, right?

 

[Diffy]

By the way, this process, is almost crashing my computer because of the amount of calculation being done. I expect this to run over night. at the very least. I will update when I have results.

 

[Diffy]

I have finished running the program. I am positive that I have done this correctly.

Just to recap, here is what I did.

I had the user input a number between 25 and 54. Then I basically flipped a coin and followed the rules stated, until I hit the bounds. I did this 10,000 times for each number between 25 and 54. Then I averaged those 10k numbers. This gave me the average number of coin flips it takes to reach the bounds for each age in between 25 and 54.

For 26, it takes on average 27 flips.
For 27, it takes on average 52 flips.
For 28, it takes on average 76 flips.
For 29, it takes on average 98 flips.
For 30, it takes on average 115 flips.
For 31, it takes on average 132 flips.
For 32, it takes on average 150 flips.
For 33, it takes on average 167 flips.
For 34, it takes on average 173 flips.
For 35, it takes on average 188 flips.
For 36, it takes on average 188 flips.
For 37, it takes on average 196 flips.
For 38, it takes on average 205 flips.
For 39, it takes on average 210 flips.
For 40, it takes on average 210 flips.
For 41, it takes on average 205 flips.
For 42, it takes on average 196 flips.

At this point it becomes symmetric.

So there are two options where it averages 210 flips. When the person is either 39 or 40. Since the problem states that he is the lesser age. The person must be 39.

I think coding a program to simulate this experiment was pretty cool, but I would love to see the solution worked out with formulas.

 

[matt grime]

Let E(n) be the expected time to hit the boundary starting at n. This satisfies the recurrence relation

E(n)=1+ (E(n-1)+E(n+1))/2

Solve, subject to the conditions E(25)=0 and E(54)=0

 

[ramsey2879]

Let E(n) be the expected time to hit the boundary starting at n. This satisfies the recurrence relation

E(n)=1+ (E(n-1)+E(n+1))/2

Solve, subject to the conditions E(25)=0 and E(54)=0

But there are some discrepancies with the Diffy's data e.g. by as much as 10 or more

 

[Curious3141]

I would've thought the problem could be viewed as a simple 1-d unbiased random walk where the expected endpoint is given and the origin is to be determined.

The (arithmetic mean) average distance from the origin <d> after N steps is, to a very good approximation for large N, $$\sqrt{\frac{2N}{\pi}}$$, which gives around 11.56.

The rms distance <d^2>^0.5 is $$\sqrt{N}$$ giving 14.49.

The first measure gives possible values of (25+11.56 = 36.56) or (54-11.56 =42.44). Naturally, these values are asymmetric in the sense that each is "closer" to one bound than the other, meaning they would (approximately) satisfy the 210-step condition only with one bound. Since the smaller value is wanted, that would be 36.56 (36 or 37 if integers are required, and 36 is the smaller value).

The second measure gives a nearer to symmetric value (25 + 14.49 = 39.49, which is close to 54 - 14.49 = 39.51) In this case, the single value 39.5 (39 or 40 if integers req'd, 39 is the smaller value) would be the answer.

 

[D H]

I have finished running the program. I am positive that I have done this correctly.

Just to recap, here is what I did.

I had the user input a number between 25 and 54. Then I basically flipped a coin and followed the rules stated, until I hit the bounds. I did this 10,000 times for each number between 25 and 54. Then I averaged those 10k numbers. This gave me the average number of coin flips it takes to reach the bounds for each age in between 25 and 54.

What you did was a Monte Carlo experiment. More below.

I think coding a program to simulate this experiment was pretty cool, but I would love to see the solution worked out with formulas.

The basis for the answer is in the Matt Grime's post, which follows right after yours. Matt Grimes showed a way to solve the problem. Remember that Matt is a mathematician. Showing that a solution exists suffices. You've heard the joke about the physicist, the engineer, and the mathematician, haven't you?

Let E(n) be the expected time to hit the boundary starting at n. This satisfies the recurrence relation

E(n)=1+ (E(n-1)+E(n+1))/2

Solve, subject to the conditions E(25)=0 and E(54)=0

This leads to the tridiagonal matrix equation

$$\left[\begin{matrix} 1 & 0 & 0 & 0 & \cdots & & & \\ -1/2 & 1 & -1/2 & 0 & \cdots & & & \\ 0 & -1/2 & 1 & -1/2 & \cdots & & & \\ \vdots & & & & \ddots & & & \\ 0 & \cdots & & & & -1/2 & 1 & -1/2 \\ 0 & \cdots & & & & 0 & 0 & 1 \end{matrix}\right] \boldsymbol x = \left[\begin{matrix} 0 \\ 1 \\ 1 \\ \vdots \\ 1 \\ 0\end{matrix}\right]$$

A comparison of the exact results against the Monte Carlo experiment:

$$\begin{matrix} \text{N} & \text{Exact} & \text{Monte} \\ 26 & 28 & 27 \\ 27 & 54 & 52 \\ 28 & 78 & 76 \\ 29 & 100 & 98 \\ 30 & 120 & 115 \\ 31 & 138 & 132 \\ 32 & 154 & 150 \\ 33 & 168 & 167 \\ 34 & 180 & 173 \\ 35 & 190 & 188 \\ 36 & 198 & 188 \\ 37 & 204 & 196 \\ 38 & 208 & 205 \\ 39 & 210 & 210\end{matrix}$$

But there are some discrepancies with the Diffy's data e.g. by as much as 10 or more

You cannot expect Monte Carlo techniques to yield exact answers. The accuracy of the results depends on the number of trials and the nature of the underlying distribution. In this case, the Monte Carlo experiment appears to have a negative bias and is not accurate enough to distinguish between 37, 38, or 39. But it is close.

 

[ramsey2879]

What you did was a Monte Carlo experiment. More below.

The basis for the answer is in the Matt Grime's post, which follows right after yours. Matt Grimes showed a way to solve the problem. Remember that Matt is a mathematician. Showing that a solution exists suffices. You've heard the joke about the physicist, the engineer, and the mathematician, haven't you?


This leads to the tridiagonal matrix equation

$$\left[\begin{matrix} 1 & 0 & 0 & 0 & \cdots & & & \\ -1/2 & 1 & -1/2 & 0 & \cdots & & & \\ 0 & -1/2 & 1 & -1/2 & \cdots & & & \\ \vdots & & & & \ddots & & & \\ 0 & \cdots & & & & -1/2 & 1 & -1/2 \\ 0 & \cdots & & & & 0 & 0 & 1 \end{matrix}\right] \boldsymbol x = \left[\begin{matrix} 0 \\ 1 \\ 1 \\ \vdots \\ 1 \\ 0\end{matrix}\right]$$

A comparison of the exact results against the Monte Carlo experiment:

$$\begin{matrix} \text{N} & \text{Exact} & \text{Monte} \\ 26 & 28 & 27 \\ 27 & 54 & 52 \\ 28 & 78 & 76 \\ 29 & 100 & 98 \\ 30 & 120 & 115 \\ 31 & 138 & 132 \\ 32 & 154 & 150 \\ 33 & 168 & 167 \\ 34 & 180 & 173 \\ 35 & 190 & 188 \\ 36 & 198 & 188 \\ 37 & 204 & 196 \\ 38 & 208 & 205 \\ 39 & 210 & 210\end{matrix}$$

I checked my hunch the average number of times to reach a bondary exactly must be of the form such that if there are zeros where the bondary is reached then the case must be of the form where there exists P(n) = P(n+1) = 2^x-2 or P(n) = P(n+2) for some n. I thought I proved that if the first case is present of the first case then P(n) must be either of the form P(n) = (2^(x-1)-1)*(2^(x + 1)-2) and the zeros are at P(n - 2^x + 1) or P(n+2^x-1)); or P(n) = x(x+1) in which the zeros are at P(n-x) or P(n+x+1). This seem to conflict with the statement the the Matt's post shows the existence of a solution for all cases in which there is are zeros at P(z) and P(z+2n+1). For instance the existence of bondary points at 1 and 18 appeared impossible but then I realized that I merely proved that P(n) = P(n+1) = 18 is impossible and the last possiblity in fact proves the existence of a solution.

 

[D H]

Matt's solution, follows directly from the problem statement. Define E(n) as the expected value of reaching a boundary point from some initial value n. The expected value for the two boundary points is obviously zero. For an interior point, at least one flip is needed, and this flip moves the initial point to the points n-1 or n+1 with equal probability. Hence E(n) = 1 + (E(n-1)+E(n+1))/2 for the interior points.

 

[ramsey2879]

Matt's solution, follows directly from the problem statement. Define E(n) as the expected value of reaching a boundary point from some initial value n. The expected value for the two boundary points is obviously zero. For an interior point, at least one flip is needed, and this flip moves the initial point to the points n-1 or n+1 with equal probability. Hence E(n) = 1 + (E(n-1)+E(n+1))/2 for the interior points.

I agree that Matts solution is correct but that doesn't provide an immediate solution except by solving equations in matrix form. Matts solution provides an recursive formula $$P_{n} = 2P_{n-1} - P_{n-2} -2$$ so if we know the initial two values we can compute the remaining values recursively. If A and B are the boundary points with B > A then P(A) = 0 and P(A+1) = B-A-1 so it is easy to obtain the result recursively. Also, if C = Foor((A+B)/2) then P(C) equals (C-A)^2 if A+B is even and equals (C-A)^2+C-A if A+B is odd.

 

[matt grime]

If A and B are the boundary points with B > A then P(A) = 0 and P(A+1) = B-A-1.

I don't immediately see the second equality there. What is the reason for that?

 

[ramsey2879]

I don't immediately see the second equality there. What is the reason for that?

It follows from induction. If A+B is odd then P((A+B-1)/2) = P((A+B+1)/2)=X
P((A+B+1)/2) = X
P((A+B+3)/2) = X-2
P((A+B+5)/2) = X-2*2 -2 = X-6
P((A+B+7)/2) =X-6*2 + 2 -2 = X-12
P((A+B+9)/2) =X-12*2+6-2 = X-20
...
P((A+B +B-A-2)/2) = P(B-1) = X - (B-A-1)*(B -A -3)/4
P((A+B +B-A)/2) = P(B) = X - (B-A-1)*(B-A+1)/4

P(B-1)-P(B) = (B-A-1)(3+1)/4 = B-A-1

A similar proof for A+B is even also leads to the same result.

 

[matt grime]

Nope, I fail to see why the expected hitting time from (A+B+3)/2 is the expected hitting time from (A+B+1)/2 minus 2.

The first thing you wrote was jus symmetry about the mid point. Why does moving one step away from the mid point decrease your expected hitting time by 2?

 

[ramsey2879]

Nope, I fail to see why the expected hitting time from (A+B+3)/2 is the expected hitting time from (A+B+1)/2 minus 2.

The first thing you wrote was jus symmetry about the mid point. Why does moving one step away from the mid point decrease your expected hitting time by 2?

Under my assumption A+B is odd, therefore B-(A+B+1)/2 = (A+B-1)/2 -A and B-(A+B-1)/2 = (A+B+1)/2 - A so the distances from the boundary points is equal and E((A+B-1)) = E((A+B+1)/2) = X
But E((A+B+1) -(E((A+B-1)/2 + E((A+B+3)/2)/2 = 1
So E((A+B+3)/2) = 2(E((A+B+1)/2)-E((A+B-1)/2 -2 = 2X-X -2 = X-2

 

[ramsey2879]

Also With the assumption that A+B is even then we have P((A+B)/2-1) = P((A+B)/2+1)
We let E(A+B)/2) = X
Then (E((A+B)-1) + E((A+B)/2+1))/2 = E((A+B)/2 +1)
Then X -E((A+B)/2+1) = 1 or
E((A+B)/2 +1) = X - 1
E((A+B)/2+2) = 2X-2 - X - 2 = X-4
E((A+B)/2+3) = X - 2*4 +1 -2 = X-9
E((A+B)/2+4) = X -2*9 + 4 -2 = X-16
E((A+B)/2+5 = X -2*16 +9 -2 = X-25
E((A+B)/2+6 = X-2*25 + 16 - 2 = X-36
...
E((A+B)/2 +(B-A-2)/2) = E(B-1) = X -(B-A-2)^2)/4 = X-((B-A)^2)/4 +4(B-A)/4 - 4/4)
E((A+B)/2 +(B-A)/2) = E(B) = X - ((B-A)^2)/4 = 0
Thus E(A+1) = E(B-1) = B-A-1

 

[ramsey2879]

I agree that Matts solution is correct but that doesn't provide an immediate solution except by solving equations in matrix form. Matts solution provides an recursive formula $$P_{n} = 2P_{n-1} - P_{n-2} -2$$ so if we know the initial two values we can compute the remaining values recursively. If A and B are the boundary points with B > A then P(A) = 0 and P(A+1) = B-A-1 so it is easy to obtain the result recursively. Also, if C = Foor((A+B)/2) then P(C) equals (C-A)^2 if A+B is even and equals (C-A)^2+C-A if A+B is odd.

I notice that the recursive sequences of the form $$P_{n} - bP_{n-1} - P_{n-2} + d$$ can be generally be solved by considering the set of equations
$$P_{n} = A*r_{1}^n + B*r_{2} - \frac{d}{b-2}$$ where $$r_1$$ and $$r_2$$ are the roots of the auxiliary equation $$x^2 - bx +1$$ but this is impossible for $$b=2$$ for two reasons: 1) there is division by zero and 2) the roots $$r_1$$ and $$r_2$$ both equal 1 so the formula becomes
$$P_{n} = A+B -\frac{d}{0}$$ which makes no sense. Even if d = 0 we have:
$$P_{n} = A + B$$ which is a constant even when the recursive sequence is not.
How would one generally go about solving recursive sequences
$$P_{n} -bP_{n-1} + cP_{n-2} = 0$$ where $$b^2 = 4c$$?