Recursive Sentence

Copyright ©1997 by Paul Niquette. All rights reserved.
{Background}

JailThe judge's original ruling in the puzzle would allow the convicted gambler to be released immediately if the prisoner calls the coin correctly, otherwise the sentence was six years (double-three). The 'expected jail time,' then would be three years (the simple average of 0 and 6). 
    The prisoner's proposal had three outcomes -- zero, one, and two. The 'expected jail time' would be only one year (the simple average of 0, 1, and 2). 
The judge did not go for the prisoner's proposal, however.  Instead he pronounced a sentence with a jail time of 0, 1, 2, 3,... or any number of years depending on the 'luck of the draw' at the end of each preceding term. What would be the 'expected jail time'? {Definition}
 
Groaner Alert


This sentence has an end. 
This sentence has no.


For more on self-reference,
see Elegancelessness.

The unsophisticated puzzle solver may recognize eventually that by reasoning forward in time, he or she will go wandering along an unlimited number of alternative mental pathways -- as if climbing an indefinitely large 'probability tree' with shrinking branches and twigs, each one associated with a jail time calculated with countless multiplications and summings until -- well, until "the sun flickers from the sky." {HyperNote}

The sophisticated puzzle solver, though, will recognize something else right away: That the Recursive Sentence is a recursive problem. {Definition}

There is only one unknown, the expected jail time. Let us act like we know what it is and merely call it x (see Hand Over Hand or Band Around the Earth). Here's what we do know: That at each and every draw, the prisoner can expect to stay in jail for x more years. The previous sentence deserves an exclamation point. 

    Each and every time the jailer shows up with his hat and three tokens, the judge's sentence is started all over again. 
At every drawing, there are only three outcomes not gazillions. Here they are: 0, x + 1, and x + 2.

In slow motion: 

  1. The prisoner, facing an expected jail time of x, may draw the token with zero printed on it and walk out the door (0 additional time). 
  2. The prisoner, facing an expected jail time of x, may draw the token with one printed on it and continue facing an expected jail time of x, after waiting one year (x + 1)
  3. The prisoner, facing an expected jail time of x, may draw the token with two printed on it and continue facing an expected jail time of x, after waiting two years (x + 2).
Each of these three outcomes are equally likely. In other words, each has a 1/3rd chance of occurring. The sophisticated solver will see an opportunity to write an equation:
    x = (0) *1/3 + (x + 1) * 1/3 + (x + 2) * 1/3,
which he or she then solves for x, something like this...
    x = x/3 + 1/3 + x/3 + 2/3 
    3x = 2x + 1 + 2 
    x = 1 + 2
The expected jail term is three years.

But wait: An expected jail term of three years is the same as the judge's original sentence. Maybe that sentence should have an exclamation point. Why is the prisoner singing a cheerful tune?  If you are not surprised, why not? {Gambler's Play-Off}

Hoo-ha (a personal 'expletive-of-discovery', often followed by an exclamation point). The final version of the equation for x can be put into a more general form.

    x = 1 + 2 
    x = a + b
...which suggests that the jailer might have been mandated to print up the tokens with 0, a, and b, and the values of a and b could be chosen arbitrarily by the judge, to create any number of punishments for the gambler and puzzles for us. 

Instead of punishments, they might represent rewards, so that x becomes an 'expected payoff.'

    Three tokens are printed with 0, 1, and 2. You win a quantity of marshmallows corresponding to the number that you draw, and you may keep drawing tokens until you get sick of marshmallows -- or until you draw a zero, at which time you must leave the campfire circle.
Sophisticated solvers will recognize a and b as 'parameters.'  Not only that, but if there were n+1 tokens, printed with 0, a1, a2 ,... an, the number of possible puzzles would be even larger than -- well, larger than 'any number.' For equally likely tokens, the value of x will be given by a1+ a2 + ... an.

Or the puzzle maker may set any combination of payoffs equal to each other. 

    You might enjoy creating a variation of the gambler's proposal by changing the sentencing units to months instead of years. How many tokens would the jailor have to print up in order to match the expected jail time (x = 36 months) imposed in the judge's original sentence?
Consider a puzzle in which a1 = a2 = ... an= A, in which x = n * A.
    There are six tokens printed with 0, H, H, H, H, H. You win some huge amount of money every time you draw an H, and you may keep drawing tokens until you get as rich as you ever wanted to be or until you draw a 0, at which time you -- well, you die. 
Don't blame me. I didn't make up the rules of 'Russian Roulette.'

 
 
 
HyperNote: Forward -- But Not Straight

