Department of Computer Science

A simple bounded random walk - a probabilistic model

Introduction

This is the RoboChart model for a simple random walk.

Model (download)

Properties

  • config.assertions
package prism_config

constants C_fair_MD10_MS20_100:
	SRWMod::SRWRP::MaxDist set to 10, 
	SRWMod::SRWRP::MaxSteps from set {20 to 100 by step 10}, and
	SRWMod::SRWRP::Pl set to 0.5
	
constants C_biased_MD10_MS20_100:
	SRWMod::SRWRP::MaxDist set to 10, 
	SRWMod::SRWRP::MaxSteps from set {20 to 100 by step 10}, and
	SRWMod::SRWRP::Pl from set {0.1, 0.3, 0.6, 0.8}
	
defs D_no_recharge:
	pfunction Plus(v, maxv) = {
		return (if (($$v) < ($$maxv)) then ($$v+1) else ($$v) end)
	}
	
	pfunction Minus(v, minv) = {
		return (if (($$v) > ($$minv)) then ($$v-1) else ($$v) end)
	}
	
	pfunction Update(v, maxv, origin) = {
		return (if (($$v) < ($$maxv)) then ($$v+1) else ($$v) end)
	}
	
defs D_recharge:
	pfunction Plus(v, maxv) = {
		return (if (($$v) < ($$maxv)) then ($$v+1) else ($$v) end)
	}
	
	pfunction Minus(v, minv) = {
		return (if (($$v) > ($$minv)) then ($$v-1) else ($$v) end)
	}
	
	pfunction Update(v, maxv, origin) = {
		return (if $$origin then 0 else 
				(if (($$v) < ($$maxv)) then ($$v+1) else ($$v) end)
			end)
	}
	
  • SRW.assertions
package SRW_properties

import prism_config::*

label l_stuck = 
	SRWMod::ctrl_ref::stm_ref is in 
		SRWMod::ctrl_ref::stm_ref::Stuck
		
label l_origin = (SRWMod::SRWRP::x == 0)
		
prob property P_deadlock_free:
	not Exists [Finally deadlock]
	with constants C_fair_MD10_MS20_100
	with definitions D_no_recharge
	
prob property P_stuck_not_origin:
	Prob=? of [Finally 
		#l_stuck /\ not #l_origin
	]
	with constants C_fair_MD10_MS20_100
	with definitions D_no_recharge
	
prob property P_stuck_not_origin_recharge:
	Prob=? of [Finally 
		#l_stuck /\ not #l_origin
	]
	with constants C_fair_MD10_MS20_100
	with definitions D_recharge
	
prob property P_stuck_not_origin_biased:
	Prob=? of [Finally 
		#l_stuck /\ not #l_origin
	]
	with constants C_biased_MD10_MS20_100
	with definitions D_no_recharge
	
rewards R_origins = 
	[ SRWMod::ctrl_ref::stm_ref::left.out ] (SRWMod::SRWRP::x == 0) : 1;
	[ SRWMod::ctrl_ref::stm_ref::right.out ] (SRWMod::SRWRP::x == 0) : 1;
endrewards

prob property R_stuck_not_origin:
	Reward {R_origins} =? of [Reachable 
		#l_stuck /\ not #l_origin
	]
	with constants C_fair_MD10_MS20_100
	with definitions D_no_recharge
	
prob property R_stuck_not_origin_recharge:
	Reward {R_origins} =? of [Reachable 
		#l_stuck /\ not #l_origin
	]
	with constants C_fair_MD10_MS20_100
	with definitions D_recharge
	
prob property R_stuck_not_origin_biased:
	Reward {R_origins} =? of [Reachable 
		#l_stuck /\ not #l_origin
	]
	with constants C_biased_MD10_MS20_100
	with definitions D_no_recharge

/*	
rewards R_l = 
	[ SRWMod::ctrl_ref::stm_ref::left.out ] true : 1;
endrewards

rewards R_r = 
	[ SRWMod::ctrl_ref::stm_ref::right.out ] true : 1;
endrewards
*/	

Reports

The verification results are displayed in the report below.


Results of analysis of assertions in SRW.assertions using PRISM

Results of probabilistic analysis of assertions in SRW.assertions using PRISM

Assertion: P_deadlock_free

Assertion Const Const Const states: transitions: result: checkTime:
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=20 MaxDist=10 1071 1211 true 0.015 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=30 MaxDist=10 1786 2021 true 0.013 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=40 MaxDist=10 2501 2831 true 0.008 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=50 MaxDist=10 3216 3641 true 0.008 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=60 MaxDist=10 3931 4451 true 0.02 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=70 MaxDist=10 4646 5261 true 0.021 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=80 MaxDist=10 5361 6071 true 0.012 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=90 MaxDist=10 6076 6881 true 0.014 seconds
P_deadlock_free SRWMod::SRWRP::Pl=0.5 MaxSteps=100 MaxDist=10 6791 7691 true 0.007 seconds

