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

Home > Probability
A biased random walk (Posted on 2016-12-01) Difficulty: 3 of 5
Consider a random walk on the number line where, at each step, the position (call it x) may change by +1 (to the right) or −1 (to the left) with probabilities:
p(go right)= 1/2+1/2*(x/(1+abs(x)) for abs(x)below 8
p(go right)=0 for x=8
p(go right)=1 for x= -8
p(go left)= 1- p(go right)

If 10000 steps of a walk are taken into account: :
a. What is the distribution of distances x appearing in the chain 01212343234543 … etc ... :
b: Explain why the said distribution is in the long run independent of the initial state.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts computer exploration Comment 1 of 1
The program conducts 20 trials at each starting position (state) from zero to 8, as negative positions would be a mirror image of the positive positions. The results are:

(Each set of 20 trials is followed by a line for the accumulated totals at each position.)

Starting at 0
 0 0 0 0 0 0 0 1 2 1 1 1 3 29 306 4968 4689
 4641 4972 353 25 4 1 1 2 2 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 1 2 2 18 295 4979 4702
 4678 4964 316 32 5 3 1 1 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 1 1 1 19 324 4979 4674
 4655 4968 340 30 4 1 1 1 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 2 2 1 3 29 351 4968 4644
 4685 4971 309 25 4 3 2 1 1 0 0 0 0 0 0 0 0
 4681 4967 314 29 2 1 2 3 2 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 1 1 5 23 331 4975 4663
 4664 4978 333 19 1 1 2 2 1 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 2 6 9 37 351 4956 4638
 4672 4979 326 19 1 1 1 1 1 0 0 0 0 0 0 0 0
 4674 4974 321 22 3 2 1 1 2 1 0 0 0 0 0 0 0
 4666 4977 329 20 3 2 2 1 1 0 0 0 0 0 0 0 0
 4679 4978 317 19 2 1 1 2 2 0 0 0 0 0 0 0 0
 4655 4965 338 32 5 1 1 1 2 1 0 0 0 0 0 0 0
 4692 4972 303 24 2 1 1 2 3 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 1 2 2 2 23 330 4974 4666
 4640 4965 351 29 5 2 2 4 3 0 0 0 0 0 0 0 0

 60682 64630 4250 325 41 20 18 23 10 11 10 14 25 178 2288 34799 32676
 
This case obviously flip-flops, with an equal likelihood of going right or left. The imbalance in the final totals represents just the happenstance of more cases going left than right (12 left and 8 right--not statistically significant). 


Starting at 1
 0 0 0 0 0 0 0 0 0 1 1 3 7 32 331 4965 4661
 4681 4971 311 23 2 2 2 2 2 2 2 1 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 1 1 1 2 15 295 4984 4702
 4641 4964 352 33 4 1 1 2 2 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 1 1 3 6 28 321 4969 4672
 0 0 0 0 0 0 0 1 2 5 5 2 2 29 349 4964 4642
 0 0 0 0 0 0 0 0 0 1 1 1 1 19 288 4980 4710
 0 0 0 0 0 0 0 0 1 2 1 2 4 29 339 4968 4655
 0 0 0 0 0 0 0 0 0 1 1 1 2 32 344 4967 4653
 0 0 0 0 0 0 0 0 0 1 1 1 2 26 347 4973 4650
 0 0 0 0 0 0 0 0 0 1 1 1 4 25 348 4974 4647
 0 0 0 0 0 0 0 0 0 1 2 2 2 19 284 4979 4712
 0 0 0 0 0 0 0 0 0 1 1 1 4 40 348 4959 4647
 0 0 0 0 0 0 0 0 0 1 1 1 4 29 330 4970 4665
 0 0 0 0 0 0 0 0 0 2 2 1 1 15 325 4983 4672
 0 0 0 0 0 0 0 0 0 1 1 2 3 18 329 4980 4667
 4676 4970 318 28 4 1 1 1 1 1 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 1 2 2 2 24 329 4974 4667
 0 0 0 0 0 0 0 0 0 1 1 1 1 19 308 4980 4690
 0 0 0 0 0 0 0 0 0 1 1 1 3 30 316 4969 4680

 13998 14905 981 84 10 4 4 6 8 7 26 27 50 429 5531 84538 79392
 
With the initial placement at position 1, there is now a definite bias toward going to the right. Also, when going in the opposite direction, there is (1) the necessity that at least +1 is represented at least once and (2) the dearth in the non-chosen direction is not as severely restricted (the first instance of ultimately going negative includes a foray to +3). On the other hand those that ultimately go to the positive direction show an increased dearth in the negative, many not even getting to zero. 


Starting at 2
 0 0 0 0 0 0 0 0 0 0 1 1 4 33 344 4966 4652
 0 0 0 0 0 0 0 0 0 0 1 1 5 23 309 4976 4686
 0 0 0 0 0 0 0 0 0 0 1 1 5 35 356 4964 4639
 0 0 0 0 0 0 0 0 0 0 1 1 7 31 318 4968 4675
 0 0 0 0 0 0 0 0 0 0 1 2 3 27 338 4971 4659
 0 0 0 0 0 0 0 0 0 0 1 2 7 39 350 4959 4643
 0 0 0 0 0 0 0 0 0 0 1 1 3 25 347 4974 4650
 0 0 0 0 0 0 0 0 0 0 1 1 3 27 330 4972 4667
 0 0 0 0 0 0 0 0 0 0 1 1 6 26 325 4973 4669
 0 0 0 0 0 0 0 0 0 0 1 1 3 22 327 4977 4670
 0 0 0 0 0 0 0 0 0 0 1 1 4 28 334 4971 4662
 0 0 0 0 0 0 0 0 0 0 1 1 1 20 327 4979 4672
 0 0 0 0 0 0 0 0 0 0 1 1 2 22 310 4977 4688
 0 0 0 0 0 0 0 0 0 0 1 1 6 35 344 4964 4650
 0 0 0 0 0 0 0 0 0 0 1 1 5 30 361 4969 4634
 0 0 0 0 0 0 0 0 0 0 1 1 2 32 354 4967 4644
 0 0 0 0 0 0 0 0 0 0 1 1 5 42 382 4957 4613
 0 0 0 0 0 0 0 0 0 0 1 2 4 32 340 4966 4656
 0 0 0 0 0 0 0 0 0 1 2 1 3 25 324 4973 4672
 0 0 0 0 0 0 0 0 0 0 2 2 1 30 356 4968 4642

 0 0 0 0 0 0 0 0 0 1 2 24 79 584 6776 99391 93143
 
All in this instance go to the right, when the initial position is 2.  I'm sure there's some small probability that it would eventually go left, but it's so small it doesn't show up in this particular sample at sample-size 20.


Starting at 3
 0 0 0 0 0 0 0 0 0 0 0 1 5 36 369 4964 4626
 0 0 0 0 0 0 0 0 0 0 1 2 2 32 360 4967 4637
 0 0 0 0 0 0 0 0 0 0 0 1 1 15 309 4985 4690
 0 0 0 0 0 0 0 0 0 0 0 2 4 19 294 4980 4702
 0 0 0 0 0 0 0 0 1 2 2 3 7 38 363 4958 4627
 0 0 0 0 0 0 0 0 0 0 0 1 4 29 343 4971 4653
 0 0 0 0 0 0 0 0 0 0 0 1 2 34 352 4966 4646
 0 0 0 0 0 0 0 0 0 0 0 1 4 33 363 4967 4633
 0 0 0 0 0 0 0 0 0 0 1 4 6 33 351 4964 4642
 0 0 0 0 0 0 0 0 0 0 0 1 2 28 329 4972 4669
 0 0 0 0 0 0 0 0 0 0 0 1 2 25 332 4975 4666
 0 0 0 0 0 0 0 0 0 0 0 2 6 31 330 4968 4664
 0 0 0 0 0 0 0 0 0 0 0 1 6 27 323 4973 4671
 0 0 0 0 0 0 0 0 0 0 0 1 2 35 344 4965 4654
 0 0 0 0 0 0 0 0 0 0 0 1 2 36 342 4964 4656
 0 0 0 0 0 0 0 0 0 0 1 2 6 30 316 4969 4677
 0 0 0 0 0 0 0 0 0 0 1 2 1 14 294 4985 4704
 0 0 0 0 0 0 0 0 0 0 0 1 2 25 329 4975 4669
 0 0 0 0 0 0 0 0 0 0 0 1 2 29 386 4971 4612
 0 0 0 0 0 0 0 0 0 0 0 1 2 23 324 4977 4674

 0 0 0 0 0 0 0 0 1 2 6 10 68 572 6753 99416 93172
 
Happenstance does bring back one foray into the zero position here, but the overall bias increases, but not by much. 


Starting at 4
 0 0 0 0 0 0 0 0 0 0 0 2 10 41 329 4957 4662
 0 0 0 0 0 0 0 0 0 0 0 0 2 30 367 4970 4632
 0 0 0 0 0 0 0 0 0 0 0 1 6 26 341 4973 4654
 0 0 0 0 0 0 0 0 0 0 0 0 2 20 335 4980 4664
 0 0 0 0 0 0 0 0 0 0 0 0 2 26 354 4974 4645
 0 0 0 0 0 0 0 0 0 0 0 1 10 29 332 4970 4659
 0 0 0 0 0 0 0 0 0 0 0 2 6 26 344 4972 4651
 0 0 0 0 0 0 0 0 0 0 0 0 1 12 312 4988 4688
 0 0 0 0 0 0 0 0 0 0 0 0 5 33 331 4967 4665
 0 0 0 0 0 0 0 0 0 0 0 0 2 25 355 4975 4644
 0 0 0 0 0 0 0 0 0 0 0 0 2 33 351 4967 4648
 0 0 0 0 0 0 0 0 0 0 0 0 1 23 344 4977 4656
 0 0 0 0 0 0 0 0 0 0 0 0 1 22 316 4978 4684
 0 0 0 0 0 0 0 0 0 0 0 0 2 27 323 4973 4676
 0 0 0 0 0 0 0 0 0 0 0 0 3 31 360 4969 4638
 0 0 0 0 0 0 0 0 0 0 0 0 4 30 330 4970 4667
 0 0 0 0 0 0 0 0 0 0 0 0 5 34 335 4966 4661
 0 0 0 0 0 0 0 0 0 0 0 1 3 37 344 4962 4654
 0 0 0 0 0 0 0 0 0 0 0 0 2 28 347 4972 4652
 0 0 0 0 0 0 0 0 0 0 0 0 4 35 386 4965 4611

 0 0 0 0 0 0 0 0 0 0 0 7 53 568 6836 99425 93111


Starting at 5
 0 0 0 0 0 0 0 0 0 0 0 0 7 42 339 4959 4654
 0 0 0 0 0 0 0 0 0 0 0 0 3 23 318 4978 4679
 0 0 0 0 0 0 0 0 0 0 0 0 3 20 330 4981 4667
 0 0 0 0 0 0 0 0 0 0 0 0 2 33 313 4968 4685
 0 0 0 0 0 0 0 0 0 0 0 0 2 29 387 4972 4611
 0 0 0 0 0 0 0 0 0 0 0 1 3 25 311 4975 4686
 0 0 0 0 0 0 0 0 0 0 0 0 0 19 346 4982 4654
 0 0 0 0 0 0 0 0 0 0 0 0 5 34 332 4967 4663
 0 0 0 0 0 0 0 0 0 0 0 0 1 29 335 4972 4664
 0 0 0 0 0 0 0 0 0 0 0 0 4 28 325 4973 4671
 0 0 0 0 0 0 0 0 0 0 0 0 1 22 321 4979 4678
 0 0 0 0 0 0 0 0 0 0 0 0 2 25 361 4976 4637
 0 0 0 0 0 0 0 0 0 0 0 0 7 33 299 4968 4694
 0 0 0 0 0 0 0 0 0 0 0 0 2 35 360 4966 4638
 0 0 0 0 0 0 0 0 0 0 0 0 1 28 320 4973 4679
 0 0 0 0 0 0 0 0 0 0 0 0 3 33 355 4968 4642
 0 0 0 0 0 0 0 0 0 0 0 0 1 26 332 4975 4667
 0 0 0 0 0 0 0 0 0 0 0 0 6 37 357 4964 4637
 0 0 0 0 0 0 0 0 0 0 0 0 5 29 356 4972 4639
 0 0 0 0 0 0 0 0 0 0 0 0 3 27 321 4974 4676

 0 0 0 0 0 0 0 0 0 0 0 1 61 557 6718 99442 93221


Starting at 6
 0 0 0 0 0 0 0 0 0 0 0 0 2 27 348 4973 4651
 0 0 0 0 0 0 0 0 0 0 0 0 1 24 316 4976 4684
 0 0 0 0 0 0 0 0 0 0 0 0 1 21 341 4979 4659
 0 0 0 0 0 0 0 0 0 0 0 0 4 33 351 4967 4646
 0 0 0 0 0 0 0 0 0 0 0 0 4 33 343 4967 4654
 0 0 0 0 0 0 0 0 0 0 0 1 4 30 343 4969 4654
 0 0 0 0 0 0 0 0 0 0 0 0 0 19 319 4981 4682
 0 0 0 0 0 0 0 0 0 0 0 2 7 32 324 4966 4670
 0 0 0 0 0 0 0 0 0 0 0 0 1 20 361 4980 4639
 0 0 0 0 0 0 0 0 0 0 0 0 0 29 383 4971 4618
 0 0 0 0 0 0 0 0 0 0 0 0 3 31 326 4969 4672
 0 0 0 0 0 0 0 0 0 0 0 0 2 26 307 4974 4692
 0 0 0 0 0 0 0 0 0 0 0 0 1 22 335 4978 4665
 0 0 0 0 0 0 0 0 0 0 0 0 2 34 368 4966 4631
 0 0 0 0 0 0 0 0 0 0 0 1 6 32 349 4967 4646
 0 0 0 0 0 0 0 0 0 0 0 0 3 24 324 4976 4674
 0 0 0 0 0 0 0 0 0 0 0 0 4 23 324 4977 4673
 0 0 0 0 0 0 0 0 0 0 0 0 1 24 350 4976 4650
 0 0 0 0 0 0 0 0 0 0 0 0 0 26 317 4974 4684
 0 0 0 0 0 0 0 0 0 0 0 0 0 24 373 4976 4628

 0 0 0 0 0 0 0 0 0 0 0 4 46 534 6782 99462 93172


Starting at 7
 0 0 0 0 0 0 0 0 0 0 0 0 3 17 304 4984 4693
 0 0 0 0 0 0 0 0 0 0 0 0 0 24 351 4977 4649
 0 0 0 0 0 0 0 0 0 0 0 0 0 18 317 4983 4683
 0 0 0 0 0 0 0 0 0 0 0 0 0 24 324 4977 4676
 0 0 0 0 0 0 0 0 0 0 0 0 5 30 355 4971 4640
 0 0 0 0 0 0 0 0 0 0 0 0 1 25 330 4976 4669
 0 0 0 0 0 0 0 0 0 0 0 0 4 32 363 4969 4633
 0 0 0 0 0 0 0 0 0 0 0 0 3 31 355 4970 4642
 0 0 0 0 0 0 0 0 0 0 0 0 1 22 349 4979 4650
 0 0 0 0 0 0 0 0 0 0 0 1 3 25 324 4975 4673
 0 0 0 0 0 0 0 0 0 0 0 0 3 24 319 4977 4678
 0 0 0 0 0 0 0 0 0 0 0 0 2 28 333 4973 4665
 0 0 0 0 0 0 0 0 0 0 0 0 0 24 324 4977 4676
 0 0 0 0 0 0 0 0 0 0 0 0 1 28 341 4973 4658
 0 0 0 0 0 0 0 0 0 0 0 0 4 27 370 4974 4626
 0 0 0 0 0 0 0 0 0 0 0 0 1 29 297 4972 4702
 0 0 0 0 0 0 0 0 0 0 0 0 5 30 322 4971 4673
 0 0 0 0 0 0 0 0 0 0 0 0 2 23 339 4978 4659
 0 0 0 0 0 0 0 0 0 0 0 1 2 21 310 4979 4688
 0 0 0 0 0 0 0 0 0 0 0 0 0 21 331 4980 4669

 0 0 0 0 0 0 0 0 0 0 0 2 40 503 6658 99495 93302


Starting at 8
 0 0 0 0 0 0 0 0 0 0 0 0 2 29 355 4971 4644
 0 0 0 0 0 0 0 0 0 0 0 3 6 27 321 4970 4674
 0 0 0 0 0 0 0 0 0 0 0 0 1 35 338 4965 4662
 0 0 0 0 0 0 0 0 0 0 0 0 0 17 318 4983 4683
 0 0 0 0 0 0 0 0 0 0 0 0 4 30 307 4970 4690
 0 0 0 0 0 0 0 0 0 0 0 0 2 28 346 4972 4653
 0 0 0 0 0 0 0 0 0 0 0 0 1 37 337 4963 4663
 0 0 0 0 0 0 0 0 0 0 0 0 3 36 363 4964 4635
 0 0 0 0 0 0 0 0 0 0 0 0 0 30 333 4970 4668
 0 0 0 0 0 0 0 0 0 0 0 0 0 20 359 4980 4642
 0 0 0 0 0 0 0 0 0 0 0 0 1 23 342 4977 4658
 0 0 0 0 0 0 0 0 0 0 0 0 1 27 325 4973 4675
 0 0 0 0 0 0 0 0 0 0 0 0 0 30 337 4970 4664
 0 0 0 0 0 0 0 0 0 0 0 0 2 21 332 4979 4667
 0 0 0 0 0 0 0 0 0 0 0 0 2 22 295 4978 4704
 0 0 0 0 0 0 0 0 0 0 0 0 1 32 342 4968 4658
 0 0 0 0 0 0 0 0 0 0 0 0 1 22 342 4978 4658
 0 0 0 0 0 0 0 0 0 0 0 0 3 28 319 4972 4679
 0 0 0 0 0 0 0 0 0 0 0 0 0 22 337 4978 4664
 0 0 0 0 0 0 0 0 0 0 0 0 0 23 318 4977 4683

 0 0 0 0 0 0 0 0 0 0 0 3 30 539 6666 99458 93304

By this time the bias is definitely more pronounced: In the 20 trials, the position never gets below 3. The case for initial position 8 is of course almost identical to initial position 7, as position 7 always immediately follows position 8, so we'd have an expected excess of only 1 for the 8's.

Again: biases toward the right would be equally to the left if negative initial positions were chosen.




DefDbl A-Z
Dim crlf$, numTimes(), cumulative()


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
For stPos = 0 To 8
 Text1.Text = Text1.Text & crlf & crlf & "Starting at " & stPos & crlf
 ReDim cumulative(-8 To 8)
For tr = 1 To 20
 Randomize Timer
 
 ReDim numTimes(-8 To 8)
 numTimes(stPos) = 1
 psn = stPos
 For i = 1 To 10000
   Select Case psn
      Case -8
        p = 1
      Case 8
        p = 0
      Case Else
        p = 0.5 + 0.5 * psn / (1 + Abs(psn))
   End Select
   r = Rnd(1)
   If r <= p Then
     psn = psn + 1
   Else
     psn = psn - 1
   End If
   numTimes(psn) = numTimes(psn) + 1
   cumulative(psn) = cumulative(psn) + 1
 Next
 
 For i = -8 To 8
  Text1.Text = Text1.Text & Str(numTimes(i))
 Next
 Text1.Text = Text1.Text & crlf
 
 
Next tr
 Text1.Text = Text1.Text & crlf
 For i = -8 To 8
  Text1.Text = Text1.Text & Str(cumulative(i))
 Next
 Text1.Text = Text1.Text & crlf
 DoEvents
Next stPos
 
 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

  Posted by Charlie on 2016-12-01 09:21:44
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 (1)
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