We might begin our analysis of the gambler's sentence by observing that on the first draw, there is a 1/3 chance that the prisoner will be released immediately, a 1/3 chance that the prisoner will stay in jail for one year before the second draw, and a 1/3 chance that the prisoner will stay in jail for two years before the second draw. On the second draw, there is a 1/3 chance that the prisoner will be released immediately, after having spent either one year in jail or two years in jail, a 1/3 chance that the prisoner will stay in jail for one year, after having spent either one year in jail or two years in jail, before the third draw, and a 1/3 chance that the prisoner will stay in jail for two years, after having spent either one year in jail or two years in jail before the third draw. On the third draw, there is a 1/3 chance that the prisoner will be released immediately, after having spent either one year in jail or two years in jail or three years in jail or four years in jail, a 1/3 chance that the prisoner will stay in jail for one year, after having spent either one year in jail or two years in jail or three years in jail or four years in jail, before the fourth draw, and a 1/3 chance that the prisoner will stay in jail for two years, after having spent either one year in jail or two years in jail or three years in jail or four years in jail before the fourth draw. On the fourth draw,... You get the idea.

Now, we know that there is a 1/3 chance that the prisoner will be released after the first draw, for which the expected jail time is 0. We know that there is a (2/3)(1/3) chance that the prisoner will be released after the second draw, for which the expected jail time is (0+1+2)/3. We know that there is a (2/3)(2/3)(1/3) chance that the prisoner will be released after the third draw, for which the expected jail time is 2(0+1+2)/3. We know that there is a (2/3)(2/3)(2/3)(1/3) chance that the prisoner will be released after the fourth draw, for which the expected jail time is 3(0+1+2)/3. We know that... You get the idea. Then, since the 'expected value' is defined as the sum of the values of a random variable with each value multiplied by its probability of occurrence, all we have to do is multiply each probability by its respective jail time and add up the results.

    There must be a better way. {Return}

Gambler's Play-Off

Standing in the 'slot room' of a Las Vegas casino, I watched with fascination as a row of solemn persons labored by the hour over their machines, brows furrowed, lips pulled taut, fingers feeding slots, hands pulling handles -- rhythmic gestures of attrition, eyes glazed -- undistracted by the wheeling icons -- fruits and bars and bells, spinning and jolting and re-blurring in mechanical impudence.

      Las Vegas has a name for the phenomenon: Grind.
    All at once I heard bells ringing, accompanied by clattering and cheering. One of the machines was happily vomiting coins. A woman in stretch-pants gathered up her winnings in a popcorn bucket and turned to leave.

    "Hey!" hollered a nearby supplicant, pointing at the bucket-of-coins. "Aren't you going to play those off?"

The prisoner in the puzzle proposed a Recursive Sentence. It was apparently a stratagem not so much intended to trick the judge into leniency (a reduced expected sentence) but instead to fulfill the gambler's psychological penchant -- not so much to win but to gamble.{Return}
-- PN

Expected Value

noun (1947) 1: the sum of the values of a random variable with each value multiplied by its probability of occurrence 2: the integral of the product of a probability density function of a continuous random variable and the random variable itself when taken over all possible values of the variable {Return}

-- Merriam-Webster's Collegiate Dictionary

Recursive

adjective (1934) 1: of, relating to, or involving recursion ?a recursive function in a computer program> 2: of, relating to, or constituting a procedure that can repeat itself indefinitely ?a recursive rule in a grammar> -- re.cur.sive.ly adv -- re.cur.sive.ness n

recursion noun [Late Latin recursion-, recursio, from recurrere] (1616) 1: return 2: the determination of a succession of elements (as numbers or functions) by operation on one or more preceding elements according to a rule or formula involving a finite number of steps 3: a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself in a step having a termination condition so that successive repetitions are processed up to the critical step until the condition is met at which time the rest of each repetition is processed from the last one called to the first -- compare to 'iteration'

-- Merriam-Webster's Collegiate Dictionary
    The earliest use of recursion is thought to be attributable to the mathematician Leonardo of Pisa, also called Fibonacci (see Prolix), who published an influential treatise, Liber abaci in 1202. The Fibonacci series 1, 2, 3, 5, 8,... is generated by adding the n-1st term to the nth to produce the n+1st. {Return}

Parameter

pa.ram.e.ter n [NL, fr. para- + Gk metron measure] (1656) 1 a: an arbitrary constant whose value characterizes a member of a system (as a family of curves); also: a quantity (as a mean or variance) that describes a statistical population b: an independent variable used to express the coordinates of a variable point and functions of them--compare parametric equation 2: any of a set of physical properties whose values determine the characteristics or behavior of something (parameters of the atmosphere such as temperature, pressure, and density) 3: something represented by a parameter: a characteristic element; broadly: characteristic, element, factor (political dissent as a parameter of modern life) 4: limit, boundary--usu. used in pl. (the parameters of science fiction) -- para.met.ric adj -- para.met.ri.cal.ly adv

-- Merriam-Webster's Collegiate Dictionary
{Return}


Background

The Recursive Sentence puzzle owes its inspiration to the venerable Three Dark Tunnel problem that circulates among brain-teaser newsgroups every once-in-a-while -- probably recursively. It was submitted by John Swanson, of Mission Viejo, California. {Return}



Home Page
Puzzle Page
Math and Models
The Puzzle as a Literary Genre