Assertion: P_stuck_not_origin

Assertion Const Const Const states: transitions: result: checkTime:
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=20 MaxDist=10 1071 1211 1.0 0.067 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=30 MaxDist=10 1786 2021 1.0 0.077 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=40 MaxDist=10 2501 2831 1.0 0.143 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=50 MaxDist=10 3216 3641 1.0 0.225 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=60 MaxDist=10 3931 4451 1.0 0.2 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=70 MaxDist=10 4646 5261 1.0 0.167 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=80 MaxDist=10 5361 6071 1.0 0.261 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=90 MaxDist=10 6076 6881 1.0 0.181 seconds
P_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=100 MaxDist=10 6791 7691 1.0 0.188 seconds

Assertion: P_stuck_not_origin_recharge

Assertion Const Const Const states: transitions: result: checkTime:
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=20 MaxDist=10 1088 1229 1.0 0.09 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=30 MaxDist=10 1773 2004 1.0 0.077 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=40 MaxDist=10 2458 2779 1.0 0.143 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=50 MaxDist=10 3143 3554 1.0 0.129 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=60 MaxDist=10 3828 4329 1.0 0.235 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=70 MaxDist=10 4513 5104 1.0 0.247 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=80 MaxDist=10 5198 5879 1.0 0.276 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=90 MaxDist=10 5883 6654 1.0 0.198 seconds
P_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=100 MaxDist=10 6568 7429 1.0 0.247 seconds

Assertion: P_stuck_not_origin_biased

Assertion Const Const Const states: transitions: result: checkTime:
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=20 MaxDist=10 1071 1211 1.0 0.075 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=20 MaxDist=10 1071 1211 1.0 0.071 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=20 MaxDist=10 1071 1211 1.0 0.071 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=20 MaxDist=10 1071 1211 1.0 0.088 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=30 MaxDist=10 1786 2021 1.0 0.121 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=30 MaxDist=10 1786 2021 1.0 0.084 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=30 MaxDist=10 1786 2021 1.0 0.054 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=30 MaxDist=10 1786 2021 1.0 0.068 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=40 MaxDist=10 2501 2831 1.0 0.096 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=40 MaxDist=10 2501 2831 1.0 0.082 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=40 MaxDist=10 2501 2831 1.0 0.127 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=40 MaxDist=10 2501 2831 1.0 0.139 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=50 MaxDist=10 3216 3641 1.0 0.217 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=50 MaxDist=10 3216 3641 1.0 0.17 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=50 MaxDist=10 3216 3641 1.0 0.146 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=50 MaxDist=10 3216 3641 1.0 0.177 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=60 MaxDist=10 3931 4451 1.0 0.187 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=60 MaxDist=10 3931 4451 1.0 0.206 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=60 MaxDist=10 3931 4451 1.0 0.171 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=60 MaxDist=10 3931 4451 1.0 0.199 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=70 MaxDist=10 4646 5261 1.0 0.171 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=70 MaxDist=10 4646 5261 1.0 0.173 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=70 MaxDist=10 4646 5261 1.0 0.24 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=70 MaxDist=10 4646 5261 1.0 0.173 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=80 MaxDist=10 5361 6071 1.0 0.246 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=80 MaxDist=10 5361 6071 1.0 0.188 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=80 MaxDist=10 5361 6071 1.0 0.176 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=80 MaxDist=10 5361 6071 1.0 0.263 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=90 MaxDist=10 6076 6881 1.0 0.288 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=90 MaxDist=10 6076 6881 1.0 0.179 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=90 MaxDist=10 6076 6881 1.0 0.166 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=90 MaxDist=10 6076 6881 1.0 0.269 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=100 MaxDist=10 6791 7691 1.0 0.284 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=100 MaxDist=10 6791 7691 1.0 0.265 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=100 MaxDist=10 6791 7691 1.0 0.184 seconds
P_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=100 MaxDist=10 6791 7691 1.0 0.295 seconds

Assertion: R_stuck_not_origin

