RandomizedAlgorithms.html

<!DOCTYPE html>
<html>
<!-- THIS FILE WAS GENERATED BY A SCRIPT: DO NOT EDIT IT! -->
    <head>
        <meta charset="utf-8">
        <meta name="viewport"
              content="width=device-width, initial-scale=1">
        <link href="style.css" rel="stylesheet" type="text/css"/>
        <title>
            Randomized Algorithms
        </title>
    </head>

    <body>
    <header id="header">
        <a id="logo" href="index.html">
            <img src="graphics/Julia.png" alt="">
            <span class="brand-text">Design &amp; Analysis of Algorithms</span>
        </a>
        <nav id="user-tools">
            <a href="index.html">Home</a>
            <a href="about.html">About</a>
            <a href="feedback.html">Feedback</a>
        </nav>
    </header>
        <h1>
            Randomized Algorithms
        </h1>

        <center>
        <img
        src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a5/6sided_dice.jpg/300px-6sided_dice.jpg">
        </center>
        <br>

        <details>
            <summary class="sum1">
                The hiring problem
            </summary>

            <p>
                Here's the algorithm:
            </p>

            <p>
            <code>
                <pre>
                Hire-Assistant(n)
                    best = 0
                    for i = 1 to n
                        interview candidate i
                        if i is better than best
                            best = i
                            hire(i)
                </pre>
            </code>
            </p>

            <details>
                <summary class="sum2">
                    Worst-case analysis
                </summary>
                <p>
                The worst case: the employment agency sets us up, and sends us
                candidates in worst-to-best order, so we hire every single one.
                </p>
            </details>


            <details>
                <summary class="sum2">
                    Probabilistic anaysis
                </summary>
                <p>
                We use probability theory to find an <em>average-case running
                time</em>. This is the average over some likely distribution of
                inputs.
                <br />
                <i>If</i> we don't know our likely inputs, we can't use
                probabilistic analysis.
                </p>

                <p>
                See also: 
                <a href="Probability.html">Probability basics</a>.
                </p>
            </details>


            <details>
                <summary class="sum2">
                    A randomized algorithm
                </summary>
                <p>
                We best the employment agency by shuffling
                their list of candidates, and seeing them
                in random order: we get a much lower average
                cost, as we shall prove.
                </p>

                <p>
                An algorithm is <i><b>randomized</b></i> if its behavior is
                controlled not only by its inputs but also by a <i><b>
                random-number generator</b></i> .
                <br />
                Random(m, n) returns with equal probability an integer between
                <i>m</i> and <i>n</i> inclusive. So Random(2, 4) returns either
                2, 3, or 4, each with probability 1/3.
                </p>

                <p>
                When we randomize the algorithm we speak of an <em>expected
                running time</em>.
                <br />
                <i>Average-case running time</i>: the probability distribution
                is over inputs.
                <br />
                <i>Expected running time</i>: the algorithm itself makes
                random choices.
                </p>

            </details>

        </details>


        <details>
        <summary class="sum1">
            Indicator random variables
        </summary>
             <p>
             (Note: <a href="https://en.wikipedia.org/wiki/Random_variable">
                 random variables</a> are actually functions.)
             <br>
             <br>
             X is an <em>indicator variable</em> for an event A if:
             <br>
             </p>
             <ul>
                 <li>X = 1 if A happens</li>
                 <li>X = 0 if A does not happen</li>
             </ul>

            <details>
             <summary class="sum2">
             Useful properties of indicator variables
             </summary>

             <p>
             If X is an indicator variable for A, then
             <br> <br>
                 Exp[X] = Prob[X=1] = Prob[A happens]
             
             <br> <br>
             This easily follows from the definition:
             <br>
             <br>
                 Exp[X] = 1 * Prob[X=1] + 0 * Prob[X=0] =
                 Prob[X=1] = Prob[A happens]
             <br>
             <br>

             <strong>Example:</strong>
             <br>
             <br>

             We throw a fair die 100 times  What is the expected number
             of times we get 1 or 6?
             <br>
             <br>

             Let X<sub>i</sub> be the indicator variable of the event "in
             i<sup>th</sup> throw we got 1 or 6".
             Then notice that the number of times we get 1 or 6 is:
             <br>
             <br>

             <img
             src=
             "graphics/Lec3Eq1.gif">
             <br>
             <br>

             and we want the expectation of this.
             By linearity of expectations:
             <br>
             <br>
             <img
             src=
             "graphics/Lec3Eq2.gif">

             <br>
             <br>

             and by the indicator variable properties:
             <br> <br>
             <img
             src=
             "graphics/Lec3Eq3.gif">

             <br> <br>

             To summarize:
             <br>
             <br>
             <img
             src=
             "graphics/Lec3Eq4.gif">
             <br>
             <br>

             So we expect to get 1 or 6 about 33.33 times.
             </p>
            </details>

            <details>
             <summary class="sum2">
                Analysis of hiring problem using indicator random variables
             </summary>
             <p>
                The first candidate we always hire. The second candidate will
                be better half the time, the third one will be better than the
                first two one third of the time, and so on, so we get the
                series:
                <br>
                <em>1 + 1/2 + 1/3 + 1/4...</em>
                <br>
                (Or <em>y = 1/x</em>.)
             <br>
             <br>
             So:
             <br>
             <br>
             <img
             src=
             "graphics/RandEq1.gif">
             <br>
             <br>
             <img
             src=
             "graphics/RandEq2.gif">
             <br>
             <br>
             <img
             src=
             "graphics/RandEq3.gif">
             <br>
             (By linearity of expectations.)
             <br>
             <br>
             <img
             src=
             "graphics/RandEq4.gif">

             <br>
             <br>
             <img
             src=
             "graphics/RandEq5.gif">
             <br>
             <br>
             Why is the last step true? <a
                 href="https://www.khanacademy.org/math/ap-calculus-ab/indefinite-integrals-ab/indefinite-integrals-of-common-functions-ab/v/antiderivative-of-x-1">
                 Video here.</a>
             <br>
             <br>
             Basically, the anti-derivative of <em>1/x</em> is ln <em>x</em>:
             <br>

             <img
             src="https://upload.wikimedia.org/wikipedia/commons/thumb/6/67/Integral_Test.svg/250px-Integral_Test.svg.png">
             </p>
            </details>
        </details>

        <details>
             <summary class="sum1">
             Randomized algorithms
             </summary>
             <p>
                In average-case analysis, we consider run-time over a
                probability distribution of inputs.
                <br />
                So, for Hire-Assistant, if we get candidates in order
                (with higher numbers meaning better):
                <br />
                A<sub>1</sub> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
                <br />
                we hire all 10 candidates. If we get:
                <br />
                A<sub>2</sub> = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
                <br />
                we hire only once. And if our input is:
                <br />
                A<sub>3</sub> = [5, 2, 1, 8, 4, 7, 10, 9, 3, 6]
                <br />
                we hire three times.
                So A<sub>1</sub> is very expensive input, A<sub>2</sub>
                is very cheap, and A<sub>3</sub> is in between.
             </p>

             <p>
                On the other hand, if we have a randomized algorithm,
                we can't say anything about how "good" A<sub>1</sub>,
                A<sub>2</sub>, and A<sub>3</sub> are as inputs: they are
                randomized before the hire code runs. <i>No particular input 
                elicits worst-case behavior</i>.
             </p>


            <details>
             <summary class="sum2">
             Randomly permuting arrays
             </summary>

             <p>
             <code>
                 <pre>
                 Permute-By-Sorting(A)
                    n = A.length
                    let P[1..n] be a new array
                    for i = 1 to n
                        P[i] = Random(1, n^3)
                    sort A, using P as sort keys
                 </pre>
             </code>
             </p>

             <p>
                We cube <i>n</i> to get at least 1 - 1/<i>n</i>^3
                probability that all enties are unique.
             </p>


            </details>

            <details>
                <summary class="sum2">
                  Run the Python code for the randomized
                  algorithm to hire an assistant
                </summary>
                 <p>
                     In the console below, type or paste:
                     <br/>
                     <code>
                         !git clone https://gist.github.com/91e59d2a36937f9be17cee01ddb9588d.git
                         <br/>
                         cd 91e59d2a36937f9be17cee01ddb9588d
                         <br/>
                         from hire_assistant import *
                         <br/>
                         n=18
                         <br/>
                         hire_assistant(n,False)
                         <br/>
                     </code>
                 </p>

        <div class="python-console">
            <iframe style="width: 640px; height: 480px;"
                    name="embedded_python_anywhere"
                    src="https://www.pythonanywhere.com/embedded3/" scrolling="yes">
            </iframe>
            <figcaption>
                Python console
            </figcaption>
        </div>


                 <p>
                     Now you can experiment with the algorithm
                     by changing the value of n
                     and running hire_assistant(n, False)
                 </p>
            </details>
        </details>

        <details>
             <summary class="sum1">
                Probabilistic analysis and further uses of indicator random
                variables
             </summary>

            <details>
             <summary class="sum2">
             The birthday paradox
             </summary>
             <p>

             <img
             src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/dd/Birthday_candles.jpg/250px-Birthday_candles.jpg">
             <br>
             <br>
             <br>
             Probability that two people have the same birthday: 1/365
             <br>
             <br>
             To generalize the problem, and see it doesn't just apply to
             birthdays, let's call the # of days in the year <em>n</em>.
             <br>
             <br>
             Let's set up an indicator random variable so that
             <em>X<sub>ij</sub></em> is:
             1 if persons i and j have the same birthday.
             <br>
             0 if the don't.
             <br>
             <br>
             Let <em>X</em> count the number of pairs of people who
             have the same birthday.
             <br> <br>
             <em>k</em> is the number of people in the room.
             <br> <br>
             <img src= "graphics/RandEq6.gif">
             <br> <br>
             Take expectations and apply linearity of expectation:
             <br> <br>
             <img src= "graphics/RandEq7.gif">
             <br> <br>
             <img src= "graphics/RandEq8.gif">
             <br> <br>
             <img src= "graphics/RandEq9.gif">
             <br> <br>
             <img src= "graphics/RandEq10.gif">
             <br>
             <br>
             So we need:
             <br />
             <i>k</i><sup>2</sup> &ge; 2n
             <br>
             For 365 days in a year, square root of 730 &asymp; 27.
             <br>
             So we are looking at <em>&Theta;(n<sup>1/2</sup>)</em>,
             asymptotically speaking.
             </p>
            </details>


            <details>
                <summary class="sum2">
                Balls and bins
                </summary>

                <figure>
                    <img src="https://upload.wikimedia.org/wikipedia/commons/4/46/Assortment_of_40_mm_table_tennis_balls.jpg"
                    height="240" width="360">
                    <figcaption>
                    </figcaption>
                </figure>

                <p>
                    <i>b</i>: number of bins.
                    <br />
                    <i>n</i>: number of balls.
                    <br />
                    <i>Expected balls in a given bin?</i>: <i>n</i> / <i>b</i>
                    <br />
                    <i>Expected tosses until a given bin contains a ball?</i>:
                        <i>b</i>
                    <br />
                    <i>How many balls must we toss until we expect that every
                        bin contains at least one ball?</i>
                    <br />
                    Call a ball falling in an empty bin a "hit." 
                    <br />
                    First toss is a guaranteed hit!
                    <br />
                    For the next stage, we have <i>i</i> - 1 bins
                    containing balls, and <i>b</i> - <i>i</i> + 1 bins
                    empty.
                    <br />
                    So for <i>i</i>th stage, the probability of a hit is:
                    <br />
                    (<i>b</i> - <i>i</i> + 1) / <i>b</i>
                    So, for 6 bins, the expected tosses to fill the next bin
                    are:
                    <br />
                    E(n<sub>2</sub>) = 6 / 5
                    <br />
                    E(n<sub>3</sub>) = 6 / 4
                    <br />
                    E(n<sub>4</sub>) = 6 / 3
                    <br />
                    (Some math equations to be filled in!)
                    <br />
                    And we get <i>b</i> ln <i>b</i> for the expected number of
                    tosses until each bin has at least one ball in it.
                </p>

            </details>


            <details>
                <summary class="sum2">
                Streaks
                <br />
                NOT COVERED FALL 2017
                </summary>
            </details>


            <details>
                <summary class="sum2">
                The on-line hiring problem
                <br />
                NOT COVERED FALL 2017
                </summary>
             <p>

             </p>
            </details>
        </details>

        <details>
            <summary class="sum1">
                Source Code
            </summary>
            <p>
            
<a href="https://github.com/gcallah/algorithms/tree/master/Java/RandomizedAlgorithms">Java</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Ruby/RandomizedAlgorithms">Ruby</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/C++/RandomizedAlgorithms">C++</a><br>
<a href="https://github.com/gcallah/algorithms/tree/master/Python/RandomizedAlgorithms">Python</a><br>
            </p>
        </details>

    </body>
    <script>
        (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
        ga('create', 'UA-97026578-2', 'auto');
        ga('send', 'pageview');
    </script>
</html>