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:
During the Drafting meeting, @adrinjalali @ogrisel @glemaitre @betatim and I discussed many aspects of random state.

Here is my summary of the discussion:

1. We agree on `randon_state=None` and `random_state=int` behavior. The hard part is the random state objects.
2. We agree that we should leave the current behavior alone. I think the docs should be updated to reflect the actual behavior.
3. We want to use the move to NumPy Generators to support the desired behavior. We do not need to worry about backward compatibility, because NumPy Generators are new objects to pass around.
4. We reconsidered [SLEP011](https://github.com/scikit-learn/enhancement_proposals/pull/24) and are undecided.
5. There is no API contract about randomness for multiple calls to predict. In scikit-learn, I think we are consistent and that multiple calls to `predict` with the same data give the same output.
6. We have a conflict about what the desired behavior of the following should be:

```python
rng = np.random.RandomState(42)
rf1 = RandomForestClassifier(random_state=rng).fit(X, y)
rf2 = RandomForestClassifier(random_state=rng).fit(X, y)

# Should the above give the same model, and thus the same predictions?
np.assert_array_equal(rf1.predict(X), rf2.predict(X))
```

### Cross validation and max entropy
We agree that in any cross validation such as GridSearchCV should give the maximum amount of entropy with a way to make it deterministic. As described in https://github.com/scikit-learn/scikit-learn/issues/26148#issuecomment-1508389314 there is no way to make it possible now **and** be deterministic. We did not come up with a good way to do it with `Generators` either. 

Estimators that know what they are spawning (RandomForestClassifer) do not have this issue and can use [SeedSequences](https://numpy.org/doc/stable/reference/random/parallel.html). Concretely, `RandomForestClassifer` can pass the random state objects to the tree directly because the forest knows it is dealing with trees. On the other hand, `GridSearchCV` can not pass this random state down because there is no API for passing these objects to an estimator.

Labels: Bug, Documentation, Needs Decision