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

Home > Probability
One up (Posted on 2014-08-22) Difficulty: 2 of 5
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?

No Solution Yet Submitted by Larry    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information