%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                %%%
%%%         .         .           ..           .         .         %%%
%%%                                                                %%%
%%%                Random Walk Algorithms:  Bonus 1                %%%
%%%                                                                %%%
%%%                         David A. Meyer                         %%%
%%%                                                                %%%
%%%                                                                %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                                                                %%%
%%%                                                                %%%
%%%                       Typesetting notes                        %%%
%%%                                                                %%%
%%%                                                                %%%
%%% Plain TeX with a few simple macros at the beginning.           %%%
%%%                                                                %%%
%%% PostScript figures included with epsf.tex:                     %%%
%%%  TeX will complain about overfull \vbox s because of the way   %%%
%%%  I've typeset the figures.  Don't worry about it; the output   %%%
%%%  should be fine.                                               %%%
%%%                                                                %%%
%%% If AMS fonts are not loaded, comment the next line and         %%%
%%%  uncomment the following one.                                  %%%
\font\bbb=msbm10                                                   %%%
\font\bbs=msbm8                                                    %%%
\font\bbss=msbm7                                                   %%%
%\def\bbb{\bf}                                                     %%%
%%%                                                                %%%
%%%                                                                %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\input amssym.tex
\input color

\definecolor{review}{rgb}{0.25,0.75,0.25}
\definecolor{exercise}{rgb}{1,0,0}
\definecolor{lightgray}{rgb}{0.5,0.5,0.5}
\definecolor{Green}{rgb}{0.25,0.75,0.25}
\definecolor{purple}{rgb}{0.5,0,1}
\definecolor{orange}{rgb}{1,0.5,0}
\definecolor{def}{cmyk}{1,0,0,0.25}
%\definecolor{def}{rgb}{1,0.6,0.2}
\definecolor{author}{rgb}{0,0.6,0.2}
\definecolor{theorem}{rgb}{0,0,1}
%\definecolor{em}{cmyk}{0,1,0,0}
\definecolor{em}{rgb}{0.6,0,0.4}
\definecolor{note}{rgb}{1,0,0}
\definecolor{IPS}{rgb}{0.6941176,0,0.1294118}
\definecolor{ID}{rgb}{1,0,0}
\definecolor{TH}{rgb}{0,0,1}

\definecolor{jattebrown}{rgb}{0.38,0.23,0.14}
\definecolor{jatteyellow}{rgb}{0.47,0.47,0.25}
\definecolor{jatteblue}{rgb}{0.27,0.33,0.42}
\definecolor{snyellow}{rgb}{0.78,0.69,0.33}
\definecolor{sndark}{rgb}{0.18,0.23,0.22}
\definecolor{snblue}{rgb}{0.20,0.37,0.47}
\definecolor{lmlav}{rgb}{0.79,0.67,0.59}
\definecolor{lmgreen}{rgb}{0.42,0.46,0.4}
\definecolor{lmblue}{rgb}{0.53,0.54,0.58}

\overfullrule=0pt

\def\C{\hbox{\bbb C}} \def\sC{\hbox{\bbs C}} 
\def\N{\hbox{\bbb N}} \def\sN{\hbox{\bbs N}} 
\def\R{\hbox{\bbb R}} \def\sR{\hbox{\bbs R}} \def\ssR{\hbox{\bbss R}}
\def\Z{\hbox{\bbb Z}} \def\sZ{\hbox{\bbs Z}} \def\ssZ{\hbox{\bbss Z}}

\font\smallss=cmss8
\font\tinyss=cmss6
\font\medss=cmss10
\font\bigss=cmss17
\font\smallssbf=cmssbx8
\font\ssbf=cmssbx10
\font\bigssbf=cmssbx17
\font\ssdc=cmssdc10
\font\ssi=cmssi10
\font\smallssi=cmssi8
\font\ssq=cmssq8
\font\ssqi=cmssqi8

