All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 One up (Posted on 2014-08-22)
Start with a unit square (n=1). At each step, randomly increase either the Length or Width (with equal chance) by 1 unit, for example, by the time n=3 there is either a 1x3 or a 2x2 rectangle. What is the expected value of the area at step n?

 See The Solution Submitted by Larry No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 With computer assistance Comment 1 of 1
At the point of step n, there have been n-1 expansions. If H is the number that have been made horizontally, then n-1-H is the number that have been made vertically. The distribution of horizontal and vertical pairings is given by C(n-1,H) / 2^(n-1) and H can range from zero to n-1. To get the expected value, each of these n values is multiplied by the area (H+1)*((n-1-H)+1) and the products summed.

The result is Sigma{H=0 to n-1}(C(n-1,H)/2^(n-1) * (H+1)*((n-H)))

For example, when n=4, there's

a 1/8 probability of no horizontal moves for an area of 4.
a 3/8 probability of one horizontal move and two vertical for an area of 6.
a 3/8 probability of two horizontal moves and one vertical for an area of 6.
a 1/8 probability of all horizontal moves for an area of 4.

The expected value is then 4/8 + 18/8 + 18/8 + 4/8 = 44/8 = 11/2.

The following program evaluates this for n = 1 to 20, before doing a simulation of the same range. As seen in the comment below the results, this summation formula can be collapsed into a direct closed formula.

This calculates the expected values for n = 1 through 20, and then does simulations of that same range.

The results follow:

`  n      exp. area  1        1.00  2        2.00  3        3.50  4        5.50  5        8.00  6       11.00  7       14.50  8       18.50  9       23.00 10       28.00 11       33.50 12       39.50 13       46.00 14       53.00 15       60.50 16       68.50 17       77.00 18       86.00 19       95.50 20      105.50`

Simulation results:

` 1 1 2 2 3 3.5036 4 5.477 5 8.0074 6 10.9652 7 14.4534 8 18.485 9 22.9953 10 28.0258 11 33.5186 12 39.5192 13 45.9705 14 53.0502 15 60.5395 16 68.5772 17 77.0263 18 86.0752 19 95.5208 20 105.4788`

The formula works out to A = n * (n+1) / 4 + 1/2.

This amounts to 1/2 more than half the nth triangular number or half of one more than the nth triangular number.

The program:

DefDbl A-Z
Dim crlf\$

Function mform\$(x, t\$)
a\$ = Format\$(x, t\$)
If Len(a\$) < Len(t\$) Then a\$ = Space\$(Len(t\$) - Len(a\$)) & a\$
mform\$ = a\$
End Function

ChDir "C:\Program Files (x86)\DevStudio\VB\projects\flooble"
Text1.Text = ""
crlf\$ = Chr(13) + Chr(10)
Form1.Visible = True
DoEvents

For n = 1 To 20
exparea = 0
For eh = 0 To n - 1
ev = n - eh - 1
exparea = exparea + combi(n - 1, eh) * (ev + 1) * (eh + 1)
Next
exparea = exparea / 2 ^ (n - 1)
Text1.Text = Text1.Text & mform(n, "##0") & mform(exparea, "########0.00") & crlf
Next n
Text1.Text = Text1.Text & crlf
For n = 1 To 20
tot = 0
For trial = 1 To 10000
v = 1: h = 1
For i = 1 To n - 1
If Rnd(1) < 0.5 Then v = v + 1 Else h = h + 1
Next
area = v * h

tot = tot + area
avrg = tot / trial
Next trial
Text1.Text = Text1.Text & Str(n) & Str(avrg) & crlf
Next n

Text1.Text = Text1.Text & crlf & " done"
End Sub

Function combi(n, r)
c = 1
For i = n To n - r + 1 Step -1
c = c * i
Next
For i = 2 To r
c = c / i
Next
combi = c
End Function

 Posted by Charlie on 2014-08-22 12:33:30

 Search: Search body:
Forums (0)