Use a Chernoff bound I've got a simple task: a share's price at day 0 is $Q$. Then each day it increases to $\frac{3}{2} \cdot q$ or decreases to $\frac{1}{2} \cdot q$ (where $q$ is its price the previous day), each with probability $\frac{1}{2}$. I am to show that the probability of the price being greater than $Q$ after $n$ days is $O(e^{-cn})$ for some constant $c > 0$. According to a hint, I should use the Chernoff bound and notice that $3^3 < 2^5$.
I've tried to use the Chernoff bound, but ended up with a useless result (and nowhere have I used that, yhm, magical inequality). Could you help me with this problem?
Here's how I've approached it:

*

*let $X_i$ be the price after the $i$-th day

*let $Y_i$ be a 0/1 variable denoting whether the price increases (1) or decreases (0) after the $i$-th day

*let $Z_i = Y_i + \frac{1}{2}$; then $X_n = Q \cdot Z_1 \cdot Z_2 \cdot \ldots \cdot Z_n$ (because $Z_i \in \{\frac{1}{2}, \frac{3}{2}\}$ and the price changes to $\frac{1}{2}$ or $\frac{3}{2}$ of its previous value with an equal probability)

*variables $Y_i$ are obviously independent, thus so are variables $Z_i$

*we try to use the Chernoff bound:
\begin{eqnarray}
  \mathbb{P}(X_n \geq Q)
    & =    & \mathbb{P}(Q \cdot Z_1 \cdot Z_2 \cdot \ldots \cdot Z_n \geq Q) \\
    & =    & \mathbb{P}(Z_1 \cdot Z_2 \cdot \ldots \cdot Z_n \geq 1) & \text{(because } Q > 0) \\
    & \leq & \min_{t > 0} \frac{\mathbb{E}(e^{t \cdot Z_1 \cdot Z_2 \cdot \ldots \cdot Z_n})}{e^t} & \text{(Chernoff bound)} \\
    & =    & \min_{t > 0} \frac{e^t \cdot \left( \mathbb{E}(e^Z) \right)^n}{e^t} & \text{(because all $Z_?$'s are independent and have the same distribution)} \\
    & =    & \left( \mathbb{E}(e^Z) \right)^n \\
    & =    & \left( e^\frac{1}{2} \cdot \frac{1}{2} + e^\frac{3}{2} \cdot \frac{1}{2} \right)^n & \text{(because $Z_i = 0/1 + \frac{1}{2}$, each with probability $\frac{1}{2}$)}
\end{eqnarray}

*but this is useless because $e^\frac{1}{2} \cdot \frac{1}{2} + e^\frac{3}{2} \cdot \frac{1}{2} > 1$
If I were to guess where I've gone astray, I see two sticky points:

*

*the very beginning of the inequality: $\mathbb{P}(X_n \geq Q)$ - the task asked us to for the probability of the strict inequality $X_n > Q$

*that pulling out of $e^t$ in $\min$ and reducing it in the enumerator and denominator seemed too easy

 A: OK, I've solved it if anyone's interested. The problem is I've approached this far too abstractly and didn't look at the specific values given here. The solution is quite nice so I'll post it:
Let $X_i$ be the share's price after the $i$-th day. Because each day the price is multiplied by either $\frac{1}{2}$ or $\frac{3}{2}$, then $X_i = Q \cdot \frac{1}{2^n} \cdot 3^{\text{the number of days when the price was increased}}$.
Let $Y_i$ be a 0/1 variable denoting whether the price increased (1) or decreased (0) after the $i$-th day. Obviously, the variables $Y_i$ are independent. Finally, let $Y = Y_1 + \ldots + Y_n$ and notice that $\mathbb{E}(Y) = n \cdot \frac{1}{2} = \frac{n}{2}$.
We have:
\begin{eqnarray}
  \mathbb{P}(X_n > Q) & = & \mathbb{P}\left(Q \cdot \frac{3^Y}{2^n} > Q\right) \\
                      & = & \mathbb{P}\left(\frac{3^Y}{2^n} > 1\right) \\
                      & = & \mathbb{P}(3^Y > 2^n) \\
                      & = & \mathbb{P}\left(3^Y > (2^5)^\frac{n}{5}\right) \\
                      & < & \mathbb{P}\left(3^Y \geq (3^3)^\frac{n}{5}\right) \text{ (the magic inequality!)} \\
                      & = & \mathbb{P}\left(3^Y \geq 3^\frac{3n}{5}\right) \\
                      & = & \mathbb{P}\left(Y \geq \frac{3n}{5}\right) \\
                      & = & \mathbb{P}\left(Y \geq \left(1 + \frac{1}{5}\right) \cdot \underbrace{\frac{n}{2}}_\text{=$\mathbb{E}(Y)$}\right) \\
                      & \leq & \exp\left(-\frac{\left(\frac{1}{5}\right)^2 \cdot \frac{n}{2}}{3}\right) \text{ (a special case of the Chernoff bound)} \\
                      & = & \exp\left(-\frac{1}{150} \cdot n\right) \\
                      & = & O(e^{-cn}) \text{ for $c = \frac{1}{150}$}
\end{eqnarray}
That concludes the proof.