\def\AI{{\sl Artificial Intelligence}}
\def\AAM{{\sl Advances in Appl.\ Math.}}
\def\AeM{{\sl Aequationes Math.}}
\def\AM{{\sl Advances in Math.}}
\def\AnM{{\sl Ann.\ Math.}}
\def\AN{{\sl Amer.\ Nat.}}
\def\ANYAS{{\sl Ann.\ NY Acad.\ Sci.}}
\def\AP{{\sl Ann.\ Phys.}}
\def\APAL{{\sl Ann.\ Pure Appl.\ Logic}}
\def\APL{{\sl Appl.\ Phys.\ Lett.}}
\def\APS{{\sl Acta Physica Slovaca\/}}
\def\BAMS{{\sl Bull.\ Amer.\ Math.\ Soc.}}
\def\BLMS{{\sl Bull.\ Lond.\ Math.\ Soc.}}
\def\BSTJ{{\sl Bell System Tech.\ J.}}
\def\CACM{{\sl Commun.\ ACM\/}}
\def\CMP{{\sl Commun.\ Math.\ Phys.}}
\def\CPAM{{\sl Commun.\ Pure Appl.\ Math.}}
\def\CQG{{\sl Class.\ Quantum Grav.}}
\def\CS{{\sl Complex Systems\/}}
\def\CSF{{\sl Chaos, Solitons \& Fractals}}
\def\CSL{{\sl Computer, Speech and Language}}
\def\Di{{\sl Dialectica\/}}
\def\DM{{\sl Discrete Math.}}
\def\DMJDMV{{\sl Doc.\ Math.\ J. DMV}}
\def\EJ{{\sl Econom.\ J.}}
\def\EJC{{\sl European J. Combin.}}
\def\EL{{\sl Europhys.\ Lett.}}
\def\ForP{{\sl Fortsch.\ Phys.}}
\def\FP{{\sl Found.\ Phys.}}
\def\Gp{{\sl Geophysics\/}}
\def\GRG{{\sl Gen.\ Relativ.\ Grav.}}
\def\HN{{\sl Hum.\ Nature\/}}
\def\IEEEJSAC{{\sl IEEE J. Selected Areas Commun.}}
\def\IEEETAC{{\sl IEEE Trans.\ Automatic Control}}
\def\IEEETAES{{\sl IEEE Trans.\ Aerospace and Electronic Systems}}
\def\IEEETC{{\sl IEEE Trans.\ Computers}}
\def\IEEETIT{{\sl IEEE Trans.\ Inform.\ Theory}}
\def\IJCS{{\sl InterJournal Complex Systems}}
\def\IJMPB{{\sl Int.\ J. Mod.\ Phys.\ B}}
\def\IJMPC{{\sl Int.\ J. Mod.\ Phys.\ C}}
\def\IJTP{{\sl Int.\ J. Theor.\ Phys.}}
\def\IPL{{\sl Info.\ Processing Lett.}}
\def\IM{{\sl Invent.\ math.}}
\def\JA{{\sl J. Algorithms}}
\def\JACM{{\sl J. ACM\/}}
\def\JAP{{\sl J. Appl.\ Phys.}}
\def\JASA{{\sl J. Acoustical Soc.\ Amer.}}
\def\JCP{{\sl J. Comput.\ Phys.}}
\def\JCSS{{\sl J. Comp.\ Syst.\ Sci.}}
\def\JEL{{\sl J. Econom.\ Lit.}}
\def\JET{{\sl J. Econom.\ Theory}}
\def\JFI{{\sl J. Franklin Inst.}}
\def\JFM{{\sl J. Fluid Mech.}}
\def\JLMS{{\sl Proc.\ Lond.\ Math.\ Soc.}}
\def\JMM{{\sl J. Math.\ Mech.}}
\def\JMO{{\sl J. Mod.\ Optics\/}}
\def\JMP{{\sl J. Math.\ Phys.}}
\def\JOSAB{{\sl J. Opt.\ Soc.\ Amer.\ B}}
\def\JPA{{\sl J. Phys.\ A:  Math.\ Gen.}}
\def\JPC{{\sl J. Phys.\ C:  Solid State Phys.}}
\def\JPCh{{\sl J. Phys.\ Chem.}}
\def\JPSJ{{\sl J. Phys.\ Soc.\ Jpn.}}
\def\JSP{{\sl J. Statist.\ Phys.}}
\def\JTB{{\sl J. Theor.\ Biol.}}
\def\LAS{{\sl Los Alamos Science\/}}
\def\MA{{\sl Math.\ Ann.}}
\def\MRSP{{\sl Mat.\ Res.\ Soc.\ Proc.}}
\def\MST{{\sl Math.\ Systems Theory\/}}
\def\Na{{\sl Nature\/}}
\def\NPB{{\sl Nucl.\ Phys.\ B}}
\def\Or{{\sl Order\/}}
\def\Ph{{\sl Physics\/}}
\def\PAMS{{\sl Proc.\ Amer.\ Math.\ Soc.}}
\def\PCPS{{\sl Proc.\ Camb.\ Phil.\ Soc.}}
\def\PA{{\sl Physica A\/}}
\def\PD{{\sl Physica D\/}}
\def\PJM{{\sl Pacific J. Math.}}
\def\PLA{{\sl Phys.\ Lett.\ A\/}}
\def\PLB{{\sl Phys.\ Lett.\ B\/}}
\def\PNAS{{\sl Proc.\ Nat.\ Acad.\ Sci.\ U.S.A.}}
\def\PNAW{{\sl Proc.\ Nederl.\ Akad.\ Wetensch.}}
\def\PNAWA{{\sl Proc.\ Nederl.\ Akad.\ Wetensch., Ser.\ A}}
\def\PRp{{\sl Phys.\ Rep.}}
\def\PR{{\sl Phys.\ Rev.}}
\def\PRA{{\sl Phys.\ Rev.\ A\/}}
\def\PRB{{\sl Phys.\ Rev.\ B\/}}
\def\PRD{{\sl Phys.\ Rev.\ D\/}}
\def\PRE{{\sl Phys.\ Rev.\ E\/}}
\def\PRL{{\sl Phys.\ Rev.\ Lett.}}
\def\PRSLA{{\sl Proc.\ Roy.\ Soc.\ Lond.\ A\/}}
\def\PRSLB{{\sl Proc.\ Roy.\ Soc.\ Lond.\ B\/}}
\def\PS{{\sl Philos.\ Sci.}}
\def\PSAM{{\sl Proc.\ Symp.\ Appl.\ Math.}}
\def\PT{{\sl Parasitol.\ Today\/}}
\def\PhT{{\sl Phys.\ Today\/}}
\def\PTP{{\sl Prog.\ Theor.\ Phys.}}
\def\PTRSLA{{\sl Phil.\ Trans.\ Roy.\ Soc.\ Lond.\ A\/}}
\def\QIP{{\sl Quantum Inform.\ Processing}}
\def\RMP{{\sl Rev.\ Mod.\ Phys.}}
\def\Sc{{\sl Science\/}}
\def\SIAMJC{{\sl SIAM J. Comput.}}
\def\SIAMJNA{{\sl SIAM J. Numer.\ Anal.}}
\def\SIGACTN{{\sl SIGACT News\/}}
\def\SMS{{\sl Smart Mater.\ Struct.}}
\def\SPAWPM{{\sl Sitzungsber.\ Preuss.\ Akad.\ Wiss., Phys.-Math.}}
\def\SPJETP{{\sl Sov.\ Phys.\ JETP\/}}
\def\SRO{{\sl Sociological Research Online}}
\def\SSc{{\sl Surface Science\/}}
\def\TAMS{{\sl Trans.\ Amer.\ Math.\ Soc.}}
\def\TIEICEJE{{\sl Trans.\ IEICE Japan E\/}}
\def\TMP{{\sl Theor.\ and Math.\ Phys.}}
\def\UMN{{\sl Uspekhi Mat.\ Nauk}}
\def\YMJ{{\sl Yokohama Math.\ J.}}
\def\ZP{{\sl Z. Physik\/}}
\def\ZPC{{\sl Z. Phys.\ C---Particles and Fields\/}}