Assertion Const Const Const states: transitions: result: checkTime:
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=20 MaxDist=10 1071 1211 2.5239410400390625 0.111 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=30 MaxDist=10 1786 2021 3.3342087790369987 0.092 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=40 MaxDist=10 2501 2831 4.018483284948161 0.116 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=50 MaxDist=10 3216 3641 4.6296200719371114 0.188 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=60 MaxDist=10 3931 4451 5.1968540647430155 0.293 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=70 MaxDist=10 4646 5261 5.73755329792438 0.225 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=80 MaxDist=10 5361 6071 6.2621930538154436 0.224 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=90 MaxDist=10 6076 6881 6.777110588667294 0.212 seconds
R_stuck_not_origin SRWMod::SRWRP::Pl=0.5 MaxSteps=100 MaxDist=10 6791 7691 7.28614208690988 0.283 seconds

Assertion: R_stuck_not_origin_recharge

Assertion Const Const Const states: transitions: result: checkTime:
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=20 MaxDist=10 1088 1229 4.6754830098358235 0.12 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=30 MaxDist=10 1773 2004 5.934770598423242 0.141 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=40 MaxDist=10 2458 2779 7.075444824781105 0.198 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=50 MaxDist=10 3143 3554 8.23487594624168 0.326 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=60 MaxDist=10 3828 4329 9.490328402810823 0.287 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=70 MaxDist=10 4513 5104 10.888069299632935 0.428 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=80 MaxDist=10 5198 5879 12.460842783184548 0.524 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=90 MaxDist=10 5883 6654 14.236824901401306 0.666 seconds
R_stuck_not_origin_recharge SRWMod::SRWRP::Pl=0.5 MaxSteps=100 MaxDist=10 6568 7429 16.244870526636518 0.497 seconds

Assertion: R_stuck_not_origin_biased

Assertion Const Const Const states: transitions: result: checkTime:
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=20 MaxDist=10 1071 1211 0.24999017529418222 0.06 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=20 MaxDist=10 1071 1211 1.337233215593495 0.089 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=20 MaxDist=10 1071 1211 2.139079785845883 0.084 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=20 MaxDist=10 1071 1211 0.6614029315027761 0.061 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=30 MaxDist=10 1786 2021 0.2499998636998548 0.068 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=30 MaxDist=10 1786 2021 1.4417769119677097 0.079 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=30 MaxDist=10 1786 2021 2.638052929366271 0.084 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=30 MaxDist=10 1786 2021 0.6661966178247976 0.073 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=40 MaxDist=10 2501 2831 0.2500000079069916 0.105 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=40 MaxDist=10 2501 2831 1.4787313204085661 0.125 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=40 MaxDist=10 2501 2831 2.9816348165885334 0.139 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=40 MaxDist=10 2501 2831 0.6666360416067811 0.143 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=50 MaxDist=10 3216 3641 0.2500000263772928 0.141 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=50 MaxDist=10 3216 3641 1.493052630686888 0.184 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=50 MaxDist=10 3216 3641 3.2332185131416775 0.154 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=50 MaxDist=10 3216 3641 0.666692509762742 0.145 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=60 MaxDist=10 3931 4451 0.2500000392134384 0.183 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=60 MaxDist=10 3931 4451 1.4994663226186244 0.181 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=60 MaxDist=10 3931 4451 3.4269584651117118 0.171 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=60 MaxDist=10 3931 4451 0.6667128714661867 0.173 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=70 MaxDist=10 4646 5261 0.25000005179760193 0.209 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=70 MaxDist=10 4646 5261 1.503059526147993 0.221 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=70 MaxDist=10 4646 5261 3.582980858466075 0.251 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=70 MaxDist=10 4646 5261 0.6667290976174807 0.198 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=80 MaxDist=10 5361 6071 0.25000006461902513 0.225 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=80 MaxDist=10 5361 6071 1.505634609102504 0.242 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=80 MaxDist=10 5361 6071 3.713744342050896 0.239 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=80 MaxDist=10 5361 6071 0.6667473844699701 0.219 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=90 MaxDist=10 6076 6881 0.2500000774267037 0.298 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=90 MaxDist=10 6076 6881 1.5078393859287555 0.263 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=90 MaxDist=10 6076 6881 3.8272472394909545 0.293 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=90 MaxDist=10 6076 6881 0.6667651879002251 0.26 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.100000 MaxSteps=100 MaxDist=10 6791 7691 0.2500000900330258 0.288 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.300000 MaxSteps=100 MaxDist=10 6791 7691 1.5099088011332162 0.275 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.600000 MaxSteps=100 MaxDist=10 6791 7691 3.928775728949201 0.2 seconds
R_stuck_not_origin_biased SRWMod::SRWRP::Pl=0.800000 MaxSteps=100 MaxDist=10 6791 7691 0.6667833805834948 0.292 seconds

Conclusion

Department of Computer Science
Deramore Lane, University of York, Heslington, York, YO10 5GH, UK
Tel: 01904 325500
University of York legal statements