title: Why on a reference string and its reverse page faults are same by LRU and Optimal Page Replacement Algorithm?
body: <p>I was reading <strong>Virtual Memory</strong> from <a href="https://rads.stackoverflow.com/amzn/click/com/1118063333" rel="nofollow noreferrer" rel="nofollow noreferrer">Operating System Concepts by Galvin</a> and came across a statement, it says: </p>
  
  <p>"<strong>We can think of LRU strategy as the optimal page-replacement algorithm looking backward in time, rather than forward.</strong>"</p>
  
  <p>Then on the other line, it says:</p>
  
  <p>"<strong>If we let <code>Sr</code> be the reverse of a reference string <code>S</code>, then the page-fault rate for the OPT algorithm(Optimal Page Replacement) on <code>S</code> is the same as the page-fault rate for the OPT algorithm on <code>Sr</code>. Similarly, the page-fault rate for the LRU algorithm(Least recently Used) on <code>S</code> is the same as the page-fault rate for the LRU algorithm on <code>Sr</code>.</strong>" </p>
  
  <p>So if <code>LRU</code> is <code>OPT</code> looking backward in time then how come on a string and it's reverse page faults are same, because according to my understanding of the first statement: if page fault on a string S by LRU is <code>x</code> and and by OPT is <code>y</code>, then page faults on it's reverse string Sr by LRU and OPT must by <code>y</code> and <code>x</code> respectively.</p>
  
  <p>Why they <strong>must</strong> be same everytime for every string set and it's reverse?</p>
  
  <p>LRU: Least Recently Used Page Replacement</p>
  
  <p>OPT: Optimal Page Replacement</p>