\def\dajm{\hbox{D. A. Meyer}}
\def\luca{\hbox{L. Bombelli}}
\def\rds{\hbox{R. D. Sorkin}}
\def\ljdr{\hbox{\luca, J. Lee, \dajm\ and \rds}}
\def\brosl{\hbox{B. Hasslacher}}
\def\bd{\hbox{\brosl\ and \dajm}}
\def\mhfreedman{\hbox{M. H. Freedman}}
\def\mike{\hbox{M. H. Freedman}}
\def\md{\hbox{\mike\ and \dajm}}
\def\md{\hbox{\mike\ and \dajm}}
\def\heather{\hbox{H. Blumer}}
\def\dh{\hbox{\dajm\ and \heather}}
\def\nrwallach{\hbox{N. R. Wallach}}
\def\dn{\hbox{\dajm\ and \nrwallach}}
\def\dd{\hbox{D. \"O. G\"uney and \dajm}}
\def\dj{\hbox{\dajm\ and J. Pommersheim}}

\def\baxter{\hbox{R. J. Baxter}}
\def\boghosian{\hbox{B. M. Boghosian}}
\def\bv{\hbox{E. Bernstein and U. Vazirani}}
\def\deutsch{\hbox{D. Deutsch}}
\def\feynman{\hbox{R. P. Feynman}}
\def\fg{\hbox{E. Farhi and S. Gutmann}}
\def\frisch{\hbox{U. Frisch}}
\def\grover{\hbox{L. K. Grover}}
\def\gz{\hbox{G. Gr\"ossing and A. Zeilinger}}
\def\hpdp{\hbox{J. Hardy, Y. Pomeau and O. de Pazzis}}
\def\hdpp{\hbox{J. Hardy, O. de Pazzis and Y. Pomeau}}
\def\pitowsky{\hbox{I. Pitowsky}}
\def\rothman{\hbox{D. H. Rothman}}
\def\shiyi{\hbox{S. Chen}}
\def\shor{\hbox{P. W. Shor}}
\def\simon{\hbox{D. R. Simon}}
\def\teich{\hbox{W. G. Teich}}
\def\vonneumann{\hbox{J. von Neumann}}
\def\kitaev{\hbox{A. Yu.\ Kitaev}}
\def\gottesman{\hbox{D. Gottesman}}
\def\rains{\hbox{E. M. Rains}}
\def\steane{\hbox{A. M. Steane}}
\def\yepez{\hbox{J. Yepez}}

\def\hfb{\hfil\break}

\catcode`@=11
\newskip\ttglue

\font\tenrm=cmr10   \font\ninerm=cmr9    \font\eightrm=cmr8
\font\sixrm=cmr6
\font\tenbf=cmbx10  \font\ninebf=cmbx9   \font\eightbf=cmbx8
\font\sixbf=cmbx6
\font\tenit=cmti10  \font\nineit=cmti9   \font\eightit=cmti8  
\font\tensl=cmsl10  \font\ninesl=cmsl9   \font\eightsl=cmsl8  
\font\tenmi=cmmi10  \font\ninemi=cmmi9   \font\eightmi=cmmi8
\font\sixmi=cmmi6
\font\tentt=cmtt10  \font\ninett=cmtt9   \font\eighttt=cmtt8

\font\bigten=cmr10 scaled\magstep2 

\def\ninepoint{\def\rm{\fam0\ninerm}%
  \textfont0=\ninerm \scriptfont0=\sixrm
  \textfont1=\ninemi \scriptfont1=\sixmi
  \textfont\itfam=\nineit  \def\it{\fam\itfam\nineit}%
  \textfont\slfam=\ninesl  \def\sl{\fam\slfam\ninesl}%
  \textfont\bffam=\ninebf  \scriptfont\bffam=\sixbf
    \def\bf{\fam\bffam\ninebf}%
  \tt \ttglue=.5em plus.25em minus.15em
  \normalbaselineskip=11pt
  \setbox\strutbox=\hbox{\vrule height8pt depth3pt width0pt}%
  \normalbaselines\rm}

\def\eightpoint{\def\rm{\fam0\eightrm}%
  \textfont0=\eightrm \scriptfont0=\sixrm
  \textfont1=\eightmi \scriptfont1=\sixmi
  \textfont\itfam=\eightit  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf  \scriptfont\bffam=\sixbf
    \def\bf{\fam\bffam\eightbf}%
  \tt \ttglue=.5em plus.25em minus.15em
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \normalbaselines\rm}

\def\sfootnote#1{\edef\@sf{\spacefactor\the\spacefactor}#1\@sf
      \insert\footins\bgroup\eightpoint
      \interlinepenalty100 \let\par=\endgraf
        \leftskip=0pt \rightskip=0pt
        \splittopskip=10pt plus 1pt minus 1pt \floatingpenalty=20000

\parskip=0pt\smallskip\item{#1}\bgroup\strut\aftergroup\@foot\let\next}
\skip\footins=12pt plus 2pt minus 2pt
\dimen\footins=30pc

\def\ie{{\it i.e.}}
\def\eg{{\it e.g.}}
\def\etc{{\it etc.}}
\def\etal{{\it et al.}}

\def\Lemma{L{\eightpoint EMMA}}
\def\Theorem{T{\eightpoint HEOREM}}
\def\Example{E{\eightpoint XAMPLE}}
\def\Examples{E{\eightpoint XAMPLES}}
\def\Corollary{C{\eightpoint OROLLARY}}
\def\Conjecture{C{\eightpoint ONJECTURE}}
\def\Definition{D{\eightpoint EFINITION}}
\def\Proposition{P{\eightpoint ROPOSITION}}
\def\endproof{\vrule height6pt width4pt depth2pt}

\def\groebner{G{\eightpoint ROEBNER}}
\def\xor{{\eightpoint XOR}}
\def\or{{\eightpoint OR}}
\def\and{{\eightpoint AND}}
\def\calit{{C{\eightpoint AL}$\cdot({\rm IT})^2$}}

\def\Htwon{(\C^2)^{\otimes n}}
\def\Hless{(\C^2)^{\otimes n-1}}

\def\hfb{\hfil\break}

\def\Laplace{1}
\def\WSSB{2}

\input epsf.tex

\magnification=1200
\nopagenumbers
\parskip=10pt
\global\setbox1=\hbox{0.\enspace}
\global\setbox2=\hbox{0. a.\enspace}
\parindent=\wd1


\line{M{\eightpoint ATH} 168A\hfill                       20 May 2019}
%\line{\hfill quant-ph/yymmnnn}
\bigskip
\centerline{\bf Random Walk Algorithms:  Bonus Problem}

\bigskip
%--------|---------|---------|---------|---------|---------|---------|
\noindent Consider a random walk $\{D_t\mid t\in\N\}$ on the set 
$\{0,1,\ldots,n\}$ defined by the transition probability matrix with 
entries:
$$
P_{ij} = \cases{1 & if $j = n$ and $i = j-1$;     \cr
                p & if $0 < j < n$ and $i = j-1$; \cr
              1-p & if $0 < j < n$ and $i = j+1$; \cr
                1 & if $j = 0$ and $i = j$;       \cr
                0 & otherwise.                    \cr
               }
$$
Let 
$$
T_d = \min_{t\ge0}\{D_t = 0\mid D_0 = d\}.
$$
How does $\hbox{\medss E}[T_d]$ depend on $n$ and $d$ for $p = 1/2$?  
For $p > 1/2$?  For $p < 1/2$?
    
\bye
