Explanation about this probabilistic proof that leads to $log_RN$ I am reading a proof based on (probabilistic) analysis on how a specific data structure performs for the case of search miss.
The base assumption is that the probability that each of the $N$ keys in a random trie differs from a random search key in at least one of the leading $t$ characters is $(1 - R^{-t})^N$ where $R$ is the alphabet size.
Then it defines as $1 - (1 - R^{-t})^N$ as the probability that the search requires more than $t$ character comparisons.
So far so good.  The following is the part I get lost.
The text says that from probabilistic analysis the sum for $t = 0, 1, 2, ...$ of the probabilities that an integer random variable is $>t$ is the average value of that random variable so the average cost is:
$1 - (1 - R^{-1})^N + 1 - (1 - R^{-2})^N 1 - (1 - R^{-3})^N + ... + 1 - (1 - R^{-t})^N$  and that using the approximation $(1-\frac{1}{x})^x \approx e$ we find the search cost to be approximately:
$(1 - e^{-\frac{N}{R^1}}) + (1 - e^{-\frac{N}{R^2}}) + ... + (1 - e^{-\frac{N}{R^t}})$
But I don't understand how we ended up with this form from the one above.
Then the proof continues that the summand is extremely close to $1$ for approximately $ln_RN$ terms with $R^t$ substantially smaller than $N$; it is extremely close to $0$ for all the terms with $R^t$ substantially greater than $N$; and it is between $0$ and $1$ for the few terms with $R^t \approx N$. So the grand total is about $log_R N$. I don't understand this explanation.
Can someone help me understand these two parts of the analysis?
Also I see in the last paragraph the text switches from $ln_RN$ to $log_RN$ are they the same thing?
 A: 
The text says that from probabilistic analysis the sum for $t = 0, 1, 2, ...$ of the probabilities that an integer random variable is $>t$ is the average value of that random variable so the average cost is:
$1 - (1 - R^{-1})^N + 1 - (1 - R^{-2})^N + \underbrace{1 - (1 - R^{-3})^N} + ... + 1 - (1 - R^{-t})^N$  and that using the approximation $(1-\frac{1}{x})^x \approx e$ we find the search cost to be approximately:
$(1 - e^{-\frac{N}{R^1}}) + (1 - e^{-\frac{N}{R^2}}) + ... + (1 - e^{-\frac{N}{R^t}})$
But I don't understand how we ended up with this form from the one above.

First, a correction; it's not true that $(1 - \frac 1 x)^x \approx e$, as claimed; rather, it holds that $(1 - \frac 1 x)^x \approx e^{\color{red}{-1}}$ instead. Perhaps there's a mistake in the original text, which may explain where you got lost; note that the approximation $(1 + \frac 1 x)^x \approx e$ is also true.
To see what's going on in the argument, let's focus on the $i^{\text{th}}$ term of your original summation. In the block quote above, I have placed an underbrace on the $i = 3$ term to illustrate what I'm looking at.
\begin{align*}
  1 - (1 - R^{-i})^N &= 1 - \left((1 - R^{-i})^{R^i} \right)^{\frac N {R^i}} & \text{(in exponent, multiply and divide by $R^i$)}\\
&= 1 - \left(e^{-1} \right)^{\frac N {R^i}} & \text{(use $(1 - 1/x )^x \approx e^{-1}$ inside parentheses)}
\end{align*}
Replacing each of the terms in the original expression gives the claimed one.

Then the proof continues that the summand is extremely close to $1$ for approximately $ln_RN$ terms with $R^t$ substantially smaller than $N$; it is extremely close to $0$ for all the terms with $R^t$ substantially greater than $N$; and it is between $0$ and $1$ for the new terms with $R^t \approx N$. So the grand total is about $log_R N$. I don't understand this explanation.

This part seems less rigorous than I would prefer, but perhaps that's because I'm just seeing your summary rather than the original proof. At any rate, the basic idea is to partition the terms in the summation based on the relative values of $R^t$ and $N$.
There are three "classes" of $N / R^t$ comparisons presented:

*

*those for which $t$ is small enough that $R^t$ is much smaller than $N$

*those for which $t$ is appropriately large that $R^t$ and $N$ are comparable to one another

*those for which $t$ is very large, meaning $R^t$ is much larger than $N$
For the first case, note that the inequality $R^t < N$ is equivalent to $t < \log_R N$. There are therefore exactly $\lfloor \log_R N \rfloor$ terms which satisfy this equation. Only the last few terms will have near-equality; most will have $t << \log_R N$. If $\log_R N$ is large, then there won't be many of these near-equality terms in the comparison, and most will be of the other flavor ("$t$ is much less than $\log_R N$"). Hence, it's fair to say that most of the $\log_R N$ terms will have $R^t << N$, meaning the corresponding summand will be $1 - (e^{-\text{large number}}) \approx 1$.
I think their argument is that there aren't many terms in the second category ($R^t \approx N$), but I'm not sure what's mean by "new" terms so I'm not completely sure. (Again, I'd strongly prefer an argument that explicitly bounds all the relevant terms, but that's just me.) But, there should be relatively few of these when compared to the first class, so their contribution to the sum is negligible.
For the third category, if $R^t$ is much larger than $N$, then $N / R^t \approx 0$, whence $1 - e^{N/R^t} \approx 1 - e^0 = 0$. But again, a complete proof should be careful here; if you add lots of small terms, you can't guarantee that their sum will be small. This is why explicit bounds on the various quantities would be preferable. Presumably, there's some argument about how many terms can appear in this summation or something like that.

Also I see in the last paragraph the text switches from $ln_RN$ to $log_RN$ are they the same thing?

These are almost certainly both just meant to be "logarithm in base $R$", yes.
