Justifying Linear Interpolation in Coin Toss Example

[Mogarrr]

Today in class, there was an example where I didn't understand certain justifications. The example goes something like this:

A casino runs a game of chance where you toss a coin and they pay $1 if you get heads , and you pay $1 if you get tails. The coin is a fair coin.

A gambler starts with fortune z. The goals is to increase the fortune to g≥z. Said gambler plays until they reach g or their fortune is $0.

Let A be the event of reaching the goal g starting from fortune z.
Let Pr(A) = ψ(z).

It's clear that ψ(0)=0 and ψ(g)=1, by the rules the gambler uses. We want a formula ψ(z) for 0<z<g. We use the law of total probability, conditioning on the first toss.
Let $B_1$=first toss is heads
Let $B_2$=first toss is tails, as this forms a partition of the sample space.

Pr(A)=$Pr(B_1)\cdot Pr(A|B_1) + Pr(B_2)\cdot Pr(A|B_2)$, so
ψ(z) = (1/2)ψ(z+1) + (1/2)ψ(z-1) = (1/2)(ψ(z+1)+ψ(z-1))

and this is where I have a big question mark over my head

ψ(z) is a linear function of z

$\exists a,b: ψ(z)=az+b$
$\psi (0)=0 \Rightarrow b=0$
$\psi (g) =1 \Rightarrow a = \frac 1{g}$
$\Rightarrow \psi (z)= \frac {z}{g}, \forall z: 0 \leq z \leq g$

...So how is it justified that the recursive function is a linear function. The professor talked about a linear interpolation happening, but I just don't see how you can make that jump. I can follow all other lines of reasoning, so I just want to talk about this.

Anybody here know how that step is justified?

 

[disregardthat]

One way of thinking about that $\psi$ has the form of a linear equation is as a hypothesis. Only one equation will satisfy the recurrence relation given the two initial conditions. The general linear function has a solution in its coefficients, and so the hypothesis was correct, and the calculation yields the exact equation for $\psi$.

But one can also deduce this without hypothesis of the form of $\psi$. The characteristic equation for the recurrence relation has only one solution r = 1, and therefore we know the equation is linear, by the general theory of linear recurrence relations in one variable. Calculating the coefficients still remain however.

 

[Mogarrr]

But one can also deduce this without hypothesis of the form of $\psi$. The characteristic equation for the recurrence relation has only one solution r = 1, and therefore we know the equation is linear, by the general theory of linear recurrence relations in one variable. Calculating the coefficients still remain however.

I don't really follow. I think the characteristic equation is a polynomial, right? What do you mean when you say it has only one solution, r=1? And the general theory of linear recurrence relations in one variable?

 

[disregardthat]

I don't really follow. I think the characteristic equation is a polynomial, right? What do you mean when you say it has only one solution, r=1? And the general theory of linear recurrence relations in one variable?

Read up some on recurrence relations. See for example here: http://en.wikipedia.org/wiki/Recurrence_relation#Solving
they do the general case for a recurrence relation in one variable, and what form it has when the characteristic roots are equal (in this case, equal to 1).

But this is of course much better explained in any book that covers this material.

To answer your questions, yes the characteristic equation is a polynomial equation (the characteristic polynomial = 0). It is a second-order polynomial equation, having two roots up to multiplicity.

 

[rikblok]

ψ(z) = (1/2)ψ(z+1) + (1/2)ψ(z-1) = (1/2)(ψ(z+1)+ψ(z-1))

The way I see it is if the above occurrence relation holds then

ψ(z+1) - ψ(z) = ψ(z) - ψ(z-1)

for any 0<z<g. That means ψ(z) must increase by the same amount with every increment in z (same difference going from z-1 to z as from z to z+1) or in other words, ψ(z) is linear.

 

[Mogarrr]

The way I see it is if the above occurrence relation holds then

ψ(z+1) - ψ(z) = ψ(z) - ψ(z-1)

for any 0<z<g. That means ψ(z) must increase by the same amount with every increment in z (same difference going from z-1 to z as from z to z+1) or in other words, ψ(z) is linear.

I see, so

$\psi (z) = \frac 12 (\psi (z+1) + \psi (z-1)) \Rightarrow 2\cdot \psi (z) = \psi (z+1) + \psi (z-1)$
$\Rightarrow \psi (z) - \psi (z-1) = \psi (z+1) - \psi(z)$

And as you say, ψ(z) increases by the same amount with every increment.

Very nice and easy to understand point.