Hoeffding's inequality with a probabilistic bound? Hoeffding's inequality states that: 
Let $\mathbf{X}_1, \dots, \mathbf{X}_n$ be independent random variables, such that $\mathbf{X}_i \in [a_i, b_i]$ with probability one. Let $\mathbf{S}_n$ be $\sum_i^n\mathbf{X}_i$. Then for any $t>0$
$$
\mathbb{P}(|\mathbf{S}_n-\mathbb{E}[\mathbf{S}_n]|\geq t) \leq 2\exp(-\dfrac{2t^2}{\sum_i^n(b_i-a_i)^2})
$$
Now, I wonder if this has any variant for the case like $\mathbf{X}_i \in [a_i, b_i]$ with probability $p_i$? Is there any theorems related? What terminologies should I use to google these results?
 A: In the most general case where the distribution of $X_i$ can be anything when outside of $[a_i, b_i]$, there can be no result - we can take a mixture of the uniform distribution on $[a, b]$ with probability $p$ and the Cauchy distribution with probability $1-p$. Just like the Cauchy distribution itself, this mixture distribution will also have undefined mean and variance, and there will be little we can say about it. 
However, if we place restrictions on what can happen outside of the interval $[a, b]$ the situation is not so bad! There is a well-known extension of Hoeffding's inequality where requirement that $X_i$ are bounded is relaxed and $X_i$ is only required to be sub-Gaussian. Sub-Gaussian distributions have "thin tails" that decay rapidly relative to the Gaussian distribution: 
$$ \forall i, P(|X_i|\geq t)\leq 2e^{-ct^2} \tag{1}$$
Then we can have a result very similar to Hoeffding's inequality. See Theorem 2.6.2 of High Dimensional Probablity by Vershynin, for instance:
$$ P(S \geq t) \leq 2 \exp \Bigg( -\frac{ct^2}{\sum_{i=1}^n ||X_i||^2_{\psi_2}} \Bigg) \tag{2}$$.
Where the notation $||X||_{\psi_2}$ refers to the "sub-Gaussian norm" defined in the same book. 
For the case where $X$ is unbounded and no particular restriction is placed on the tails, I'm not aware of any result better than Chebyshev's Inequality. Chebyshev's inequality works for any distribution with finite mean and variance so is very general. Let $\mu = \mathbb{E}[S] = \sum_{i=1}^n \mathbb{E}[ X_i ]$ and $\sigma^2 = \mathrm{Var}[S] = \sum_{i=1}^n \mathrm{Var}[ X_i] $. Then the Chebyshev bound is:
$$ P(|S-\mu|\geq k\sigma) \leq \frac{1}{k^2} \tag{3} $$
Which we could also write in the same form as the other theorems but substituting $t = k\sigma$:
$$ P(|S-\mu|\geq t) \leq \frac{\sigma^2}{t^2} \tag{4} $$
As for other references, definitely try Vershynin's book. There was also a Google hit for "unbounded Hoeffding inequality" but I haven't read it. 
