?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.relation=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F110%2F&rft.title=Sensitivity+of+Markov+chains+for+wireless%0Aprotocols&rft.creator=Allwright%2C+David&rft.creator=Dellar%2C+Paul&rft.subject=Information+and+communication+technology&rft.description=Network+communication+protocols+such+as+the+IEEE+802.11+wireless+protocol+are+currently+best+modelled+as+Markov+chains.+In+these+situations+we+have+some+protocol+parameters+%24%5Calpha%24%2C+and+a+transition+matrix+%24P(%5Calpha)%24+from+which+we+can+compute+the+steady+state+(equilibrium)+distribution+%24z(%5Calpha)%24+and+hence+final+desired+quantities+%24q(%5Calpha)%24%2C+which+might+be+for+example+the+throughput+of+the+protocol.+Typically+the+chain+will+have+thousands+of+states%2C+and+a+particular+example+of+interest+is+the+Bianchi+chain+defined+later.+Generally+we+want+to+optimise+%24q%24%2C+perhaps+subject+to+some+constraints+that+also+depend+on+the+Markov+chain.+To+do+this+efficiently+we+need+the+gradient+of+%24q%24+with+respect+to+%24%5Calpha%24%2C+and+therefore+need+the+gradient+of+%24z%24+and+other+properties+of+the+chain+with+respect+to+%24%5Calpha%24.+The+matrix+formulas+available+for+this+involve+the+so-called+fundamental+matrix%2C+but+are+there+approximate+gradients+available+which+are+faster+and+still+sufficiently+accurate%3F+In+some+cases+BT+would+like+to+do+the+whole+calculation+in+computer+algebra%2C+and+get+a+series+expansion+of+the+equilibrium+%24z%24+with+respect+to+a+parameter+in+%24P%24.+In+addition+to+the+steady+state+%24z%24%2C+the+same+questions+arise+for+the+mixing+time+and+the+mean+hitting+times.+Two+qualitative+features+that+were+brought+to+the+Study+Group%E2%80%99s+attention+were%3A%0A%0A++++*+the+transition+matrix+%24P%24+is+large%2C+but+sparse.%0A++++*+the+systems+of+linear+equations+to+be+solved+are+generally+singular+and+need+some+additional+normalisation+condition%2C+such+as+is+provided+by+using+the+fundamental+matrix.+%0A%0AWe+also+note+a+third+highly+important+property+regarding+applications+of+numerical+linear+algebra%3A%0A%0A++++*+the+transition+matrix+%24P%24+is+asymmetric.+%0A%0AA+realistic+dimension+for+the+matrix+%24P%24+in+the+Bianchi+model+described+below+is+8064%C3%978064%2C+but+on+average+there+are+only+a+few+nonzero+entries+per+column.+Merely+storing+such+a+large+matrix+in+dense+form+would+require+nearly+0.5GBytes+using+64-bit+floating+point+numbers%2C+and+computing+its+LU+factorisation+takes+around+80+seconds+on+a+modern+microprocessor.+It+is+thus+highly+desirable+to+employ+specialised+algorithms+for+sparse+matrices.+These+algorithms+are+generally+divided+between+those+only+applicable+to+symmetric+matrices%2C+the+most+prominent+being+the+conjugate-gradient+(CG)+algorithm+for+solving+linear+equations%2C+and+those+applicable+to+general+matrices.+A+similar+division+is+present+in+the+literature+on+numerical+eigenvalue+problems.&rft.date=2007-04-17&rft.type=Study+Group+Report&rft.type=NonPeerReviewed&rft.format=application%2Fpdf&rft.language=en&rft.identifier=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F110%2F1%2FBT-ProtocolReport.pdf&rft.identifier=++Allwright%2C+David+and+Dellar%2C+Paul++(2007)+Sensitivity+of+Markov+chains+for+wireless%0Aprotocols.++%5BStudy+Group+Report%5D+++++