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?
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
Private Sub Form_Load()
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 |
With computer assistance