Cloned estimators have identical randomness but different RNG instances

### Describe the bug

Cloned estimators have identical randomness but different RNG instances. According to documentation, it should be the other way around: different randomness but identical RNG instances.

Related #25395 

The User Guide [says](https://scikit-learn.org/stable/common_pitfalls.html#controlling-randomness):
> For an optimal robustness of cross-validation (CV) results, pass RandomState instances when creating estimators

> ```python
> rf_inst = RandomForestClassifier(random_state=np.random.RandomState(0))
> cross_val_score(rf_inst, X, y)
> ```
> ...
> Since `rf_inst` was passed a `RandomState` instance, each call to `fit` starts from a different RNG. As a result, the random subset of features will be different for each folds

In regards to cloning, the same reference says:
> ```python
> rng = np.random.RandomState(0)
> a = RandomForestClassifier(random_state=rng)
> b = clone(a)
> ```
> Moreover, `a` and `b` will influence each-other since they share the same internal RNG: calling `a.fit` will consume `b`’s RNG, and calling `b.fit` will consume `a`’s RNG, since they are the same. 

The actual behaviour does not follow this description. 

### Steps/Code to Reproduce

```python
import numpy as np
from sklearn import clone
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_validate
from sklearn.ensemble import RandomForestClassifier

rng = np.random.RandomState(0)
X, y = make_classification(random_state=rng)
rf = RandomForestClassifier(random_state=rng)

d = cross_validate(rf, X, y, return_estimator=True, cv=2)
rngs = [e.random_state for e in d['estimator']]
# estimators corresponding to different CV runs have different but identical RNGs:
print(rngs[0] is rngs[1]) # False
print(all(rngs[0].randint(10, size=10) == rngs[1].randint(10, size=10))) # True

rf_clone = clone(rf)
rngs = [rf.random_state, rf_clone.random_state]
print(rngs[0] is rngs[1]) # False
print(all(rngs[0].randint(10, size=10) == rngs[1].randint(10, size=10))) # True
```

### Expected Results

True False True False

### Actual Results

False True False True

### Versions

```shell
Tested on a two-week-old dev build and also on the following version (Kaggle)

System:
    python: 3.7.12 | packaged by conda-forge | (default, Oct 26 2021, 06:08:53)  [GCC 9.4.0]
executable: /opt/conda/bin/python3.7
   machine: Linux-5.15.90+-x86_64-with-debian-bullseye-sid

Python dependencies:
          pip: 22.3.1
   setuptools: 59.8.0
      sklearn: 1.0.2
        numpy: 1.21.6
        scipy: 1.7.3
       Cython: 0.29.34
       pandas: 1.3.5
   matplotlib: 3.5.3
       joblib: 1.2.0
threadpoolctl: 3.1.0

Built with OpenMP: True
```

COMMENT:
> I wonder about point 6: people might use a predictor that sample the posterior, and be surprised if multiple calls give the same samples.

I think you can argue that this is a case that is different from what the code snippet shows. At least for me what you point out is more akin to this:
```python
clf = FooWithSamplingClassifier(random_state=<int or random_state>).fit(X, y)

# calling once
pred1 = clf.predict(X)
# calling twice
pred2 = clf.predict(X)
np.assert_array_not_equal(pred1, pred2)
```
Where `FooWithSamplingClassifier` is a classifier that does some sampling as part of its prediction.

For me the take away is that `predict()` can't make promises because the right answer depends on the estimator. Some estimators are fully deterministic (repeated calls to `predict` with same `X` will return same prediction), some estimators use randomness to perform sampling (repeated calls to `predict` with same `X` will return different predictions) and some estimators use randomness to make predictions but there should be no history (repeated calls to `predict` with same `X` will return the same prediction). The last example is my understanding of a example Adrin brought up. It is an algorithm that uses randomness to make its prediction but importantly the prediction should not depend on how many times `predict` has been called previously.

These three use-cases all seem legitimate so I think we can't enforce a particular contract, it will depend on the estimator. It also means whether a `int` or `random_state` is passed in doesn't matter, you need to read the estimator's docs to know how it will behave.

> My take on point 6 in [#26148 (comment)](https://github.com/scikit-learn/scikit-learn/issues/26148#issuecomment-1536979006) is that it should result in 2 different random forests, thus the assert should fail. Otherwise we make it hard for someone who knows what she is doing with rng.

I think a person's expectation of what happens will depend on whether they think `RandomState(42)` is a mutable object or not. If you think that it is mutable then it makes sense that `rf1` and `rf2` are different. If you think that it is an immutable object then `rf1` and `rf2` should be the same. I don't know what my naive/unbiased by history expectation is about (im)mutability of `RandomState` objects. I've learnt they are mutable. However, I also know that at some point in their life every Python programmer falls into the "mutable object as default argument value" trap (`def foo(arg=[]):`). And it is tricky to explain to novice Python users why it totally makes sense that things work this way.

This makes me wonder if life would be simpler for everyone if we considered them immutable. Using the [JAX notation](https://jax.readthedocs.io/en/latest/notebooks/Common_Gotchas_in_JAX.html#random-numbers) (because you can go and read about it). To get two estimators that are the same you'd do:
```python
from jax import random
key = random.PRNGKey(0)

rf1 = RandomForestClassifier(random_state=key)
rf2 = RandomForestClassifier(random_state=key)
```
To have two different estimators you'd split the key before passing it to the constructor:
```python
from jax import random
key = random.PRNGKey(0)
key, rf1_key, rf2_key = random.split(key)
rf1 = RandomForestClassifier(random_state=rf1_key)
rf2 = RandomForestClassifier(random_state=rf2_key)
```

I quite like this. It is only marginally more complex to understand for a user than using integers as seeds and like with seeds you can have both kinds of behaviours. I think it is also possible to do this with the new random number generator infrastructure of Numpy?!

(n.b. I have rewritten my comment three or four times over the course of the last hour, and each time I changed my conclusion. But I think I like this version now, but who knows, if I think some more about it I might change my mind again??)

Labels: Bug, Documentation, Needs Decision